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

Example-Matrix Multiplication

 

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

  equation32932

Section gif shows that the direct implementation of Equation gif results in an tex2html_wrap_inline58715 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_inline67888 matrices as a tex2html_wrap_inline67902 matrix, the elements of which are tex2html_wrap_inline67904 submatrices. Thus, the original matrix multiplication, tex2html_wrap_inline67896 can be written as

displaymath67884

where each tex2html_wrap_inline67908, tex2html_wrap_inline67910, and tex2html_wrap_inline67912 is an tex2html_wrap_inline67904 matrix.

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

eqnarray32972

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

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

  equation33008

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_inline67826, the total running time is tex2html_wrap_inline67938. 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_inline67904 matrices:

eqnarray33022

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

eqnarray33048

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

  equation33062

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_inline67826 and the total running time is

displaymath67885

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


next up previous contents index

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