Home\ Tutorial \ MCM Version 2.0
 Matrix Chain Multiplication (MCM)

Background

If two matrix A and B whose dimension is (m,n) and (n,p) respectively then the multiplication of A and B needs m*n*p scalar multiplication.

Suppose you are given a sequence of n matrix A1,A2,.....An. Matrix Ai has dimension (Pi-1,Pi). Your task is to parenthesize the product A1,A2,.....An such a way that minimize the number of scalar product.

As matrix multiplication is associative so all the parenthesizations yield the same product.

A brute force approach of finding the optimal sequence is enumerating all sequences and finding the optimum one which takes too much time. However, We have a Dynamic Programming solution for this problem. For details, you are refer to Introduction to Algorithm, By by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest second edition chapter 15 (Dynamic Programming), I will write the algorithm first and then code of this, written in C++, ready to use.

The  algorithm :

MATRIX_CHAIN_ORDER(P)
The input  is a sequrnce P = <P0,P1,P2,.....Pn> where length[P] = n+1. The procedure uses an auxlary table m[1....n,1....n] for storing the m[i,j] costs and auxlary table s[1...n,1...n] that records which index of k achive the optimal cost in computing m[i,j].

1. n <- length[P]-1

2. for i <- 1 to n

3.        do m[i,j] <- 0

4. for l <- 2 to n

5.        do for i <- 1 to n – l + 1

6.                  do j <- i + l – 1

7.                       m[i,j] <- INF     //  INF is infnity

8.                       for k <- i  to j –1

9.                             do q <- m[i,k]+m[k+1,j]+ Pi-1PkPj

10.                                   if q < m[i,j]

11.                                       then m[i,j] <- q

12.                                               s[i,j] <- k

13. return m,s

PRINT(s,i,j)
The following recursive procedure prints an optimal parentathesization of (Ai,Ai+1,.....Aj) given the s table computed by MATRIX_CHAIN_ORDER and indices i and j. The initial call PRINT(s,1,n) prints optimal parentathesization of (A1,A2,.....An).

1. if i == j

2.     then print “A”i

3.     else  print “(“

4.             PRINT(s,i,s[i,j])

5.             PRINT(s,s[i,j]+1,j)

6.             print “)”

Code

/* matrix.cpp

Implementation of general matrix chain multiplication algorithm

Compiled : CYGNU & Microsoft Visual C++ 6.0

Permission is granted for use in non-commerical applications provided this copyrightnotice remains intact and

unchanged.

*/

#include<stdio.h>

#define MAX 15               /* number of matrix */

#define INF 4294967295       /* a maximum number of multiplication */

int num;

/* ************************************************* */

/*     Print out the sequence                        */

/*     Input : A two dimentional array(created       */

/*             by the matrix chan order function)    */

/*             with there starting point             */

/*     Return : None                                 */

/* ************************************************* */

void print(unsigned long s[][MAX],int i,int j)

{

if(i==j)

printf("A%d",num++);

else

{

printf("(");

print(s,i,s[i][j]);

printf(" x ");

print(s,s[i][j]+1,j);

printf(")");

}

}

/* *********************************************** */

/*      Find out the order                         */

/*      Input : A sequence of dimention and the    */

/*              number of matrix                   */

/*      Return : none                              */

/* *********************************************** */

void matrix_chan_order(int *p,int n)

{

unsigned long m[MAX][MAX] = {0};

unsigned long s[MAX][MAX] = {0};

unsigned int q;

int l,j,i,k;

for(l = 2; l <= n ;l++)

{

for(i = 1 ; i <= n - l +1 ; i++)

{

j = i + l -1;

m[i][j] = INF;

for(k=i ; k < j ; k++)

{

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;

}

}

}

}

num =1;

print(s,1,n);

}

/* A sample main function */

main(void)

{

int n;

int p[MAX]={0};

int i;

while(scanf("%d",&n),n)

{

for(i=1;i<=n;i++)

scanf("%d %d",&p[i-1],&p[i]);

matrix_chan_order(p,n);

putchar('\n');

}

return 0;

}

 Related Problems
 ProblemSet Tricks | Reference | Tutorial FAQ|Index|Info Credits|Guestbook|Update