Data Structures and Algorithms
Matrix Chain Multiplication

Problem

We are given a sequence of matrices to multiply:
A1 A2 A3 ... An
Matrix multiplication is associative, so
A1 ( A2 A3 ) = ( A1 A2 ) A3
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(n3) for two nxn ones). A poor choice of parenthesisation can be expensive: eg if we have

MatrixRowsColumns
A110100
A21005
A3550
the cost for ( A1 A2 ) A3 is
A1A2 10x100x5= 5000 => A1 A2 (10x5)
(A1A2) A3 10x5x50= 2500 => A1A2A3 (10x50)
Total   7500 
but for A1 ( A2 A3 )
A2A3 100x5x50= 25000 => A2A3 (100x5)
A1(A2A3) 10x100x50= 50000 => A1A2A3 (10x50)
Total   75000 
Clearly demonstrating the benefit of calculating the optimum order before commencing the product calculation!

Optimal Sub-structure

As with the optimal binary search tree, we can observe that if we divide a chain of matrices to be multiplied into two optimal sub-chains:
(A1 A2 A3 ... Aj) (Aj+1 ... An )
then the optimal parenthesisations of the sub-chains must be composed of optimal chains. If they were not, then we could replace them with cheaper parenthesisations.

This property, known as optimal sub-structure is a hallmark of dynamic algorithms: it enables us to solve the small problems (the sub-structure) 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,

As before, if we have n matrices to multiply, it will take O(n) time to generate each of the O(n2) costs and entries in the best matrix for an overall complexity of O(n3) time at a cost of O(n2) 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 sub-structure
a property of optimisation problems in which the sub-problems which constitute the solution to the problem itself are themselves optimal solutions to those sub-problems. This property permits the construction of dynamic algorithms to solve the problem.

Continue on to Longest Common Subsequence Back to the Table of Contents
©
John Morris, 1998