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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.