Matrix Chain Multiplication

Matrix Chain Multiplication
• Given some matrices to multiply, determine the best order

to multiply them so you minimize the number of single
element multiplications.
– i.e. Determine the way the matrices are parenthesized.
• First off, it should be noted that matrix multiplication is

associative, but not commutative. But since it is associative,
we always have:
• ((AB)(CD)) = (A(B(CD))), or any other grouping as long as the

matrices are in the same consecutive order.
• BUT NOT: ((AB)(CD)) = ((BA)(DC))

• It may appear that the amount of work done won’t
change if you change the parenthesization of the
expression, but we can prove that is not the case!
• Let us use the following example:

– Let A be a 2x10 matrix
– Let B be a 10x50 matrix
– Let C be a 50x20 matrix
• But FIRST, let’s review some matrix multiplication

rules…
• Let’s get back to our example: We will show that the way we
group matrices when multiplying A, B, C matters:
– Let A be a 2x10 matrix
– Let B be a 10x50 matrix
– Let C be a 50x20 matrix
• Consider computing A(BC):

– # multiplications for (BC) = 10x50x20 = 10000, creating a 10x20
answer matrix
– # multiplications for A(BC) = 2x10x20 = 400
– Total multiplications = 10000 + 400 = 10400.
• Consider computing (AB)C:

– # multiplications for (AB) = 2x10x50 = 1000, creating a 2x50 answer
matrix
– # multiplications for (AB)C = 2x50x20 = 2000,
– Total multiplications = 1000 + 2000 = 3000
• Thus, our goal today is:
• Given a chain of matrices to multiply,
determine the fewest number of
multiplications necessary to compute the
product.
• Formal Definition of the problem:
– Let A = A1 A2 ... An
– Let Mi,j denote the minimal number of
multiplications necessary to find the product:
• Ai Ai+1 ... Aj.
– And let pi-1xpi denote the dimensions of matrix Ai.
• We must attempt to determine the minimal

number of multiplications necessary(m1,n) to find
A,
– assuming that we simply do each single matrix
multiplication in the standard method.
• The key to solving this problem is noticing the
sub-problem optimality condition:
– If a particular parenthesization of the whole product
is optimal, then any sub-parenthesization in that
product is optimal as well.
• Say What?
– If (A (B ((CD) (EF)) ) ) is optimal
– Then (B ((CD) (EF)) ) is optimal as well
– Proof on the next slide…
• Assume that we are calculating ABCDEF and that
the following parenthesization is optimal:
• (A (B ((CD) (EF)) ) )
– Then it is necessarily the case that
• (B ((CD) (EF)) )
– is the optimal parenthesization of BCDEF.
• Why is this?
– Because if it wasn't, and say ( ((BC) (DE)) F) was
better, then it would also follow that
• (A ( ((BC) (DE)) F) ) was better than
• (A (B ((CD) (EF)) ) ),
• Our final multiplication will ALWAYS be of the form
– (A1 A2 ... Ak)  (Ak+1 Ak+2 ... An)
• In essence, there is exactly one value of k for which we should

"split" our work into two separate cases so that we get an optimal
result.
– Here is a list of the cases to choose from:
– (A1)  (A2 A3 ... An)
– (A1 A2)  (A3 A4 ... An)
– (A1 A2A3)  (A4 A5 ... An)
– ...
– (A1 A2 ... An-2)  (An-1 An)
– (A1 A2 ... An-1)  (An)
• Basically, count the number of multiplications in each of these

choices and pick the minimum.
– One other point to notice is that you have to account for the
minimum number of multiplications in each of the two products.
• Consider the case multiplying these 4 matrices:
– A: 2x4
– B: 4x2
– C: 2x3
– D: 3x1
• 1. (A)(BCD) - This is a 2x4 multiplied by a 4x1,

– so 2x4x1 = 8 multiplications, plus whatever work it will take to
multiply (BCD).
• 2. (AB)(CD) - This is a 2x2 multiplied by a 2x1,

multiply (AB) and (CD).
• 3. (ABC)(D) - This is a 2x3 multiplied by a 3x1,

multiply (ABC).
• Our recursive formula:
– Mi,j = min value of Mi,k + Mk+1,j + pi-1pkpj, over all valid
values of k.
• Now let’s turn this recursive formula into a dynamic

programming solution
– Which sub-problems are necessary to solve first?
– Clearly it's necessary to solve the smaller problems

before the larger ones.
• In particular, we need to know mi,i+1, the number of
multiplications to multiply any adjacent pair of matrices
before we move onto larger tasks.
• Similarly, the next task we want to solve is finding all the
values of the form mi,i+2, then mi,i+3, etc.
•Basically, we’re checking different places to “split” our

matrices by checking different values of k and seeing if they
improve our current minimum value.

Matrix Chain Multiplication

Uploaded by

Copyright:

Available Formats

Matrix Chain Multiplication

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Matrix Chain Multiplication

Uploaded by

Copyright:

Available Formats

Matrix Chain Multiplication

• Given some matrices to multiply, determine the best order

• First off, it should be noted that matrix multiplication is

• ((AB)(CD)) = (A(B(CD))), or any other grouping as long as the

• BUT NOT: ((AB)(CD)) = ((BA)(DC))

• Let us use the following example:

• But FIRST, let’s review some matrix multiplication

• Consider computing A(BC):

• Consider computing (AB)C:

• We must attempt to determine the minimal

• In essence, there is exactly one value of k for which we should

• Basically, count the number of multiplications in each of these

• 1. (A)(BCD) - This is a 2x4 multiplied by a 4x1,

• 2. (AB)(CD) - This is a 2x2 multiplied by a 2x1,

• 3. (ABC)(D) - This is a 2x3 multiplied by a 3x1,

• Now let’s turn this recursive formula into a dynamic

– Clearly it's necessary to solve the smaller problems

•Basically, we’re checking different places to “split” our

You might also like