Question

Find an optimal parenthesization of a matrix-chain product

Answer 1

MATRIX-MULTIPLY(Ap×q, Bq×r)
1. for i ← 1 to p
2. for j ← 1 to r
3. C[i, j] ← 0
4. for k ← 1 to q
5. C[i, j] ← C[i, j] + A[i, k] · B[k, j]
6. return C
Scalar multiplication in line 5 dominates time to compute C
number of scalar multiplications = pqr
B. Multiplication of Two Matrices [7]
MATRIX-MULTIPLY(A, B)
1. if A.columns ≠ B.rows
2. error “incompatible dimensions”
3. else let C be a new A.rows × B.columns matrix
4. for i = 1 to A.rows
5. for j = 1 to B.columns
6. cij = 0
7. for k = 1 to A.columns
8. cij = cij + aik • bkj
9. return C
Example:Consider three matrices A10100, B1005, and C550
There are two ways to parenthesize
((AB)C) = D10  5 · C5  50
AB  10 × 100 × 5 = 5000 scalar multiplications
DC  10 × 5 × 50 = 2500 scalar multiplications Total:
7500
(A(BC)) = A10  100 · E100  50
BC  100 × 5 × 50 = 25000 scalar multiplications
AE  10 × 100 × 50 = 50000 scalar multiplications Total:
7500
C. Matrix Chain Product Problem
Given a chain A1, A2,…, An of n matrices, where for i = 1,
2,…, n, matrix Ai has dimension pi-1  pi
Parenthesize the product A1A2…An such that the total
number of scalar multiplications is minimized [6].
Counting the number of parenthesizations
D. Dynamic Programming Approach [8]
Step 1: Structure of an optimal parenthesization
1. Let us use the notation Ai..j for the matrix that
results from the product Ai Ai+1 … Aj
2. An optimal parenthesization of the product
A1A2…An splits the product between Ak and
Ak+1 for some integer k where1 ≤ k < n
3. First compute matrices A1..k and Ak+1..n; then
multiply them to obtain the final matrix A1..n
4. Key observation: Parenthesizations of
subchains A1A2…Ak and Ak+1Ak+2…An must
also be optimal if the parenthesization of chain
A1A2…An is optimal.
5. In other words, the optimal solution to a
problem contains within it the optimal solution
to subproblems.
6.
Step 2: Recursive solution [9]
1. Let m[i, j] be the minimum number of scalar
multiplications that are needed to compute Ai..j
2. Minimum cost to compute A1..n is m[1, n]
3. Suppose the optimal parenthesization of Ai..j
splits the product between Ak and Ak+1 for some
integer k where i ≤ k < j
4. Ai..j = (Ai Ai+1…Ak)·(Ak+1Ak+2…Aj)= Ai..k ·
Ak+1..j
5. Cost of computing Ai..j = cost of computing Ai..k
+ cost of computing Ak+1..j + cost of multiplying
Ai..k and Ak+1..j
6. Cost of multiplying Ai..k and Ak+1..j is pi-1pk pj
7. m[i, j ] = m[i, k] + m[k+1, j ] + pi-1pk pj
for i ≤ k < j
8. m[i, i ] = 0 for i = 1,2,…,n
9. But optimal parenthesization occurs at one
value of k among all possible i ≤ k < j
10. Check all these and select the best one.
Step 3: Computing the optimal cost [10]
1. To keep track of how to construct an optimal
solution, we use a split table s
2. s[i, j ] = value of k at which Ai Ai+1 … Aj is split for
optimal parenthesization .

THANKU

[I hope this ans will help u]

{{{{ MARK AS BRAIN LIEST }}}}}