Summary: In this tutorial, we will learn what the Matrix Chain Multiplication problem is and how to solve Matrix Chain Multiplication using Dynamic Programming in Java.

What is Matrix Chain Multiplication?

Given a sequence of matrices, the goal is to find the most efficient way to multiply these matrices. The problem is not actually to perform the multiplications, but merely to decide the sequence of the matrix multiplications involved.

Wikipedia

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

Let’s 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.

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

In the case of more than two matrices, the total number of multiplication depends on the sequence of multiplication. E.g. see the diagram below.

Matrix Chain Multiplication

Therefore, we need to find a sequence of multiplication of matrices which results into minimum number of multiplication.

Matrix Chain Multiplication Solution using Dynamic Programming

Matrix chain multiplication problem can be easily solved using dynamic programming because it is an optimization problem, where we need to find the most efficient sequence of multiplying the 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 the matrix chain problem with ‘n‘ matrices can be solved in 2nCn/(n+1) ways.

Using dynamic programming the process can be made easy and more efficient.

For example, consider the following sequences for a set of matrices.

matrix chain multiplication dynamic programming

Notice that multiplication of matrix A with matrix B i.e. (A.B) is being repeated in two sequences.

If we could reuse the previous multiplication result of A.B in the next sequence, our algorithm will become faster.

For this, we have to store the solution of subproblems like this into a 2D array i.e. memoize, so that we can use it later easily.

The following picture illustrate the solution for the matrix chain multiplication using dynamic programming :

matrix chain multiplication dynamic programming 2
matrix chain multiplication dynamic programming 3
matrix chain multiplication dynamic programming 4

Here the matrix index represents the multiplication sequence of a set of matrixes and the corresponding value holds the required minimum multiplications.

Example: (1,3) represent the multiplication of sequence from A2 to A4 i.e. A2xA3xA4

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

Let’s implement the same in program code.

Matrix Chain Multiplication in Java

Output:

matrix chain multiplication solution

In this tutorial, we learned what the Matrix chain multiplication problem is and how to solve matrix chain multiplication problem using dynamic programming.

This Post Has One Comment

  1. Joe Petricone

    This actually answered my downside, thank you!

Leave a Reply to Joe Petricone Cancel reply