CSC373H Matrix Chain
Dan Zingaro
October 2016
Matrices: Order of Multiplication
Multiplying two matrices of dimensions pq and qr takes pqr multiplications
Consider these three matrices: Ais1x10
Bis10x10 Cis10x100
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 Therearen−1choicesforthis
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
Supposethebestsplitisp1=A0A1…Ak−1and 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]isthesmallestcostofmultiplyingAiAi+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
N[i,j] =
i