Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Example-Matrix Multiplication

 

Consider the problem of computing the product of two matrices. That is, given two tex2html_wrap_inline67605 matrices, A and B, compute the tex2html_wrap_inline67605 matrix tex2html_wrap_inline67613, the elements of which are given by

  equation32684

Section gif shows that the direct implementation of Equation gif results in an tex2html_wrap_inline58434 running time. In this section we show that the use of a divide-and-conquer strategy results in a slightly better asymptotic running time.

To implement a divide-and-conquer algorithm we must break the given problem into several subproblems that are similar to the original one. In this instance we view each of the tex2html_wrap_inline67605 matrices as a tex2html_wrap_inline67619 matrix, the elements of which are tex2html_wrap_inline67621 submatrices. Thus, the original matrix multiplication, tex2html_wrap_inline67613 can be written as

displaymath67601

where each tex2html_wrap_inline67625, tex2html_wrap_inline67627, and tex2html_wrap_inline67629 is an tex2html_wrap_inline67621 matrix.

From Equation gif we get that the result submatrices can be computed as follows:

eqnarray32724

Here the symbols + and tex2html_wrap_inline60264 are taken to mean addition and multiplication (respectively) of tex2html_wrap_inline67621 matrices.

In order to compute the original tex2html_wrap_inline67605 matrix multiplication we must compute eight tex2html_wrap_inline67621 matrix products (divide) followed by four tex2html_wrap_inline67621 matrix sums (conquer). Since matrix addition is an tex2html_wrap_inline58122 operation, the total running time for the multiplication operation is given by the recurrence:

  equation32760

Note that Equation gif is an instance of the general recurrence given in Equation gif. In this case, a=8, b=2, and k=2. We can obtain the solution directly from Equation gif. Since tex2html_wrap_inline67543, the total running time is tex2html_wrap_inline67655. But this no better than the original, direct algorithm!

Fortunately, it turns out that one of the eight matrix multiplications is redundant. Consider the following series of seven tex2html_wrap_inline67621 matrices:

eqnarray32774

Each equation above has only one multiplication. Ten additions and seven multiplications are required to compute tex2html_wrap_inline67659 through tex2html_wrap_inline67661. Given tex2html_wrap_inline67659 through tex2html_wrap_inline67661, we can compute the elements of the product matrix C as follows:

eqnarray32800

Altogether this approach requires seven tex2html_wrap_inline67621 matrix multiplications and 18 tex2html_wrap_inline67621 additions. Therefore, the worst-case running time is given by the following recurrence:

  equation32814

As above, Equation gif is an instance of the general recurrence given in Equation gif. and we obtain the solution directly from Equation gif. In this case, a=7, b=2, and k=2. Therefore, tex2html_wrap_inline67543 and the total running time is

displaymath67602

Note tex2html_wrap_inline67681. Consequently, the running time of the divide-and-conquer matrix multiplication strategy is tex2html_wrap_inline67683 which is better (asymptotically) than the straightforward tex2html_wrap_inline58434 approach.


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.