Make delicious recipes!

Optimum order for matrix chain multiplications


Given an array of matrices such that matrix at any index can be multiplied by the matrix at the next contiguous index, find the best order to multiply them such that number of computations is minimum.

Note: To multiply 2 contiguous matrices of size PxQ and QxM, computations required are PxQxM

Example:
3x2
A B
D E
G H
2x1
P
Q
3x1
AP+BQ
DP+EQ
GP+HQ
3x2
A B
D E
G H
2x2
P R
Q S
3x2
AP+BQ AR+BS
DP+EQ DR+ES
GP+HQ GR+HS


Example of correct order: Consider the multiplication of matrices with following dimensions: 4x3 3x2 2x5
They can be multiplied in two ways:
(AB)C A(BC)
  = ((4x3 3x2) 2x5)
  = (4x2 2x5), multiplications = 4x3x2 = 24
  = 4x5, multiplications = 24 + 4x2x5 = 64
  = (4x3 (3x2 2x5))
  = (4x3 3x5), multiplications = 3x2x5 = 30
  = 4x5, multiplications = 30 + 4x3x5 = 90



Solution: Let each matrix be represented by a letter and let the matrix array be ABCD.

Let result of multiplying matrices P and Q be shown as (PQ)

Then we can choose to multiply matrices in many ways, some of which are as follows:

  1. (((AB)C)D)
  2. (A((BC)D))
  3. ((AB)(CD))
  4. ...

Whatever be the order of multiplication, the last two matrices to multiply will be contiguous.
And the solution to the problem lies in finding that pair which will be multiplied last.


Basically, the idea is that any two contiguous matrices can be multiplied.

To consider all the possible cases, we need to do the following:

1) Multiply 2 matrices at indices k and k+1

2) Multiply matrices from 0 to k-1 in best possible manner

3) Multiply matrices from k+1 to N in best possible manner

4) Multiply all 3 matrices obtained in 3 steps above.

5) Store the number of computations.

6) Vary k from 0 to N-1 and choose the combination which yields minimum computations.


Let us specify an array mtrxSizes[] whose every 2 contiguous indices will be used to specify a matrix of size matrxSizes[k] x mtrxSizes[k+1]

Thus to specify N matrices, mtrxSizes has to be of size N+1




The above is a recursive solution and since it does not use any DP, many subproblems are calculated repeatedly.


Dynamic Programming Solution


int minCalcsForMatrices(int p[], int n)
{
    // 0th row and 0th column of lookup[][] are not used.
    int lookup[n][n];
 
    // No cost if there is only one matrix
    for (int i = 1; i < n; i++)
        lookup[i][i] = 0;
 
    // find solution for increasing group-size of matrices
    for (int chainLen=2; chainLen<n; chainLen++)
    {
        for (int i=1; i<=n-chainLen+1; i++) // set i as starting of group
        {
            int j = i+chainLen-1;  // set j as ending of group
            lookup[i][j] = Integer.MAX_VALUE;
            for (int k=i; k<=j-1; k++) // vary k from i to j
            {
                int cost = lookup[i][k] + lookup[k+1][j] + p[i-1]*p[k]*p[j];
                if (int cost < lookup[i][j])
                    lookup[i][j] = int cost;
            }
        }
    }
 
    return lookup[1][n-1];
}

In terms of loops, note how similar this problem is to:
  1. Max ways for boolean expression to be true
  2. Longest palindrome creation
All of these problems have an outer loop which starts with 1 or 2 elements and then gradually widens the scope of the problem being solved.






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal