Matrix chain multiplication

An algorithm to find the optimal paranthesization of n matrices.

1. Matrix -Chain Multiplication
Dr.Kiran K
Assistant Professor
Department of CSE
UVCE
Bengaluru, India.

2. Introduction
ProblemStatement:
Givenachainofnmatrices<A
1,A
2,...,A
n>,
A
ihasdimensionp
i-1xp
i,(i=1,2,...,n)
FullyParenthesizetheproductA
1A
2...A
ninawaythatMinimizesthenumberof
ScalarMultiplications.
FullyParenthesize:
AproductofmatricesisFullyParenthesizedifitiseither
•ASingleMatrixor
•ProductofTwoFullyParenthesizedMatrixProducts,surroundedby
parentheses.

3. Eg.:
TheproductA1A2A3A4ofthematrices<A1,A2,A3,A4>,canbeFully
ParenthesizedinFivedistinctways:
•(A1(A2(A3A4)))
•(A1((A2A3) A4))
•((A1A2)(A3A4))
•((A1(A2A3))A4)
•(((A1A2)A3)A4)
Introduction…

4. MATRIX-MULTIPLY (A, B)
If (A.columnsB.rows)
Error “Incompatible Dimensions”
Else
Let Cbe a new A.rowsx B.columnsMatrix
For (i= 1 to A.rows)
For (j= 1 to B.columns)
c
ij= 0
For (k= 1 to A.columns)
c
ij= c
ij+a
ik. b
kj
return C
Order of A: ix k
Order of B: kx j
Order of C: ix j
Number of Scalar Multiplications:
kmultiplicationsforeachofthe
(i*j)entriesofC.
=i*k*j
=ikj
Multiplication of Two Matrices

5. Eg.:
<A1, A2, A3>
A1 - 10 x 100
A2 - 100 x 5
A3 - 5 x 50
Cost of Matrix Multiplication
((A1A2) A3)
A1A2-10 * 100 * 5 = 5000
((A1A2) A3) –10 * 5 * 50 = 2500
Total 5000 + 2500
= 7500 Scalar Multipliations
(A1 (A2A3))
A2A3–100 * 5 * 50 = 25000
(A1(A2A3) –10 * 100 * 50 = 50000
Total 25000 + 50000
= 75000 Scalar Multiplications
Parenthesizinga chain of matrices can have a dramatic impact on the cost of product
evaluation.

6. Goal:
To determine an
Order for Multiplying Matrices
that has the
Lowest Cost

7. LetP(n)-NumberofAlternativeParenthesizationsofasequenceofnmatrices.
•n=1,Onlyonematrix:
•Onlyonewaytofullyparenthesizethematrixproduct.
•n>=2:
•AFullyParenthesizedmatrixproductistheProductofTwoFully
ParenthesizedMatrixSubproducts.
•Splitbetweenthetwosubproductsmayoccurbetweenthek
th
and(k+1)
st
matricesforanyk=1,2,...,n-1.
Counting the Number of Parenthesizations

8. Dynamic-programmingmethodisusedtodeterminehowtooptimallyparenthesize
amatrixchain:
1. Characterize the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution.
4. Construct an optimal solution from computed information
Optimal Parenthesizationof Matrix-Chain

9. •A
i...j:MatrixthatresultsfromevaluatingtheproductA
iA
i+1...A
j.ij.
•If(i<j)
ParenthesizeA
iA
i+1...A
jbysplittingtheproductbetweenA
kandA
k+1
forik<j.
→ComputematricesA
i...kandA
k+1...jandthenmultiplythemtogetherto
producethefinalproductA
i...j.
•CostofParenthesizing=CostofComputingA
i...k+CostofComputingA
k+1...j
+CostofMultiplyingthemtogether.
1. Structure of an Optimal Parenthesization

10. •Costofanoptimalsolutionisdefinedrecursivelyintermsofoptimalsolutionsto
sub-problems.
•Sub-problems:Problemsofdeterminingtheminimumcostofparenthesizing
A
iA
i+1...A
jfor1ijn.
•m[i,j]:MinimumnumberofscalarmultiplicationstocomputematrixA
i...
j
if(i=j)
ThereisonlyonematrixA
i...i=A
1
m[i,j]=0
If(i<j)
m[i,j]=CostofComputingA
i...k+CostofComputingA
k+1...j+
CostofMultiplyingthemtogether.
m[i,j]=m[i,k]+m[k+1,j]+p
i–1p
kp
j
2. A Recursive solution

11. kvariesfromitoj–1.Hence,
•s[i,j]:ValueofkatwhichtheSplitisanOptimalParenthesization.
A Recursive Solution…

12. •p
i –1x p
i - Dimensionof matrix A
i. i= 1, 2, . . . , n
•p= <p
0 , p
1 , . . . p
n> - List of Matrix Dimensions.
•m[1 . . n, 1 . . n] - Table storing the Costsm[i, j]
•s[1..n-1,2..n] - TablestoringtheIndexofkthatachieved
optimalcostincomputingm[i,j].
Usedtoconstructanoptimalsolution.
•m[1,n] - LowestcosttocomputeA
1..n
3. Computing the Optimal Costs

13. MATRIX-CHAIN-ORDER (p)
n= p.length-1
let m[1 . . n, 1 . . n] and s[1 . . n-1, 2 . . n] be new tables
For (i= 1 to n)
m[i, i] = 0
For (l= 2 to n)
For (i= 1 to n-l+ 1)
j= i+ l–1
m[i, j] = 
For (k= ito j–1)
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 mand s
Computing the Optimal Costs…
Running Time : O (n
3
)
Space to store Tables mand s: O (n
2
)

14. Example
n=6
p
i=30,35,15,5,10,20,25
Tablem:
•Order:nxn
•i-rowsandj-columns
•Onlythelowerhalfofthe
tableupto(i,i)getsfilled
because1ijn
Matrix A1 A2 A3 A4 A5 A6
Dimension30 x 3535 x 1515 x 55 x 1010 x 2020 x 25
123456
10
2 0
3 0
4 0
5 0
6 0
Ifno.ofmatrices=1,No.ofwaysto
parenthesize=0.i.e.,m(i,i)=0
m[1,1]=0,m[2,2]=0,m[3,3]=0
m[4,4]=0,m[5,5]=0,m[6,6]=0
j
i
Table m

15. Example…
•l=2→2Matrices
•Matrices:A
1A
2,A
2A
3,A
3A
4,A
4A
5,A
5A
6
•No.ofpositionswheresplitcanoccur=1.Therefore,k=1,2,3,4,5
respectively.
•Numberofdifferentparenthesizations:
A
1A
2:m[1,2]=m[1,1]+m[2,2]+p
0p
1p
2=0+0+30x35x15=15,750
s[1,2]=1
A
2A
3:m[2,3]=m[2,2]+m[3,3]+p
1p
2p
3=0+0+35x15x05=2,625
s[2,3]=2
A
3A
4:m[3,4]=m[3,3]+m[4,4]+p
2p
3p
4=0+0+15x05x10=750
s[2,3]=3
A
4A
5:m[4,5]=m[4,4]+m[5,5]+p
3p
4p
5=0+0+30x35x15=1,000
s[1,2]=4
A
5A
6:m[5,6]=m[5,5]+m[6,6]+p
4p
5p
6=0+0+10x20x25=5,000
s[1,2]=5

16. Example…
n =6; p
i= 30, 35, 15, 5, 10, 20, 25; l= 2i= 1 to n-l+ 1; j= i+ l–1; k= ito j–1
q= m[i, k] + m[k+ 1, j] + p
i-1 p
k p
j
i= 1
j= 1+2-1 = 2
i= 2
j= 2+2-1 = 3
i= 3
j= 3+2-1 = 4
k= 1
q= m[1,1] + m[2,2] + p
0 p
1 p
2
= 0 + 0 + 30 x 35 x 15 = 15,750
k= 2
q= m [2,2] + m [3,3] + p
1 p
2 p
3
= 0 + 0 + 35 x 15 x 5 = 2,625
k= 3
q= m [3,3] + m [4,4] + p
2 p
3 p
4
= 0 + 0 + 15 x 5 x 10 = 750
m[1, 2] = 15,750
s[1, 2] = 1
m[2, 3] = 2,625
s[2, 3] = 2
m[3, 4] = 750
s[3, 4] = 3
i= 4
j= 4+2-1 = 5
i= 5
j= 5+2-1 = 6
k= 4
q= m[4,4] + m[5,5] + p
3 p
4 p
5
= 0 + 0 + 30 x 35 x 15 = 1,000
k= 5
q= m[5,5] + m[6,6] + p
4 p
5 p
6
= 0 + 0 + 10 x 20 x 25 = 5,000
m[4, 5] = 1,000
s[4, 5] = 4
m[5, 6] = 5,000
s[5, 6] = 5

17. Example…
1 2 3 4 5 6
1 015,750
2 0 2,625
3 0 750
4 0 1,000
5 0 5,000
6 0
j
i
Table m 123456
1 1
2 2
3 3
4 4
5 5
Table s
j
i

18. Example…
•l=3→3Matrices
•Matrices:A
1A
2A
3,A
2A
3A
4,A
3A
4A
5,A
4A
5A
6
•No.ofpositionswheresplitcanoccur=2.
Therefore,k=(1,2),(2,3)(3,4),(4,5)respectively.
•Numberofdifferentparenthesizations:
A
1A
2A
3:
m[1,1]+m[2,3]+p
0p
1p
3=0+2625+30x35x05=7,875
m[1,2]+m[3,3]+p
0p
2p
3=15750+0+30x15x05=18,000
s[1,3]=1
A
2A
3A
4:
m[2,2]+m[3,4]+p
1p
2p
4=0+750+30x15x10=6,000
m[2,3]+m[4,4]+p
1p
3p
4=2625+0+35x05x10=4,375
s[2,4]=3
m[1, 3] = min
=4,375m[2, 4] = min
=7,875

19. Example…
A
3A
4A
5:
m[3,3]+m[4,5]+p
2p
3p
5=0+1000+15x05x20=2,500
m[3,4]+m[5,5]+p
2p
4p
5=750+0+15x10x20=3,750
s[3,5]=3
A
4A
5A
6:
m[4,4]+m[5,6]+p
3p
4p
6=0+5000+05x10x25=6,250
m[4,5]+m[6,6]+p
3p
5p
6=1000+0+05x20x25=3,500
s[4,6]=5
m[3, 5] = min
=3,500m[4, 6] = min
=2,500

20. Example…
n =6; p
i= 30, 35, 15, 5, 10, 20, 25; l= 3i= 1 to n-l+ 1; j= i+ l–1; k= ito j–1
q= m[i, k] + m[k+ 1, j] + p
i-1 p
k p
j
i= 1
j= 1+3-1 = 3
i= 2
j= 2+3-1 = 4
k= 1
q=m[1,1]+m[2,3]+ p
0 p
1 p
3
=0+2625+30x35x5
q= 7,875
k= 2
q=m[1,2]+m[3,3]+ p
0 p
2 p
3
=15750+0+30x15x5
q= 18,000
k= 2
q=m[2,2]+m[3,4]+ p
1 p
2 p
4
=0+750+35x15x10
q= 6,000
k= 3
q=m[2,3]+m[4,4]+ p
1 p
3 p
4
=2625+0+35x5x10
q= 4,375
m[1, 3] = min (7875, 18000) = 7,875
s[1, 3] = 1
m[2, 4] = min (6000, 4375) = 4,375
s[2,4] = 3
i= 3
j= 3+3-1 = 5
i= 4
j= 4+3-1 = 6
k= 3
q=m[3,3]+m[4,5]+ p
2 p
3 p
5
=0+1000+15x5x20
q= 2,500
k= 4
q=m[3,4]+m[5,5]+ p
2 p
4 p
5
=750+0+15x10x20
q= 3,750
k= 4
q=m[4,4]+m[5,6]+ p
3 p
4 p
6
=0+5000+5x10x25
q= 6,250
k= 5
q=m[4,5]+m[6,6]+ p
3 p
5 p
6
=1000+0+5x20x25
q= 3,500
m[3, 5] = min (2500, 3750) = 2,500
s[3, 5] = 3
m[4, 6] = min (6250, 3500) = 3,500
s[4, 6] = 5

21. Example…
1 2 3 4 5 6
1 015,7507,875
2 0 2,6254,375
3 0 7502,500
4 0 1,0003,500
5 0 5,000
6 0
j
i
Table m 123456
1 11
2 23
3 33
4 45
5 5
Table s
j
i

22. Example…
•l=4→4Matrices
•Matrices:A
1A
2A
3A
4,A
2A
3A
4A
5,A
3A
4A
5A
6
•No.ofpositionswheresplitcanoccur=3.
Therefore,k=(1,2,3),(2,3,4)(3,4,5)respectively.
•Numberofdifferentparenthesizations:
A
1A
2A
3A
4:
m[1,1]+m[2,4]+p
0p
1p
4=0+4375+30x35x10=14,875
m[1,4]=minm[1,2]+m[3,4]+p
0p
2p
4=15750+750+30x15x10=21,000=9,375
m[1,3]+m[4,4]+p
0p
3p
4=7875+0+30x5x10=9,375
s[1,4]=1

23. Example…
A
2A
3A
4A
5:
m[2,2]+m[3,5]+p
1p
2p
5=0+2500+35x15x20=13,000
m[2,5]=minm[2,3]+m[4,5]+p
1p
3p
5=2625+1000+35x5x20=7,125=7,125
m[2,4]+m[5,5]+p
1p
4p
5=4375+0+30x10x20=11,375
s[2,5]=3
A
3A
4A
5A
6:
m[3,3]+m[4,6]+p
2p
3p
6=0+3500+15x5x25=5,375
m[3,6]=minm[3,4]+m[5,6]+p
2p
4p
6=750+3500+15x10x25=8,000=5,375
m[3,5]+m[6,6]+p
2p
5p
6=2500+0+15x20x25=10,000
s[3,6]=3

24. Example…
n =6; p
i= 30, 35, 15, 5, 10, 20, 25; l= 4i= 1 to n-l+ 1; j= i+ l–1; k= ito j–1
q= m[i, k] + m[k+ 1, j] + p
i-1 p
k p
j
i= 1; j= 1+4-1 = 4
k= 1
q=m[1,1]+m[2,4]+ p
0 p
1 p
4
=0+4375+30x35x10 =14,875
k= 2
q=m[1,2]+m[3,4]+ p
0 p
2 p
4
=15750+750+30x15x10 =21,000
k= 3
q=m[1,3]+m[4,4]+ p
0 p
3 p
4
=7875+0+30x5x10 =9,375
m[1, 4] = min (14875, 21000, 9375) = 9,375; s[1, 4] = 3
i= 2; j= 2+4-1 = 5
k= 2
q=m[2,2]+m[3,5]+ p
1 p
2 p
5
=0+2500+35x15x20 =13,000
k= 3
q=m[2,3]+m[4,5]+ p
1 p
3 p
5
=2625+1000+35x5x20 =7,125
k= 4
q=m[2,4]+m[5,5]+ p
1 p
4 p
5
=4375+0+35x10x20 =11,375
m[2, 5] = min (13000, 7125, 11375) = 7,125; s[2, 5] = 3
i= 3; j= 3+4-1 = 6
k= 3
q=m[3,3]+m[4,6]+ p
2 p
3 p
6
=0+3500+15x5x25 =5,375
k= 4
q=m[3,4]+m[5,6]+ p
2 p
4 p
6
=750+3500+15x10x25 =8,000
k= 5
q=m[3,5]+m[6,6]+ p
2 p
5 p
6
=2500+0+15x20x25 =10,000
m[3, 6] = min (5375, 8000, 10000) = 5,375; s[3, 6] = 3

25. Example…
1 2 3 4 5 6
1 015,7507,8759,375
2 0 2,6254,3757,125
3 0 7502,5005,375
4 0 1,0003,500
5 0 5,000
6 0
j
i
Table m 123456
1 113
2 233
3 333
4 45
5 5
Table s
j
i

26. Example…
•l=5→5Matrices
•Matrices:A
1A
2A
3A
4A
5,A
2A
3A
4A
5A
6
•No.ofpositionswheresplitcanoccur=4.
Therefore,k=(1,2,3,4),(2,3,4,5)respectively.
•Numberofdifferentparenthesizations:
A
1A
2A
3A
4A
5:
m[1,1]+m[2,5]+p
0p
1p
5=0+7175+30x35x20=28,125
m[1,2]+m[3,5]+p
0p
2p
5=15750+2500+30x15x20=27,250
m[1,3]+m[4,5]+p
0p
3p
5=7875+1000+30x5x20=11,875
m[1,4]+m[5,5]+p
0p
4p
5=9375+0+35x10x20=16,375
s[1,5]=3
A
2A
3A
4A
5A
6:
m[2,2]+m[3,6]+p
1p
2p
6=0+5375+35x15x25=18,500
m[2,3]+m[4,6]+p
2p
3p
6=2625+3500+15x5x25=8,000
m[2,4]+m[5,6]+p
1p
4p
6=4375+5000+35x10x25=18,125
m[2,5]+m[6,6]+p
1p
5p
6=7125+0+35x20x25=24,625
s[2,6]=3
m[1, 5] = min = 11,875
m[2, 6] = min
= 8,000

27. Example…
n =6; p
i= 30, 35, 15, 5, 10, 20, 25; l= 5i= 1 to n-l+ 1; j= i+ l–1; k= ito j–1
q= m[i, k] + m[k+ 1, j] + p
i-1 p
k p
j
i= 1
j= 1+5-1 = 5
k= 1
q=m[1,1]+m[2,5]+ p
0 p
1 p
5
=0+7125+30x35x20
q= 28,125
k= 2
q=m[1,2]+m[3,5]+ p
0 p
2 p
5
=15750+2500+30x15x20
q= 27,250
k= 3
q=m[1,3]+m[4,5]+ p
0 p
3 p
5
=7875+1000+30x5x20
q= 11,875
k= 4
q=m[1,4]+m[5,5]+ p
0 p
4 p
5
=9375+0+35x10x20
q= 16,375
m[1, 5] = min (28125, 27250, 11875, 16375) = 11,875
s[1, 5] = 3
i= 2
j= 2+5-1 = 6
k= 2
q=m[2,2]+m[3,6]+ p
1 p
2 p
6
=0+5375+35x15x25
q= 18,500
k= 3
q=m[2,3]+m[4,6]+ p
2 p
3 p
6
=2625+3500+15x5x25
q= 8,000
k= 4
q=m[2,4]+m[5,6]+ p
1 p
4 p
6
=4375+5000+35x10x25
q= 18,125
k= 5
q=m[2,5]+m[6,6]+ p
1 p
5 p
6
=7125+0+35x20x25
q= 24,625
m[2, 6] = min (18500, 8000, 18125, 24625) = 8,000
s[2, 6] = 3

28. Example…
1 2 3 4 5 6
1 015,7507,8759,37511,875
2 0 2,6254,3757,1258,000
3 0 7502,5005,375
4 0 1,0003,500
5 0 5,000
6 0
j
i
Table m 123456
1 1133
2 2333
3 333
4 45
5 5
Table s
j
i

29. Example…
•l=6→6Matrices
•Matrices:A
1A
2A
3A
4A
5A
6
•No.ofpositionswheresplitcanoccur=5.
Therefore,k=(1,2,3,4,5).
•Numberofdifferentparenthesizations:
A
1A
2A
3A
4A
5:
m[1,1]+m[2,6]+p
0p
1p
6=0+8000+30x35x25=34,250
m[1,2]+m[3,6]+p
0p
2p
6=15750+5375+35x15x25=32,375
m[1,6]=minm[1,3]+m[4,6]+p
0p
3p
6=7875+3500+30x5x25=15,125=15,125
m[1,4]+m[5,6]+p
0p
4p
6=9375+5000+35x10x25=21,875
m[1,5]+m[6,6]+p
0p
5p
6=11875+0+35x20x25=26,875
s[1,6]=3

30. Example…
n =6; p
i= 30, 35, 15, 5, 10, 20, 25; l= 6i= 1 to n-l+ 1; j= i+ l–1; k= ito j–1
q= m[i, k] + m[k+ 1, j] + p
i-1 p
k p
j
i= 1
j= 1+6-1 = 6
k= 1
q= m[1,1] + m[2,6] + p
0 p
1 p
6
= 0+8000+30x35x25= 34,250
k= 2
q= m [1,2] + m [3,6] + p
0 p
2 p
6
=15750+5375+30x15x25= 32,375
k= 3
q= m [1,3] + m [4,6] + p
0 p
3 p
6
=7875+3500+30x5x25= 15,125
k= 4
q= m[1,4] + m[5,6] + p
0 p
4 p
6
=9375+5000+30x10x25= 21,875
k= 5
q= m[1,5] + m[6,6] + p
0 p
5 p
6
=11875+0+30x20x25 = 26,875
m[1, 6] = min (34250, 34250, 15125, 21875, 26875) = 15125
s[1, 6] = 3

31. Example…
1 2 3 4 5 6
1 015,7507,8759,37511,87515125
2 0 2,6254,3757,1258,000
3 0 7502,5005,375
4 0 1,0003,500
5 0 5,000
6 0
j
i
Table m 123456
1 11333
2 2333
3 333
4 45
5 5
Table s
j
i
TheMinimumnumberofScalar
Multiplicationstomultiplythe6
matricesA
1A
2A
3A
4A
5A
6is:
m[1,6]=15,125.
TheOptimalsplitoccursat:
s[1,6]=3.

32. •Optimal way of computing A
1. . n is: A
1. .
S [1, n]xA
S [1, n]+ 1. .
n
•TheinitialcallPRINT-OPTIMAL-PARENS(s,1,n)printsanoptimal
parenthesizationofA
1,A
2,...,A
n
PRINT-OPTIMAL-PARENS (s,i, j)
If (i== j)
Print “A”
i
Else Print “(”
PRINT-OPTIMAL-PARENS (s, i, s [i,j])
PRINT-OPTIMAL-PARENS (s, s [i, j] + 1, j)
Print “)”
4. Constructing an Optimal Solution
PRINT-OPTIMAL-PARENS(s,1,6)
printstheParenthesization:
((A1(A2 A3)) ((A4 A5) A6))

33. PRINT-OPTIMAL-PARENS (s, 1, 6) Push (i= 1, j= 6)
(
PRINT-OPTIMAL-PARENS (s, 1, 3) Push (i= 1, j= 3)
((
PRINT-OPTIMAL-PARENS (s, 1, 1) Push (i= 1, j= 1)
((A1 Pop (i= 1, j= 1)
PRINT-OPTIMAL-PARENS (s, 2,3) Push (i= 2, j= 3)
((A1(
PRINT-OPTIMAL-PARENS (s, 2,2) Push (i= 2, j= 2)
((A1(A2 Pop (i= 2, j= 2)
PRINT-OPTIMAL-PARENS (s, 3,3) Push (i= 3, j= 3)
((A1(A2A3 Pop (i= 3, j= 3)
((A1(A2A3) Pop (i= 2, j= 3)
Constructing an Optimal Solution…

34. ((A1(A2A3)) Pop (i= 1, j= 3)
PRINT-OPTIMAL-PARENS (s, 4, 6) Push (i= 4, j= 6)
((A1(A2A3))(
PRINT-OPTIMAL-PARENS (s, 4, 5) Push (i= 4, j= 5)
((A1(A2A3))((
PRINT-OPTIMAL-PARENS (s, 4, 4) Push (i= 4, j= 4)
((A1(A2A3))((A4 Pop (i= 4, j= 4)
PRINT-OPTIMAL-PARENS (s, 5, 5) Push (i= 5, j= 5)
((A1(A2A3))((A4A5 Pop (i= 5, j= 5)
((A1(A2A3))((A4A5) Pop (i= 4, j= 5)
PRINT-OPTIMAL-PARENS (s, 6, 6) Push (i= 6, j= 6)
((A1(A2A3))((A4A5)A6 Push (i= 6, j= 6)
((A1(A2A3))((A4A5)A6) Pop (i= 4, j= 6)
((A1(A2A3))((A4A5)A6)) Pop (i= 1, j= 6)
Optimal Parenthesization: ((A1(A2A3))((A4A5)A6))
Constructing an Optimal Solution…

35. References:
•ThomasHCormen.CharlesELeiserson,RonaldLRivest,CliffordStein,
IntroductiontoAlgorithms,ThirdEdition,TheMITPressCambridge,
MassachusettsLondon,England.