Data Structures and Algorithms

Matrix Chain Multiplication

Problem
We are given a sequence of matrices to multiply:
A_{1}
A_{2}
A_{3}
...
A_{n}
Matrix multiplication is associative, so
A_{1} ( A_{2} A_{3} ) =
( A_{1} A_{2} ) A_{3}
that is, we can can generate the product in two ways.
The cost of multiplying an
nxm
by an
mxp
one is O(nmp) (or
O(n^{3}) for two
nxn
ones).
A poor choice of parenthesisation can be expensive:
eg if we have
Matrix  Rows  Columns 
A_{1}  10  100 
A_{2}  100  5 
A_{3}  5  50 
the cost for
( A_{1} A_{2} ) A_{3} is
A_{1}A_{2}  10x100x5  = 5000 
=> A_{1} A_{2} (10x5) 
(A_{1}A_{2}) A_{3}  10x5x50  = 2500 
=> A_{1}A_{2}A_{3} (10x50) 
Total   7500  
but for
A_{1} ( A_{2} A_{3} )
A_{2}A_{3}  100x5x50  = 25000 
=> A_{2}A_{3} (100x5) 
A_{1}(A_{2}A_{3})  10x100x50  = 50000 
=> A_{1}A_{2}A_{3} (10x50) 
Total   75000  
Clearly demonstrating the benefit of calculating the optimum order
before commencing the product calculation!
Optimal Substructure
As with the optimal binary search tree, we can observe that
if we divide a chain of matrices to be multiplied into two optimal
subchains:
(A_{1}
A_{2}
A_{3}
...
A_{j})
(A_{j+1}
...
A_{n}
)
then the optimal parenthesisations of the subchains must be
composed of optimal chains.
If they were not, then we could replace them with cheaper parenthesisations.
This property, known as optimal substructure
is a hallmark of dynamic algorithms:
it enables us to solve the small problems (the substructure) and use those
solutions to generate solutions to larger problems.
For matrix chain multiplication, the procedure is now almost identical to
that used for constructing an optimal binary search tree.
We gradually fill in two matrices,
 one containing the costs of multiplying all the subchains.
The diagonal below the main diagonal contains the costs of all
pairwise multiplications:
cost[1,2] contains the cost of generating product
A_{1}A_{2}, etc.
The diagonal below that contains the costs of triple products:
eg cost[1,3] contains the cost of generating product
A_{1}A_{2}A_{3}, which we derived
from comparing cost[1,2] and cost[2,3], etc.
 one containing the index of last array in the left parenthesisation
(similar to the root of the optimal subtree in the optimal binary
search tree, but there's no root here  the chain is divided into
left and right subproducts), so that
best[1,3] might contain 2 to indicate that the
left subchain contains
A_{1}A_{2} and the right one is
A_{3} in the optimal parenthesisation of
A_{1}A_{2}A_{3}.
As before, if we have n matrices to multiply,
it will take O(n) time to generate each of the
O(n^{2}) costs and entries in the
best matrix for an overall complexity of
O(n^{3}) time
at a cost of
O(n^{2}) space.
Animation
Matrix Chain Multiplication Animation
This animation was written by Woi Ang. 

Please email comments to:
morris@ee.uwa.edu.au

Key terms 
 optimal substructure
 a property of optimisation problems in which the subproblems
which constitute the solution to the problem itself are themselves
optimal solutions to those subproblems.
This property permits the construction of dynamic algorithms to
solve the problem.

© John Morris, 1998