Minimum Matrix Multiplication

Date: 02/16/2003 at 02:05:07
From: Ezad Atta
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

Hi Ezad,

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 
additions against multiplications.

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/