Koushik Dasika

Hacker/Mathist Extraordinaire

Dynamic Programming: Chain Matrix Multiplication

If you would prefer reading the post as a contiguous block rather than a slide show,

Motivation

The purpose of this post is to show a fully worked out example of Chain Matrix Multiplication using dynamic programming, a fancy term for breaking a big problem down into subproblems which are easier to solve. (Note: Not the technical definition)

There are multiple sources online with great proofs, source code, and explanation of the proofs, but I did not find an example problem that I felt was easy to understand and follow. I hope that the proofs become much easier to understand after seeing this problem worked out.

You may be wondering “What is my motivation for doing this problem using Dynamic Programming when I could just as easily multiply the matrices in order and be done with it?”. Well, suppose that the matrices are really big; as in, each matrix was a couple of hundred columns and rows. Ordinary matrix multiplication is an Θ(n3) operation, so it will take many operations. It just so happens that the order in which you multiply matrices makes a huge difference in the number of calculations you have to do. That’s why we look for the optimal order (technical term is factorization) of multiplication.

Preliminaries

Notation

  • The symbol ‘×’ will be used to signify multiplying two matrices together.
  • The symbol ’’ will be used to signify multiplying two integers together.
  • Za,b will be used to signify the cost of multiplying all the matrices from Matrix a to Matrix b together in the optimal order.

Preliminaries 2

Prerequisite Math Facts

  • Ap x q × Bq x r will take pqr operations, where A is a matrix with p rows and q columns and B is a matrix with q rows and r columns.
  • Matrix multiplication is associative, so A × (B × C) == (A × B) × C.
  • Multiplying Ap x q × Bq x r will yield the matrix C p x r.
  • For matrices A and B, A × B B × A

Preliminaries 3

Cost Table

× 1 2 3 4 5
1 0 ? ? ? ?
2 - 0 ? ? ?
3 - - 0 ? ?
4 - - - 0 ?
5 - - - - 0

We will use this table to keep track of the cost of multiplying matrices. Notice that the diagonals are all 0; it’s because we won’t be multiplying a matrix by itself. The boxes with hyphens will be ignored because matrix multiplication works from left to right, not the other way around. Element Za,b in the table will be the cost of multiplying all the matrices between a and b. Getting the top right corner box will give us our final answer.

Preliminaries 4

Dimensions Table

× 1 2 3 4 5
1 3 x 4 ? ? ? ?
2 - 4 x 2 ? ? ?
3 - - 2 x 3 ? ?
4 - - - 3 x 6 ?
5 - - - - 6 x 5

The aptly named dimension table will be used to keep track of the dimensions of the resultant matrix.

Game Time!

Matrix Dimensions
M1 3 x 4
M2 4 x 2
M3 2 x 3
M4 3 x 6
M5 6 x 5

Looks like everything is set. Looks like we’re ready for the problem. Suppose we want to multiply the matrices M1 × M2 × M3 × M4 × M5. What is the optimal factorization (technical term for order of multiplying matrices) for this problem? Let’s do this!

Round 1

Cost Table

× 1 2 3 4 5
1 0 ? ? ? ?
2 - 0 ? ? ?
3 - - 0 ? ?
4 - - - 0 ?
5 - - - - 0

Dimensions Table

× 1 2 3 4 5
1 3 x 4 ? ? ? ?
2 - 4 x 2 ? ? ?
3 - - 2 x 3 ? ?
4 - - - 3 x 6 ?
5 - - - - 6 x 5

First, we start by keeping track of all the possible combinations of multiplying 2 matrices. Remember, we are not allowed to switch the order of the matrices, so there are only 4 combinations.

Cell Combination Calculation Resulting Dimension
Z1,2 M1 × M2 342 = 24 3 x 2
Z2,3 M2 × M3 423 = 24 4 x 3
Z3,4 M3 × M4 236 = 36 2 x 6
Z4,5 M4 × M5 365 = 90 3 x 5

With that, we’ve completed round one. We update our costs and dimensions tables and we’re ready for round 2.

Round 2

Cost Table

× 1 2 3 4 5
1 0 24 ? ? ?
2 - 0 24 ? ?
3 - - 0 36 ?
4 - - - 0 90
5 - - - - 0

Dimensions Table

× 1 2 3 4 5
1 3 x 4 3 x 2 ? ? ?
2 - 4 x 2 4 x 3 ? ?
3 - - 2 x 3 2 x 6 ?
4 - - - 3 x 6 3 x 5
5 - - - - 6 x 5

From here on out, we will start heavily using our tables. For round 2, we will start looking at cost of multiplying 3 matrices together: Z1,3, Z2,4, and Z3,5.

For Z1,3, we want the min{(M1 × M2) × M3 , M1 × (M2 × M3)}.
We can rewrite that as min{Z1,2 × M3, M1 × Z2,3)}. Now we recognize the values from the table.

An important point is that when we do the calculation of cost of Z1,2 × M3, we have to find the cost of multiplying Z1,2 × M3 and we have to add to that the cost of Z1,2, which is 24.

We have to do this for each of the remaining 2 combinations. We will end up doing 6 subproblems.

Round 2

Cost Table

× 1 2 3 4 5
1 0 24 ? ? ?
2 - 0 24 ? ?
3 - - 0 36 ?
4 - - - 0 90
5 - - - - 0

Dimensions Table

× 1 2 3 4 5
1 3 x 4 3 x 2 ? ? ?
2 - 4 x 2 4 x 3 ? ?
3 - - 2 x 3 2 x 6 ?
4 - - - 3 x 6 3 x 5
5 - - - - 6 x 5

Cell Combination Shorthand Calculation Total Cost Resulting Dimension Winner
Z1,3 (M1 × M2) × M3 Z1,2 × M3 323 = 18 18 + 24 = 42 3 x 3
Z1,3 M1 × (M2 × M3) M1 × Z2,3 343 = 36 36 + 24 = 50 3 x 3
Z2,4 (M2 × M3) × M4 Z2,3 × M4 436 = 72 72 + 24 = 96 4 x 6
Z2,4 M2 × (M3 × M4) M2 × Z3,4 426 = 48 36 + 48 = 84 4 x 6
Z3,5 (M3 × M4) × M5 Z3,4 × M5 265 = 60 36 + 60 = 96 2 x 5
Z3,5 M3 × (M4 × M5) M3 × Z4,5 235 = 30 30 + 90 = 120 2 x 5

With that, we’re finished with round 2. We just update our cost and dimension tables with the values with the check marks, and we’re ready for round 3.

Round 3

Cost Table

× 1 2 3 4 5
1 0 24 42 ? ?
2 - 0 24 84 ?
3 - - 0 36 96
4 - - - 0 90
5 - - - - 0

Dimensions Table

× 1 2 3 4 5
1 3 x 4 3 x 2 3 x 3 ? ?
2 - 4 x 2 4 x 3 4 x 6 ?
3 - - 2 x 3 2 x 6 2 x 5
4 - - - 3 x 6 3 x 5
5 - - - - 6 x 5

For round 3, we’re finding all the possible ways to multiply 4 matrices without changing their order. Our goal is to fill in Z1,4 and Z2,5. Let’s start with Z1,4.

Z1,4 = min{ M1 × Z2,4, Z1,2 × Z3,4, Z1,3 × M4}

Cell Combination Calculation Total Cost Resulting Dimension Winner
Z1,4 M1 × Z2,4 346 = 72 72 + 84 = 156 3 x 6
Z1,4 Z1,2 × Z3,4 326 = 36 24 + 36 + 36 = 96 3 x 6
Z1,4 Z1,3 × M4 336 = 54 42 + 54 = 96 3 x 6

Notice that two of the solutions have the same cost. This means that either ordering is equally optimal way to factorize multiplication for Z1,4.

Round 3 Part 2

Cost Table

× 1 2 3 4 5
1 0 24 42 96 ?
2 - 0 24 84 ?
3 - - 0 36 96
4 - - - 0 90
5 - - - - 0

Dimensions Table

× 1 2 3 4 5
1 3 x 4 3 x 2 3 x 3 3 x 6 ?
2 - 4 x 2 4 x 3 4 x 6 ?
3 - - 2 x 3 2 x 6 2 x 5
4 - - - 3 x 6 3 x 5
5 - - - - 6 x 5

Now we’re doing Z2,5.

Z2,5 = min{ M2 × Z3,5, Z2,3 × Z4,5, Z2,4 × M5}

Cell Combination Calculation Total Cost Resulting Dimension Winner
Z2,5 M2 × Z3,5 425 = 40 40 + 96 = 136 4 x 5
Z2,5 Z2,3 × Z4,5 435 = 60 60 + 24 + 90 = 174 4 x 5
Z2,5 Z2,4 × M5 465 = 120 84 + 120 = 204 4 x 5

With that, we’re done with round 3. Time for the last round!

Final Round!

Cost Table

× 1 2 3 4 5
1 0 24 42 96 ?
2 - 0 24 84 136
3 - - 0 36 96
4 - - - 0 90
5 - - - - 0

Dimensions Table

× 1 2 3 4 5
1 3 x 4 3 x 2 3 x 3 3 x 6 ?
2 - 4 x 2 4 x 3 4 x 6 4 x 5
3 - - 2 x 3 2 x 6 2 x 5
4 - - - 3 x 6 3 x 5
5 - - - - 6 x 5

As with any good final boss battle, this one will have the most parts.

Z1,5 = min{ M1 × Z2,5, Z1,2 × Z3,5, Z1,3 × Z4,5, Z1,4 × M5}

Cell Combination Calculation Total Cost Resulting Dimension Winner
Z1,5 M1 × Z2,5 245 = 60 60 + 136 = 196 3 x 5
Z1,5 Z1,2 × Z3,5 325 = 30 30 + 24 + 96 = 150 3 x 5
Z1,5 Z1,3 × Z4,5 335 = 45 45 + 42 + 90 = 177 3 x 5
Z1,5 Z1,4 × M5 365 = 90 96 + 90 = 186 3 x 5

So we found that the best factorization for this problm is Z1,2 × Z3,5 and the total cost is 150.

Final Credits

Cost Table

× 1 2 3 4 5
1 0 24 42 96 150
2 - 0 24 84 136
3 - - 0 36 96
4 - - - 0 90
5 - - - - 0

Dimensions Table

× 1 2 3 4 5
1 3 x 4 3 x 2 3 x 3 3 x 6 3 x 5
2 - 4 x 2 4 x 3 4 x 6 4 x 5
3 - - 2 x 3 2 x 6 2 x 5
4 - - - 3 x 6 3 x 5
5 - - - - 6 x 5

So we found that the best factorization for this problm is Z1,2 × Z3,5 and the total cost is 150.
Recall from round 1 that Z1,2 is M1 × M2.
Also recall from round 2 that Z3,5 is (M3 × M4) × M5.
So the best factorization of these matrices is (M1 × M2) × ((M3 × M4) × M5). And with that, we’re done! Thanks for reading!

Motivation

The purpose of this post is to show a fully worked out example of Chain Matrix Multiplication using dynamic programming, a fancy term for breaking a big problem down into subproblems which are easier to solve. (Note: Not the technical definition)

There are multiple sources online with great proofs, source code, and explanation of the proofs, but I did not find an example problem that I felt was easy to understand and follow. I hope that the proofs become much easier to understand after seeing this problem worked out.

You may be wondering “What is my motivation for doing this problem using Dynamic Programming when I could just as easily multiply the matrices in order and be done with it?”. Well, suppose that the matrices are really big; as in, each matrix was a couple of hundred columns and rows. Ordinary matrix multiplication is an Θ(n3) operation, so it will take many operations. It just so happens that the order in which you multiply matrices makes a huge difference in the number of calculations you have to do. That’s why we look for the optimal order (technical term is factorization) of multiplication.

Preliminaries

Notation

  • The symbol ‘×’ will be used to signify multiplying two matrices together.
  • The symbol ’’ will be used to signify multiplying two integers together.
  • Za,b will be used to signify the cost of multiplying all the matrices from Matrix a to Matrix b together in the optimal order.

Preliminaries 2

Prerequisite Math Facts

  • Ap x q × Bq x r will take pqr operations, where A is a matrix with p rows and q columns and B is a matrix with q rows and r columns.
  • Matrix multiplication is associative, so A × (B × C) == (A × B) × C.
  • Multiplying Ap x q × Bq x r will yield the matrix C p x r.
  • For matrices A and B, A × B B × A

Preliminaries 3

Cost Table

× 1 2 3 4 5
1 0 ? ? ? ?
2 - 0 ? ? ?
3 - - 0 ? ?
4 - - - 0 ?
5 - - - - 0

We will use this table to keep track of the cost of multiplying matrices. Notice that the diagonals are all 0; it’s because we won’t be multiplying a matrix by itself. The boxes with hyphens will be ignored because matrix multiplication works from left to right, not the other way around. Element Za,b in the table will be the cost of multiplying all the matrices between a and b. Getting the top right corner box will give us our final answer.

Preliminaries 4

Dimensions Table

× 1 2 3 4 5
1 3 x 4 ? ? ? ?
2 - 4 x 2 ? ? ?
3 - - 2 x 3 ? ?
4 - - - 3 x 6 ?
5 - - - - 6 x 5

The aptly named dimension table will be used to keep track of the dimensions of the resultant matrix.

Game Time!

Matrix Dimensions
M1 3 x 4
M2 4 x 2
M3 2 x 3
M4 3 x 6
M5 6 x 5

Looks like everything is set. Looks like we’re ready for the problem. Suppose we want to multiply the matrices M1 × M2 × M3 × M4 × M5. What is the optimal factorization (technical term for order of multiplying matrices) for this problem? Let’s do this!

Round 1

Cost Table

× 1 2 3 4 5
1 0 ? ? ? ?
2 - 0 ? ? ?
3 - - 0 ? ?
4 - - - 0 ?
5 - - - - 0

Dimensions Table

× 1 2 3 4 5
1 3 x 4 ? ? ? ?
2 - 4 x 2 ? ? ?
3 - - 2 x 3 ? ?
4 - - - 3 x 6 ?
5 - - - - 6 x 5

First, we start by keeping track of all the possible combinations of multiplying 2 matrices. Remember, we are not allowed to switch the order of the matrices, so there are only 4 combinations.

Cell Combination Calculation Resulting Dimension
Z1,2 M1 × M2 342 = 24 3 x 2
Z2,3 M2 × M3 423 = 24 4 x 3
Z3,4 M3 × M4 236 = 36 2 x 6
Z4,5 M4 × M5 365 = 90 3 x 5

With that, we’ve completed round one. We update our costs and dimensions tables and we’re ready for round 2.

Round 2

Cost Table

× 1 2 3 4 5
1 0 24 ? ? ?
2 - 0 24 ? ?
3 - - 0 36 ?
4 - - - 0 90
5 - - - - 0

Dimensions Table

× 1 2 3 4 5
1 3 x 4 3 x 2 ? ? ?
2 - 4 x 2 4 x 3 ? ?
3 - - 2 x 3 2 x 6 ?
4 - - - 3 x 6 3 x 5
5 - - - - 6 x 5

From here on out, we will start heavily using our tables. For round 2, we will start looking at cost of multiplying 3 matrices together: Z1,3, Z2,4, and Z3,5.

For Z1,3, we want the min{(M1 × M2) × M3 , M1 × (M2 × M3)}.
We can rewrite that as min{Z1,2 × M3, M1 × Z2,3)}. Now we recognize the values from the table.

An important point is that when we do the calculation of cost of Z1,2 × M3, we have to find the cost of multiplying Z1,2 × M3 and we have to add to that the cost of Z1,2, which is 24.

We have to do this for each of the remaining 2 combinations. We will end up doing 6 subproblems.

Round 2

Cost Table

× 1 2 3 4 5
1 0 24 ? ? ?
2 - 0 24 ? ?
3 - - 0 36 ?
4 - - - 0 90
5 - - - - 0

Dimensions Table

× 1 2 3 4 5
1 3 x 4 3 x 2 ? ? ?
2 - 4 x 2 4 x 3 ? ?
3 - - 2 x 3 2 x 6 ?
4 - - - 3 x 6 3 x 5
5 - - - - 6 x 5

Cell Combination Shorthand Calculation Total Cost Resulting Dimension Winner
Z1,3 (M1 × M2) × M3 Z1,2 × M3 323 = 18 18 + 24 = 42 3 x 3
Z1,3 M1 × (M2 × M3) M1 × Z2,3 343 = 36 36 + 24 = 50 3 x 3
Z2,4 (M2 × M3) × M4 Z2,3 × M4 436 = 72 72 + 24 = 96 4 x 6
Z2,4 M2 × (M3 × M4) M2 × Z3,4 426 = 48 36 + 48 = 84 4 x 6
Z3,5 (M3 × M4) × M5 Z3,4 × M5 265 = 60 36 + 60 = 96 2 x 5
Z3,5 M3 × (M4 × M5) M3 × Z4,5 235 = 30 30 + 90 = 120 2 x 5

With that, we’re finished with round 2. We just update our cost and dimension tables with the values with the check marks, and we’re ready for round 3.

Round 3

Cost Table

× 1 2 3 4 5
1 0 24 42 ? ?
2 - 0 24 84 ?
3 - - 0 36 96
4 - - - 0 90
5 - - - - 0

Dimensions Table

× 1 2 3 4 5
1 3 x 4 3 x 2 3 x 3 ? ?
2 - 4 x 2 4 x 3 4 x 6 ?
3 - - 2 x 3 2 x 6 2 x 5
4 - - - 3 x 6 3 x 5
5 - - - - 6 x 5

For round 3, we’re finding all the possible ways to multiply 4 matrices without changing their order. Our goal is to fill in Z1,4 and Z2,5. Let’s start with Z1,4.

Z1,4 = min{ M1 × Z2,4, Z1,2 × Z3,4, Z1,3 × M4}

Cell Combination Calculation Total Cost Resulting Dimension Winner
Z1,4 M1 × Z2,4 346 = 72 72 + 84 = 156 3 x 6
Z1,4 Z1,2 × Z3,4 326 = 36 24 + 36 + 36 = 96 3 x 6
Z1,4 Z1,3 × M4 336 = 54 42 + 54 = 96 3 x 6

Notice that two of the solutions have the same cost. This means that either ordering is equally optimal way to factorize multiplication for Z1,4.

Round 3 Part 2

Cost Table

× 1 2 3 4 5
1 0 24 42 96 ?
2 - 0 24 84 ?
3 - - 0 36 96
4 - - - 0 90
5 - - - - 0

Dimensions Table

× 1 2 3 4 5
1 3 x 4 3 x 2 3 x 3 3 x 6 ?
2 - 4 x 2 4 x 3 4 x 6 ?
3 - - 2 x 3 2 x 6 2 x 5
4 - - - 3 x 6 3 x 5
5 - - - - 6 x 5

Now we’re doing Z2,5.

Z2,5 = min{ M2 × Z3,5, Z2,3 × Z4,5, Z2,4 × M5}

Cell Combination Calculation Total Cost Resulting Dimension Winner
Z2,5 M2 × Z3,5 425 = 40 40 + 96 = 136 4 x 5
Z2,5 Z2,3 × Z4,5 435 = 60 60 + 24 + 90 = 174 4 x 5
Z2,5 Z2,4 × M5 465 = 120 84 + 120 = 204 4 x 5

With that, we’re done with round 3. Time for the last round!

Final Round!

Cost Table

× 1 2 3 4 5
1 0 24 42 96 ?
2 - 0 24 84 136
3 - - 0 36 96
4 - - - 0 90
5 - - - - 0

Dimensions Table

× 1 2 3 4 5
1 3 x 4 3 x 2 3 x 3 3 x 6 ?
2 - 4 x 2 4 x 3 4 x 6 4 x 5
3 - - 2 x 3 2 x 6 2 x 5
4 - - - 3 x 6 3 x 5
5 - - - - 6 x 5

As with any good final boss battle, this one will have the most parts.

Z1,5 = min{ M1 × Z2,5, Z1,2 × Z3,5, Z1,3 × Z4,5, Z1,4 × M5}

Cell Combination Calculation Total Cost Resulting Dimension Winner
Z1,5 M1 × Z2,5 245 = 60 60 + 136 = 196 3 x 5
Z1,5 Z1,2 × Z3,5 325 = 30 30 + 24 + 96 = 150 3 x 5
Z1,5 Z1,3 × Z4,5 335 = 45 45 + 42 + 90 = 177 3 x 5
Z1,5 Z1,4 × M5 365 = 90 96 + 90 = 186 3 x 5

So we found that the best factorization for this problm is Z1,2 × Z3,5 and the total cost is 150.

Final Credits

Cost Table

× 1 2 3 4 5
1 0 24 42 96 150
2 - 0 24 84 136
3 - - 0 36 96
4 - - - 0 90
5 - - - - 0

Dimensions Table

× 1 2 3 4 5
1 3 x 4 3 x 2 3 x 3 3 x 6 3 x 5
2 - 4 x 2 4 x 3 4 x 6 4 x 5
3 - - 2 x 3 2 x 6 2 x 5
4 - - - 3 x 6 3 x 5
5 - - - - 6 x 5

So we found that the best factorization for this problm is Z1,2 × Z3,5 and the total cost is 150.
Recall from round 1 that Z1,2 is M1 × M2.
Also recall from round 2 that Z3,5 is (M3 × M4) × M5.
So the best factorization of these matrices is (M1 × M2) × ((M3 × M4) × M5). And with that, we’re done! Thanks for reading!

Edit 1: Changed the multiplication symbols to more friendly ones. Edit 2: Fixed spelling mistakes….I are really good at English :D

Comments