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

Learn Me Something

Learn Me Something was a hackathon project that was submitted for the 2012 Rails Rumble hackathon. The idea came to me at 4:30 am on October 7, when I was thinking about how I had to tutor a student on limits. I immediately turned on my laptop, and opened up a Google Doc to write down my thoughts. Here was the elevator speech that I thought up for it.

Education on the web has a huge disconnect today. On one end, there are people with questions that need answering, and a lack of quality content to satisfy their needs. On the other end are aspiring content creators with vast pools of knowledge, but no idea where to start. Learn Me Something smashes these two groups of people together. Now people can request full lessons about certain topics and subjects, and content creators can find their audience.

How are we different from StackOverflow, RailsCasts, or Quora?
Learn Me Something differs from StackOverflow in that it encourages answerers to create their own fleshed-out content rather than providing quick answers to questions. Our users’ responses will be focused on original content for video tutorials or blog posts. StackOverflow is more about bug fixes of specific portions of code. We’re more about providing more complete lessons on subjects rather than just specific answers to specific questions.

Railscasts, Khan Academy, or even Code Academy are great services, but they are run individuals or startups who only have the capability of releasing a limited amount of content at any time. We let our users decide what kinds of tutorials they want, and judge the quality of the responses to their questions. Learn Me Something will also cater to a wide range of topics that are not just tech related. We want to be the one stop source for FAQs, tutorials, and open source education. Bloggers and tutorial video makers will know what topics are in great demand, and they will also have an idea of who and where their audience is.

I started thinking about what my strengths were as a developer and who among my friends would complement my skills. I am primarily good with backend development and so I would need help with front end. My friends, Dan Mundy, a great front end developer, Russ Frank, a super skilled systems and mobile developer, and Mike Swift, full-stack developer and all around boss, liked the idea.

The competition started on Friday, October 12th at 8pm for us; officially it started October 13th at 12am UTC so. We did not actually begin development until the next morning, when the team was able to get together. So we had about 36 hours to get it together. We were also attending HackRU, a hackathon hosted by Rutgers, because Swift is a developer evangelist for Sendgrid, so both he and Russ Frank were super busy mentoring Rutgers hackers. How they managed to still do a ton of work for us is a testament to their abilities.

So here is a run through of how to use LearnMeSomthin right now.

1) This is what you see on the homepage. Search asked questions bar will give you a list of questions and requests already in the system. From there you can click on a question to view its responses. For right now, because its a bit buggy, its best to sign up.

2) A Signup page. We will eventually have a email confirmation module running.

3) Once logged in, you can really get going. You can check out questions. The Pending questions bar on the side is the questions that you asked, but do not have any responses yet.

4) If the question that you wanted does not exist, just create one of your own. For now, users have to tag their questions with their own discretion. We will make it smarter in the future with autocomplete and suggestions.

5) Once you created a question, you can view it. Once answered, you will see the responses.

6) A successful thread. The goal is to eventually have a community driven tutorial site. There are so many tutorials on the internet and we want to be the place that gathers them. There are millions of tutorials for commonly studied subjects like Calculus, but what if you needed a lesson on finding closed form sums for hypergeometric series. This would be the place to ask.

We are very excited about this project and we will definitely flesh it out. We are well aware of the flaws of the site as it is, but bear in mind that we cranked it out in less than 36 hours. Please visit Learnmesometh.in frequently.