Matrix Multiplication using Dynamic Programming

It is difficult to solve complex problems in one go. Breaking them into subproblems and them attacking them makes it easier to solve. We combine the solutions of all the subproblems and them arrive at the main solution for the complex problem.
Top down approach with memorization or bottom-down approach are generally used in dynamic programming.
Consider you want to multiply two matrices A (n x m) and B(p x q). Let the cost for doing this be the sum of total operations for doing it which is ‘nm’.
If you have three matrices, A,B,C of 10×30, 30×5, 5×60, then the cost for multiplying the three will be as follows based on the associative rule.

 (AB)C = (10x30x5)+(10x5x60) = 1500 + 3000 = 4500
 A(BC) = (10x30x60)+ (30x5x60) = 18000 + 9000 = 27000

Here the first method is obviously better than the second method as the cost is low there.
Our aim is to find the minimum cost for finding the multiplication of all matrices. Given some matrix, we find all possible ways to represent it and find the cost using recursive calls. Those are the subproblems. But if we do that, we calculate the same task again and again. This repeated calculation lead to increase the time needed and hence less efficient.
In order to avoid this repetition problem, we use a simple solution of memoization. The computation for a subproblem is remembered in some way.
Also the whole problem can be looked in a bottom up approach.
Let us consider for matrices A11,A22,A33,A44. Our aim is to find A14. That means

 A14 = A11 x A22 x A33 x A44

A11 = 50 x 10
A22 = 10 x 40 
A33 = 40 x 30 
A44 = 30 x 5

A12 = 50 x 10 x 40 = 20000
A23 = 10 x 40 x 30 = 12000
A34 = 40 x 30 x 5 = 6000

Now we have to calculate A13.

A13 = min( A11 x A23  ,  A12 x A33)

A11 x A23 = 50 x 10 x 30 + 12000 = 27000

A12 x A33 = 50 x 40 x 30 + 20000 = 80000

So  choose A13  as A11 x A23  as that is the smallest.

Similarly, we can find A14 which is min(A11 x A24, A12 x A34, A13 x A44)

And calculating in the previous way, you get it as A11 x A24

So the final answer is A14 = A11 x (A22 ( A33 x A44) )

If not done with dynamic programming, the time complexity of this problem is exponential which is now reduced to O(n^3).

Advertisements

One thought on “Matrix Multiplication using Dynamic Programming

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s