Associated Topics || Dr. Math Home || Search Dr. Math

### Minimum Matrix Multiplication

```Date: 02/16/2003 at 02:05:07
Subject: Matrices

Find a way to multiply n matrices using a minimum number of
multiplications of the entities.

E.g., if A1 is a matrix with order 30*20, A2 is a matrix of order
20*40, and A3 is a matrix with order 40*10, there are two ways of
multiplying them: A1(A2*A3) and (A1*A2)A3.

Multiplying the first way involves fewer multiplications then the
second way.

Similarly, what if we had n number of matrices and we wanted to
find out the minimum number of multiplications?
```

```
Date: 02/16/2003 at 08:38:39
From: Doctor Jacques
Subject: Re: Matrices

There is no general, ready-to-use, formula for finding the best
order. What we have is an algorithm, i.e. a procedure to solve the
problem.

I'll describe a procedure to minimize the number of multiplications;
it is easy to modify it to count additions as well, but, in that
case, you must assign a "cost" to each operation, to be able to trade

We know that to multiply 2 matrices of sizes m*n and n*p, we need
(mnp) multiplications.

We could try all the possible combinations, but the number of such
combinations grows quite rapidly, and this would be very inefficient
(at least for a large number of matrices).

The idea is to build a table that gives the number of operations
needed to compute all sets of k consecutives matrices in an optimal
way, for k = 2, 3, ... Saving the results in a table allows us to
reuse them without the need to compute them again.

Let us assume that we want to compute the product ABCD, where the
matrices have the following dimensions:

A : 3 * 2
B : 2 * 5
C : 5 * 4
D : 4 * 2

It may prove convenient to write that down in the form:

3   2   5   4   2
A   B   C   D

because this allows us to find quickly the size of any intermediate
product (for example, ABC is 3*4)

We build a 3 by 3 table. The rows are labelled A, B, C, and the
columns B, C, D. The (i,j) entry in the table contains the cost of
computing the product of the matrices from i to j. For example, row B,
column D contains the optimal cost of computing the product BCD. We
also store the corresponding order (in this case, B(CD) or (BC)D), to
be able to construct the final order.

We start by computing the costs of multiplying pairs of adjacent
matrices:

AB -> 3*2*5 = 30
BC -> 2*5*4 = 40
CD -> 5*4*2 = 40

We store these results in the table, along with the order of
operations (in this case, there is only one order, but it is better
to work systematically, specially if you want to write a computer
program to do the job).

B       C      D
------------------------
A  30
(AB)
------------------------

B         40
(BC)
------------------------
C                 40
(CD)

We now proceed to compute the cost of multiplying sets of three
consecutive matrices. In each case, there are two possibilities for
the last product; we compute these costs and keep the lower.

For example, to compute ABC, the last operation could be either
A*(BC) or (AB)*C.

For the first case, A*(BC), A is 3*2 and BC is 2*4, so the last
product is 3*2*4 = 24. We must add to that the cost of the product BC.
The important thing is that that cost has already been computed - we
just read it in the table (in this case, it's 40).

We have thus 2 possibilities for ABC:

A*(BC) -> 3*2*4 + (BC) = 24 + 40 = 64
(AB)*C -> 3*5*4 + (AB) = 60 + 30 = 90

The best choice is A*(BC); we record it in the table in row A, column
C, with the corresponding order (which we also read from the table,
although in this case there is only one choice)

In a similar way, we find, for BCD:

B*(CD) -> 2*5*2 + (CD) = 20 + 40 = 60
(BC)*D -> 2*4*2 + (BC) = 16 + 40 = 56

and the best choice is (BC)*D.

Our table becomes:

B       C      D
------------------------
A  30     64
(AB)   A(BC)
------------------------

B         40      56
(BC)    (BC)D
------------------------
C                 40
(CD)

We now turn to the product ABCD. There are 3 possibilities for the
final operation: A*(BCD), (AB)*(CD), (ABC)*D.

To compute the cost of A*(BCD), we note that A is 3*2 and (BCD) is
2*2, therefore the final product costs 3*2*2 = 12 operations. We must
add to that the cost of computing the factors : A alone is free, and
we find that (BCD) costs 56 in our table (this is where the savings
come from : if we tried all possibilities, we would recompute the
cost of (BCD) several times).

The costs of the three possibilities are:

A*(BCD)   -> 3*2*2 + (BCD) = 12 + 56 = 68
(AB)*(CD) -> 3*5*2 + (AB) + (CD) = 30 + 30 + 40 = 100
(ABC)*D   -> 3*4*2 + (ABC) = 24 + 64 = 88

The best choice is the first one; we store it in the table with the
corresponding order. Note that the order of the intermediate
operations (in this case, the BCD product) can be simply copied from
the table - that's the reason why we wrote it.

Our table becomes:

B       C      D
------------------------
A  30     64      68
(AB)   A(BC)  A((BC)D)
------------------------

B         40      56
(BC)    (BC)D
------------------------
C                 40
(CD)

This is the final result: the order is A((BC)D), and the cost is 68
multiplications.

In this simple case, the savings with respect to the exhaustive
approach are not very significant, but the difference grows rapidly
when we have more matrices to multiply.

This technique is used in many optimisation problems, it is called
"dynamic programming."

The basic idea is to start form the end of the process, compute the
costs for the various ways of executing the last step, and going
backward while reusing results previously computed.

Please feel free to write again if you want to discuss this further.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Linear Algebra
High School Linear Algebra

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search