Matrix Chain Multiplication

 Algorithm of Matrix Chain Multiplication 

Given a sequence of matrices, find the most efficient way to multiply  these matrices together. The problem is not actually to perform the  multiplications, but merely to decide in which order to perform the  multiplications. 

We have many options to multiply a chain of matrices because matrix  multiplication is associative. In other words, no matter how we  parenthesize the product, the result will be the same. For example, if  we had four matrices A, B, C, and D, we would have: 

 (ABC)D = (AB)(CD) = A(BCD) = (A (BC) D) .... 

However, the order in which we parenthesize the product affects the  number of simple arithmetic operations needed to compute the  product, or the efficiency. For example, suppose A is a 10 × 30  matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then, 

 (AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations 

 A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000  operations. 

Clearly the first parenthesization requires less number of operations. ALGORITHM 

MATRIX-CHAIN-ORDER (p) 

1. n length[p]-1 

2. for i ← 1 to n 

3. do m [i, i] ← 0 

4. for l ← 2 to n // l is the chain  length 

5. do for i ← 1 to n-l + 1 

6. do j ← i+ l -1 

7. m[i,j] ← ∞ 

8. for k ← i to j-1 

9. do q ← m [i, k] + m [k + 1, j] + pi-1 pk pj

10. If q < m [i,j] 

11. then m [i,j] ← q 

12. s [i,j] ← k 

13. return m and s.  

Step 1: Constructing an Optimal Solution: 

PRINT-OPTIMAL-PARENS (s, i, j) 

1. if i=j 

2. then print "A" 

3. else print "(" 

4. PRINT-OPTIMAL-PARENS (s, i, s [i, j]) 5. PRINT-OPTIMAL-PARENS (s, s [i, j] + 1, j) 6. print ")" 

Example of Matrix Chain Multiplication 

Example1: We are given the sequence {4, 10, 3, 12, 20,  and 7}. The matrices have size 4 x 10, 10 x 3, 3 x 12, 12 x 20, 20 x 7. We need to compute M [i,j], 0 ≤ i, j≤ 5. We  know M [i, i] = 0 for all i. 

A1 4 x 10, P0=4 

A2 10 x 3 P1= 10 

A3 3 x 12 P2=3 

A4 12 x 20 P3 = 12 

A5 20 x 7 P4 = 20 

 P5 = 7 

do q ← m [i, k] + m [k + 1, j] + pi-1pkpj M[1,2] = { m[1,1]+m[2,2]+p0*p1*p2 k=1

1<=k<2 =4*10*3=120 

  

  

let us proceed with working away from the diagonal. We compute the  optimal solution for the product of 2 matrices. 

Let us proceed with working away from the diagonal. We  compute the optimal solution for the product of 2 matrices. 

Here P0 to P5 are Position and M1 to M5 are matrix of size  (pi to pi-1

On the basis of sequence, we make a formula 

In Dynamic Programming, initialization of every method done by  '0'.So we initialize it by '0'.It will sort out diagonally.

We have to sort out all the combination but the minimum output  combination is taken into consideration. 

Calculation of Product of 2 matrices: 

1. m (1,2) = m1 x m

 = 4 x 10 x 10 x 3 

 = 4 x 10 x 3 = 120 

  

2. m (2, 3) = m2 x m

 = 10 x 3 x 3 x 12 

 = 10 x 3 x 12 = 360 

3. m (3, 4) = m3 x m

 = 3 x 12 x 12 x 20 

 = 3 x 12 x 20 = 720 

4. m (4,5) = m4 x m

 = 12 x 20 x 20 x 7 

 = 12 x 20 x 7 = 1680 

o We initialize the diagonal element with equal i,j value with '0'. 

o After that second diagonal is sorted out and we get all the values corresponded to it Now the third diagonal will be solved out in the same way. 

Now product of 3 matrices: 

M [1, 3] = M1 M2 M

1. There are two cases by which we can solve this multiplication:  2. ( M1 x M2) + M3, M1+ (M2x M3

3. After solving both cases we choose the case in which minimum output is  there. 

q ← m [i, k] + m [k + 1, j] + pi-1pkp

1<=k<3  

M[1,2]= m[1,1]+m[2,2]+p0*p1*p2 

1<=k<2 = 0+0+4*10*3=120 

1<=1<2

M[2,3]=m[2,2]+m[3,3]+p1*p2*p3 

= 10*3*12=360 

K=2 

M[3,4] = m[3,3]+m[4,4]+p2*p3*p4 

K=3 =3*12*20= 720 

M[4,5] =m[4,4]+m[5,5]+p3*p4*p5 

K=4 =12*20*7=1680 

m[1,3] = min {M[1,1]+M[2,3]+P0*P1*P3= 0+360+4*10*12=840 K=1 1<=k<3 M[[1,2]+M[3,3]+P0*P2*P3= 120+4*3*12 =264 K=2 

m[2,4]= min {m[2,2]+m[3,4]+p1*p2*p4 = 720+10*3*20 = 1320 k=2

2<=k<4 m[2,3]+m[4,4]+p1*p3*p4 = 360+10*12*20 = 2760 k=3 

m[ 3,5] = min { m[3,3]+m[4,5]+p2*p3*p5 = 1680+3*12*7= 1932 k=3 3<=k<5 m[3,4]+m[5,5]+p2*p4*p5 = 720+3*20*7= 1140 k=4 

M[2,5] = min {m[2,2]+m[3,5]+p1*p2*p5 = 0+1140+10*3*7 = 1350 k=2

2<=k<5 m[2,3]+m[4,5]+p1*p3*p5 = 360+1680+10*12*7 = 2880 k=3  M[2,4]+m[5,5]+p1*p4*p5 = 1320+10*20*7 = 2720 

M[1,4] = min {m[1,1]+m[2,4]+p0*p1*p4 = 1320+4*10*20=2120 k=1 1<=k<4 M[1,2]+m[3,4]+p0*p2*p4 =120+720+4*3*20=1080 k=2                M[1,3]+m[4,4]+p0*p3*p4 = 264+4*12*20 = 1224 k=3

M[1,5] = min {m[1,1]+m[2,5]+p0*p1*p5 = 1350+4*10*7 =1630 k=1

M[1,2] +m[3,5]+p0*p2*p5= 120+1140+4*3*7 = 1344, k=2 M[1,3]+m[4,5]+p0*p3*p5 =264+1680+4*12*7 =2280 k=3 M[1,4]+m[5,5]+p0*p4*p5 =1080+4*20*7= 1640 k=4

M[i , j] j  ------------------->

1 2 3 4 5 

120 

264 

1080 

1344


360 

1320 

1350 



720 

1140 




1680 








S[ i, j]  

  

2 3 4 5 

2 i 3 












PRINT-OPTIMAL-PARENS (s, i, j)

1. if i=j 

2. then print "A" 

3. else print "(" 

4. PRINT-OPTIMAL-PARENS (s, i, s [i, j]) 5. PRINT-OPTIMAL-PARENS (s, s [i, j] + 1, j) 6. print ")"


(S,1,5) = ((S,1,2)(S,3,5)) 

 =(((S,1,1)(S,2,2) ) ( (S,3,4)(S,5,5))) 

 =((A1,A2)(( (S,3,3)(S,4,4)) A5)) 

 = ((A1,A2)((A3,A4),A5))  




M[1,5] 

M[1,2] m[3,5]  

M[1,1] M[2, 2] m[3, 4] m[5,5] 

 M[3,3] M[4,4]  

A1A2 A5 

A3 A5

= [ [ A1,A2] [ [A3,A4 ] A5] ] 





Example 2 : 

Find an optimal parenthesization of a matrix chain product whose  sequence of dimension is < 5,4,6,2,7 > 

A1 5 x 4, P0=5 

A2 4 x 6 P1= 4 

A3 6 x 2 P2=6 

A4 2 x 7 P3 = 2 

 P4 = 7 

M[i , j] 

1 2 3 4 

120 

88 

158 


48 

104 



84 





do q ← m [i, k] + m [k + 1, j] + pi-1pkpj M[1,2] = { m[1,1]+m[2,2]+p0*p1*p2 k=1 

 = 0+0+5*4*6=120 

M[2,3] =m[2,2]+m[3,3]+p1*p2*p3 

 =48 

M[3,4] = m[3,3]+m[4,4]+p2*p3*p4 

 =84 

M[1,3] =min { m[1,1]+m[2,3]+p0*p1*p3 =48+5*4*2=88 k=1  K=1,2 m[1,2]+[3,3]+p0*p2*p3 = 120+5*6*2=180 k=2 M[2,4] = min { m[2,2]+m[3,4]+p1*p2*p4= 84+4*6*7 = 252 k=2 K=2,3 m[2,3]+m[4,4]+p1*p3*p4 =48+4*2*7=104 k=3 

M[1,4] =min { m[1,1]+m[2,4]+p0*p1*p4= 104+5*4*7=244 k=1 M[1,2]+m[3,4]+p0*p2*p4=294 k=2 

M[1,3]+m[4,4]+p0*p3*p4= 88+5*2*7=158 k=3

S[ i, j]  

2 3 4 






2 i 3 




PRINT-OPTIMAL-PARENS (s, i, j) 

1. if i=j 

2. then print "A" 

3. else print "(" 

4. PRINT-OPTIMAL-PARENS (s, i, s [i, j]) 5. PRINT-OPTIMAL-PARENS (s, s [i, j] + 1, j) 6. print ")"






Example 3: 

Find an optimal parenthesization for multiplication of 5 matrix:- A1 5 x 10, P0=5 

A2 10 x 3 P1= 10 

A3 3 x 12 P2=3 

A4 12 x 5 P3 = 12 

A5 5 x 50 P4 = 5 

P5 = 50 

M[i , j] 

do q ← m [i, k] + m [k + 1, j] + pi-1pkpj M[1,2] = { m[1,1]+m[2,2]+p0*p1*p2 k=1 

1 2 3 4 5 

2 i 






S[ i, j]  





























2 3 4 5

2 i 

  




















PRINT-OPTIMAL-PARENS (s, i, j) 

1. if i=j 

2. then print "A" 

3. else print "(" 

4. PRINT-OPTIMAL-PARENS (s, i, s [i, j]) 5. PRINT-OPTIMAL-PARENS (s, s [i, j] + 1, j) 6. print ")" 

Example 4: 

Find an optimal parenthesization of matrix chain product whose  dimension is 

< 30 x 35, 35 x 15, 15 x 5, 5 x 10, 10 x 20, 20 x 25 >






Comments