Logo 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. I.e., given two tex2html_wrap_inline68887 matrices, A and B, compute the tex2html_wrap_inline68887 matrix tex2html_wrap_inline68895, the elements of which are given by

  equation33138

Section gif shows that the direct implementation of Equation gif results in an tex2html_wrap_inline59491 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_inline68887 matrices as a tex2html_wrap_inline68901 matrix, the elements of which are tex2html_wrap_inline68903 submatrices. Thus, the original matrix multiplication, tex2html_wrap_inline68895 can be written as

displaymath68883

where each tex2html_wrap_inline68907, tex2html_wrap_inline68909 and tex2html_wrap_inline68911 is an tex2html_wrap_inline68903 matrix.

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

eqnarray33178

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

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

  equation33214

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_inline68825, the total running time is tex2html_wrap_inline68937. 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_inline68903 matrices:

eqnarray33228

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

eqnarray33254

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

  equation33268

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

displaymath68884

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


next up previous contents index

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