## 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).

## Sowmya Ravidas 3:46 pm

onOctober 12, 2012 Permalink |Very useful stuff. Thanks 🙂