CSC373H Matrix Chain
Dan Zingaro
October 2021
Copyright By PowCoder代写 加微信 powcoder
Matrices: Order of Multiplication
▶ Multiplying two matrices of dimensions pq and qr takes pqr multiplications
▶ Consider these three matrices: ▶ Ais1x10
▶ B is 10 x 10 ▶ C is 10 x 100
▶ We want the product ABC
▶ Two choices: (AB)C or A(BC)
▶ Does it matter which one we choose?
Matrices: Order of Multiplication…
A1x10,B 10×10,C 10×100 ▶ (AB)C
▶ AB takes1∗10∗10=100multiplicationsandyieldsa1x10 matrix
▶ Then, (AB)C takes 1 ∗ 10 ∗ 100 = 1000 multiplications ▶ Total multiplications is 1100
▶ Now figure out how many multiplications for A(BC)! Hint: it’s way worse!
Matrix Chain Multiplication
▶ The matrix-chain multiplication problem asks for the best way to parenthesize a product of matrices to minimize total multiplications
▶ Input: Matrices A0, A1, . . . , An−1 with dimensions d0 x d1, d1 xd2,…,dn−1 xdn
▶ Output: fully parenthesized product that gives minimum number of multiplications
▶ Brute force is impractical: there are Ω(4n) ways to parenthesize a product of n matrices
Matrix Chain: Greedy?
Perhaps we can do the product of smallest cost first? No. Smallest counterexample:
A10x1,B 1×10,C 10×100
Product of largest cost first?
No again. Smallest counterexample is one we saw before: A1x10,B 10×10,C 10×100
Greedy isn’t going to work.
Matrix Chain: Step 1
On to dynamic programming!
▶ Consider where to put the last product ▶ There are n − 1 choices for this
▶ A0(A1…An−1)
▶ (A0A1)(A2…An−1) ▶ …
▶ (A0A1…An−2)An−1
▶ If we knew the cost of each of these n − 1 choices, we could pick the best one
Matrix Chain: Step 1…
Optimal substructure of matrix chain multiplication
▶ Suppose the best split is p1 = A0A1 …Ak−1 and p2 =AkAk+1…An−1 forsome1≤k≤n−1
▶ Then the overall solution must contain optimal solutions to p1 and p2. Why?
▶ For contradiction, suppose the optimal solution uses some suboptimal solution for p1
▶ Then replace that suboptimal solution to p1 with the optimal solution to p1 to get a better overall solution
▶ (Analogous proof by contradiction for p2)
Matrix Chain: Step 2
▶ We have a 2d array this time
▶ N[i, j] is the smallest cost of multiplying +1 . . . Aj
Matrix Chain: Step 3
▶ The cost of multiplying one matrix is 0 ▶ Otherwise, we do three kinds of work
▶ N[i, k − 1] for the multiplication of the left subproduct ▶ N[k,j] for the multiplication of the right subproduct
▶ didkdj+1 for the final multiplication
0, if i = j
min{didkdj+1+N[i,k−1]+N[k,j]} ifi