Home > Applied Algorithms, Dynamic Programming > Minimizing multiplications in Chain Matrix Multiplications

Minimizing multiplications in Chain Matrix Multiplications

Be patient and read every line. You’ll end up understanding a great problem of Dynamic Programming.

Problem Statement: Parenthesize a Matrix Chain multiplication matrix in such a way that the number of multiplications required are minimized.

First things first, how many multiplications are involved in multiplying 2 matrices?

If your 1st matrix is of dimensions mxn and your second matrix is of dimensions nxq, you will need to perform mxnxq multiplications in this matrix multiplication.

So if your matrix multiplication chain is as follows,

A x B x C x D , we have the following scenarios,

A = 50 x 20

B = 20 x 1

C = 1 x 10

D = 10 x 100

So you see how we minimized the cost of multiplications there. Now we want to develop an algorithm for the same. You can check all possibilities but as you will realize that you will have very high complexity with such a Brute Force method.

As we discussed a parenthesis problem in my previous post, your mind should jump to find an optimal substructure here. Now you can see all these parenthesizations as a binary tree with these matrices as the leaves and the root element being the final product of all matrices. For example, you can view ((AxB)xC)xD) as,

Hopefully you understood everything till here. Now for a tree to be optimal, its subtrees should also be optimal. So here we come across our optimal substructure. Hence, subproblems are of the form,

(That is the representation of any one node in some binary tree except for the leaf nodes)

Thus we define this sub-problem as,

C ( i, j ) = minimum cost of multiplying  

Size of this subproblem = j-i

Hence, minimum possible size is when i=j (single matrix), so C ( i, i) = 0

For j>i, we consider optimal subtree for C ( i, j ). Now, we can divide this from Ai to Ak and Ak to Aj for some k>i and k<j. The cost of the subtree is then the cost of these two partial products plus the cost of combining these. So we land with the recurrence,

C (i, j) = min { C(i, k) + C(k+1, j) + m(i-1) x mk x mj }

where i<=k<=j.

Coding this is pretty simple now and I need not (and should not) spoonfeed it to you. All you need to do is generate this 2D matrix and another one which holds details about parenthesizations and you’ll end up with your answer. 🙂

PS: If someone requires the code, sorry won’t give you that. If you need the algorithm, drop a comment or a mail. That I can write down.

 

 

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

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

%d bloggers like this: