Matrix chain multiplication

Problem
Given a sequence of n matrices M₁, M₂, ... M_n, and their dimensions p₀, p₁, p₂, ..., p_n, where where i = 1, 2, ..., n, matrix M_i has dimension p_{i − 1} × p_i, determine the order of multiplication that minimizes the the number of scalar multiplications.

We wish to determine the value of the product ∏i = 1 to n Mi, where Mi has ri-1 rows and ri columns.

The order of which matrices are multiplied together first can significantly affect the time required.

To multiply M×N, where matrix M is p×q and matrix N is q×r, takes pqr operations if we use the "normal" matrix multiplication algorithm.   Note that the matrices have a common dimension value of q.   This makes the matrices have the property of compatibility, without which it would not be possible for them to be multiplied.   Also note that, while matrix multiplication is associative, matrix multiplication is not commutative.   That is, N×M might not equal M×N and, in fact, N×M might not even be defined because of a lack of compatibility.

Example 1
Compute  A * B * C * D
A = 30 × 1, B =  1 × 40, C =  40 × 10, D =  10 × 25

Multiplication order (A * B) * (C * D) requires
= M1 * M2 = (30 X 40 ) * (40  X 25)
= 30 * 1 * 40 + 40 * 10 * 25 + 30 * 40 * 25
        = 41, 200 multiplications.

Multiplication order A * ((B * C) * D) requires
= A * (M1 * D) = A * M2
1 * 40 * 10 + 1 * 10 * 25 + 30 * 1 * 25 = 1, 400 multiplications.
where M1 = (1 X 10) matrix = B*C = 1 * 40 * 10, M2 = (1 X 25 ) matrix = 1 * 10 * 25
and A*M2 = (30 X 25) = 30*1*25

Example 2

Calculate M = M1 × M2 × M3 × M4,
where the dimensions of the matrices are
M1: 10,20       M2: 20,50       M3: 50,1       M4: 1,100

Calculating M = M1 × ( M2 × ( M3 × M4 ) ) requires 125000 operations.
=M1 * (M2 * (50*1*100)) = M1 * (20 * 50

Calculating M = ( M1 × ( M2 × M3 ) ) × M4 requires 2200 operations.

We could figure out how many operations each possible order will take and then use the one having the minimum number of operations, but there are there are an exponential number of orderings.   Any of the n-1 multiplications could be first and then any of the remaining n-2 multiplications could be next and so on, leading to a total of (n-1)! orderings.

We can find the best order in time O(n^3) by using dynamic programming.

Matrix-Chain-Order(p){
n  = p.length - 1;
for (i from  1 to n)
 m[i, i]  =  0
for (l = 2 to n) // l is the chain length.
 for (i = 1 to n − l + 1){
  j=i + l − 1;
  m[i, j]=1;
  for (k=i to j − 1){
    q=m[i, k] + m[k + 1, j] + p[i-1]*p[k]*p[j]
    if q < m[i, j]){
     then m[i, j]=q
    s[i, j]=k
    }
  }  
 }
 return m and s
 }

In the above listing, length refers to the number of matrix multiplications in a subproblem. An alternative approach would be to use size (equal to length+1) as the number of matrices in the subproblem.

Here is java code:

private void matrixChainOrder(int[] p)
{
 int n = p.length - 1; // how many matrices are in the chain
 int[][] m = new int[n+1][n+1]; // overallocate m, so that we don't use index 0
 int[][] s = new int[n+1][n+1]; 
 
 // Initial the cost for the empty subproblems.
 for (int i = 1; i <= n; i++)
  m[i][i] = 0;

 // Solve for chains of increasing length l.
 for (int l = 2; l <= n; l++) {
  for (int i = 1; i <= n-l+1; i++) {
  int j = i + l - 1;
  m[i][j] = Integer.MAX_VALUE;

  // Check each possible split to see if it's better
  // than all seen so far.
  for (int k = i; k < j; k++) {
   int q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];
   if (q < m[i][j]) {
   // q is the best split for this subproblem so far.
   m[i][j] = q;
   s[i][j] = k;
   }
  }
  }
 }
}

For the example given above, we would calculate:
m1,1 = 0,   m2,2 = 0,   m3,3 = 0,   m4,4 = 0
m1,2 = 10000,   m2,3 = 1000,   m3,4 = 5000
m1,3 = 1200,   m2,4 = 3000
m1,4 = 2200