Dynamic Programming : Matrix chain multiplication

Matrix chain multiplication using dynamic programming

Problem here is, we are given N matrices. Dimensions of each matrix given in an array P where P[i-1] and P[i] denote rows and column respectively of ith matrix. We need to find an order in which these matrices are multiplied, so that total number of scalar multiplications are least. Matrix chain multiplication is a typical problem which is used to explain dynamic programming. Approach learnt here can be easily applied to many other problems.

Before going further, lets understand some points about matrix multiplication
  1. Matrix multiplication is associative i.e.  A* (B*C) = (A*B) *C
  2. It is not commutative i.e  A * (B*C) not equal to A * (C * B)
  3. To multiply two matrices, they should be compatible i.e. no of columns in first matrix should be equal to number of rows of second matrix.
Let’s get back to problem.  Easy way to understand the problem is to say we need to figure out a way to put parenthesis around matrices so that total number of multiplication are least.

Brute force way of doing this to find out every possible combination of parenthesis and check which one is minimum. 
This algorithm is exponential in time and hence of no use for every large input.

Let’s see if dynamic programming fit in.

We can see that cost of multiplying matrices Ai to Aj  is cost of (Ai to Ak) + (Ak+1 to Aj )+ 
(P[i] * P[k-1] * P[j]).
Idea is to find out K such that later expression becomes minimum. M[i,j] represents the cost to multiply matrix i to matrix j

M[i,j]  = M[i,k] + M[K+1,j] + ((P[i] * P[k-1] * P[j]) )

So when we are calculating M[i,j] we should already have M[i,k] and M[k+1,j].  
We also know that M[i,i] = 0 as multiplying a single matrix will be 0.

Looking at the requirement to calculate M[i,j], we can say that it depends on the length of the chain.
Length of chain from matrix i to matrix j would be i+j-1.

We start with length 2 and go on to solve the table entry for length N. M[1, N] will give us the final cost. Since we need to start at every position for every length,
then i + L -1 = j. Also, j<=N; hence i <= N-L+1.

Code for multiplication of matrix problem

Complexity analysis

Time complexity of matrix chain multiplication using dynamic programming is O(N*N). Also space complexity is O(N*N).

Reference

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s