What is Matrix Chain Multiplication Problem?

In Matrix Chain Multiplication Problem we are given a number of matrices and is asked to multiply in such a way that the total number of multiplication should be minimum.

Lets breakdown the problem.

Two matrices can only be multiplied if the number of columns of the first matrix is equal to the number of rows of the second one and vice-versa may not be true.

Matrix multiplication

And the number of multiplications required to multiply two matrices is the product of their order.

Number of multiplication in multiplying two matrices

When we have to multiply more than two matrices then the total number of multiplication depends on their sequence of multiplication. E.g see the diagram below.

Matrix Chain Multiplication

Therefore, we need to find a sequence of multiplication of matrices so that the total number of multiplication is minimum.

Matrix Chain Multiplication using Dynamic Programming

Matrix chain multiplication problem can be easily solved using dynamic programming because it is an optimization problem in which we need to find the most efficient way of multiplying the given sequence of matrices.

Recommended: If you don’t know what is dynamic programming?

There is no doubt that we have to examine every possible sequence or parenthesization. Therefore for matrix chain problem having ‘n‘ matrices can be solved in 2nCn/(n+1) ways.

But by using dynamic programming the process can be made easy and fast.

Examine some possible sequence of matrices multiplication given below. You will notice that certain multiplication is getting repeated again and again.

matrix chain multiplication dynamic programming

Notice that multiplication of matrix A with matrix B i.e (A.B) is being repeated in two sequences. Thus reusing its precalculated solution is will be a better choice to make our algorithm faster. Therefore we need to store the solution of subproblems like this into a 2D array i.e memoize, so that we can use it later easily.

So let’s solve it manually.

matrix chain multiplication dynamic programming 2

matrix chain multiplication dynamic programming 3

matrix chain multiplication dynamic programming 4

In the calculation of the next bigger sequence, we are using the values of previous multiplications stored in the 2D array.

Let’s do the same in program code.

Matrix Chain Multiplication in Java

Output

matrix chain multiplication solution

That’s all we need to do know to solve matrix chain multiplication algorithm. If you have any doubt then comment below.

This Post Has One Comment

  1. This actually answered my downside, thank you!

Leave a Reply

Close Menu