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 m2
= 4 x 10 x 10 x 3
= 4 x 10 x 3 = 120
2. m (2, 3) = m2 x m3
= 10 x 3 x 3 x 12
= 10 x 3 x 12 = 360
3. m (3, 4) = m3 x m4
= 3 x 12 x 12 x 20
= 3 x 12 x 20 = 720
4. m (4,5) = m4 x m5
= 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 M3
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-1pkpj
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
S[ i, j]
2 3 4 5
1
2 i 3
4
5
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
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
1
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
1
2 i
3
4
5
S[ i, j]
2 3 4 5
1
2 i
3
4
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
Post a Comment