Matrix Chain Multiplication

By | October 23, 2015

Matrix Chain Multiplication – Dynamic Programming

Matrix Chain Multiplication Problem Statement:

Given an array p[] which represents the chain of matrices such that the ith matrix Ai is of dimension
p[i-1] x p[i].
We need to write a function MatrixChainOrder() that should return the minimum number of multiplications needed to multiply the chain.

The problem is not actually to perform the multiplications, but merely to decide in which order to perform the multiplications.

Givne 4 matrices A1 A2 AA, we need they can be parenthesised as

(A1 (A2 (AA4)))
(A1 ((A2 A)A4))
((A1 A2 )(AA4))
(((A1 A)A)A4)

The order in which we parenthesize the product of matrices affects the number of simple arithmetic operations needed to compute the product, or the efficiency. For example, suppose A1 is a 10 × 100 matrix, A2 is a 100 × 5 matrix, and Ais a 5 × 50 matrix. (To mulitply Ap*q *Aq*r  we need p*q*r number of operations). Then,

(A1A2)A3 = (10×100×5) + (10×5×50) = 5,000 + 2,500 = 7,500 operations
A1(A2A3) = (100×5×50) + (10×100×50) = 25,000 + 50,000 = 75,000 operations.

Thus how we parenthesize plays a very important role.

Matrix Chain Multiplication Examples:

Input: p[] = {30, 35, 15, 5, 10, 20, 25}   
  Output: 15125  
  There are 6 matrices of dimensions 30x35, 35x15, 15x5, 5x10, 10x20, 20x25.
  Let the input 6 matrices be A1, A2, A3 ,A4 ,A5 ,and A6 .  The minimum number of 
  multiplications are obtained by putting parenthesis in following way
  ((A1(A2 A3))((A4 A5) A6) --> 15,125

  Input: p[] = {10, 20, 30, 40, 30} 
  Output: 30000 
  There are 4 matrices of dimensions 10x20, 20x30, 30x40 and 40x30. 
  Let the input 4 matrices be A, B, C and D.  The minimum number of 
  multiplications are obtained by putting parenthesis in following way
  (((AB)C)D) --> 30,000

Matrix Chain Multiplication Solution:

Matrix Chain Multiplication Video Explanation:

To help us keep track of solutions to subproblems, we will use a table, and build the table in a bottom­up manner. For 1 ≤ ij n, let m[i, j] be the minimum number of scalar multiplications needed to compute the Ai..j. The optimum cost can be described by the following recursive formulation.

State of DP:
let m[i, j] be the minimum number of scalar multiplications needed to compute the Ai..j.

Basis: Observe that if i = j then the problem is trivial; the sequence contains only one matrix, and so the cost is 0. (In other words, there is nothing to multiply.) Thus,

m[i, i] = 0 for i = 1, 2, …, n. 

Step: If ij, then we are asking about the product of the subchain Ai..j and we take advantage of the structure of an optimal solution. We assume that the optimal parenthesization splits the product, Ai..j into for each value of k, 1 ≤  k ≤  n − 1 as Ai..k . Ak+1..j.

The optimum time to compute is m[i, k], and the optimum time to compute is m[k + 1, j]. We may assume that these values have been computed previously and stored in our array. Since Ai..k is a matrix, and Ak+1..j is a matrix, the time to multiply them is pi − 1 . pk . pj. This suggests the following recursive rule for computing m[i, j].

Recursion for DP:

Matrix chain recurrence

To keep track of optimal subsolutions, we store the value of k in a table s[i, j]. Recall, k is the place at which we split the product Ai..j to get an optimal parenthesization. That is,

s[i, j] = k such that m[i, j] = m[i, k] + m[k + 1, j] + pi − 1 . pk . pj.

Implementing the Rule

In Dynamic Programming we reuse stored values, in our problem the only tricky part is arranging the order in which to compute the values (so that it is readily available when we need it).
In the process of computing m[i,j] we will need to access values m[i, k] and m[k + 1, j] for each value of k lying between i and j. This suggests that we should organize our computation according to the number of matrices in the subchain. So, lets work on the subchain:

Let L = ji + 1 denote the length of the subchain being multiplied.
The subchains of length 1 (m[i, i]) are trivial. Then we build up by computing the subchains of length 2, 3, …, n. The final answer is m[1, n].

Now set up the loop: Observe that if a subchain of length L starts at position i, then j = i + L − 1. Since, we would like to keep j in bounds, this means we want jn, this, in turn, means that we want i + L − 1 ≤ n, actually what we are saying here is that we want in − L +1. This gives us the closed interval for i. So our loop for i runs from 1 to n − L + 1.

Algorithm:
(It is stated as given in the CLRS book)

Matrix-Chain(array p[1 .. n], int n) {
       Array s[1 .. n − 1, 2 .. n];
       FOR i = 1 TO n DO m[i, i] = 0;          // initialize
       FOR L = 2 TO n DO {                       // L=length of subchain
               FOR i = 1 TO n − L + 1 do {
                      j = i + L − 1;
                      m[i, j] = infinity;
                      FOR k = i TO j − 1 DO {          // check all splits
                           q = m[i, k] + m[k + 1, j] + p[i − 1] p[k] p[j];
                           IF (q < m[i, j]) {
                                  m[i, j] = q; 
                                  s[i, j] = k; 
                           }
                       } 
               } 
         }
        return m[1, n](final cost) and s (splitting markers); 
        }

Example [on page 337 in CLRS]: The m-table computed by MatrixChain procedure for n = 6 matrices A1, A2, A3, A4, A5, A6 and their dimensions 30, 35, 15, 5, 10, 20, 25.

The m-matrix table computed by Chain-Matrix-Order for n=6.

Note that the m-table is rotated so that the main diagonal runs horizontally. Only the main diagonal and upper triangle is used.

The s-table computer by Matrix-Chain-Ordre for n = 6.

Our required parenthesized matrices are ((A1(A2 A3))((A4 A5) A6)

Matrix Chain Multiplication Solution code:

Here is the working code:

#include<bits/stdc++.h>
using namespace std;


/*Matrix Ai has dimension p[i-1] x p[i] for i = 1..n*/
int MatrixChainOrder(int p[], int n)
{
    int m[n][n];
 
    int i, j, k, L, q;
 
    /* m[i,j] = Minimum number of scalar multiplications needed to compute
       the matrix A[i]A[i+1]...A[j] = A[i..j] where dimention of A[i] is
       p[i-1] x p[i] */
 
    /*cost is zero when multiplying one matrix.*/
    for (i = 1; i < n; i++)
        m[i][i] = 0;
 
    /*L is chain length. */
    for (L=2; L<n; L++)   
    {
        for (i=1; i<=n-L+1; i++)
        {
            j = i+L-1;
            m[i][j] = INT_MAX;
            for (k=i; k<=j-1; k++)
            {
                // q = cost/scalar multiplications
                q = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
                if (q < m[i][j])
                    m[i][j] = q;
            }
        }
    }
    return m[1][n-1];
}
 
int main()
{
    int arr[] = {30, 35, 15, 5, 10, 20, 25};
    int size = sizeof(arr)/sizeof(arr[0]);
 
    cout<<"Minimum number of multiplications is:\n";
   cout<<MatrixChainOrder(arr, size);
    return 0;
}

Output:

Minimum number of multiplications is:
15125

Time Complexity: O(N3)
Auxiliary Space: O(N2)