(20 points)
For two n x n matrices of real numbers A = (ai,j) and B
= (bi,j), their product C = A*B is defined by
ci,j = &Sigma1≤k≤n
ai,k*bk,j. The obvious algorithm based on
this definition takes time O(n3): O(n) steps to compute
each of the O(n2) entries ci,j. To be more
precise, let's focus on the number of scalar multiplications
(i.e., multiplications of two real numbers) performed; it will be
exactly n3 multiplications. Is there a better way?
Having just read the Divide & Conquer chapter, you might think
of this:
MMult(A,B)
View A as a 2 x 2 matrix (Ai,j) for 1≤i,j≤2, where
A1,1 is the n/2 x n/2 matrix consisting of the first
n/2 rows by n/2 columns of A, etc.
Similarly, view B and C as 2 x 2 matrices whose entries are n/2 x n/2 matrices.
Calculate
C1,1 = A1,1 * B1,1 + A1,2 * B2,1
C1,2 = A1,1 * B1,2 + A1,2 * B2,2
C2,1 = A2,1 * B1,1 + A2,2 * B2,1
C2,2 = A2,1 * B1,2 + A2,2 * B2,2
Return C
(Here "*" denotes matrix multiplication and "+" just means to add
corresponding pairs of matrix elements.) If you do the algebra,
you should find that this correctly computes C = A*B. (No need to
turn this in.) In this problem we're going to look at 4
different versions of MMult, based on how that "*" is computed:
-
For version 1, suppose the eight "*"'s in MMult are directly
computed by the "obvious" algorithm suggested in the first
paragraph (not by recursively applying MMult). How many scalar
multiplications are performed by the algorithm MMult when
multiplying two n x n matrices?
-
For version 2, suppose instead that "*" in this algorithm is
performed by recursively calling MMult (unless n=1, in
which case A and B are scalars and you just directly multiply
them and return their product). Write a recurrence relation
for the number of scalar multiplications performed by this
algorithm when multiplying two n x n matrices.
-
Solve the above recurrence using the "master recurrence" on
slide #49 of the D&C slides.
-
Solve the recurrence directly, using one of the methods
outlined in the text (5.1-5.2) or lecture (slides 43-48,
excluding the "master recurrence"); i.e., fun with algebra...
-
Around 1969, V. Strassen figured out a way to do matrix
multiplication by a method somewhat like MMult above, but
using 7 multiplications of n/2 x n/2 matrices instead of the 8
used above (somewhat like the trick in Karatsuba's algorithm
for integer multiplication). For versions 3, repeat step a
assuming that the body of MMult, version 1, is replaced by
this more clever method (but "*" is again computed by the
direct n3 method). Finally, for version 4, repeat
steps b, and c (but not d) assuming the fancy 7-multiply
method is used recursively.
-
Strassen's method requires more additions than MMult above
(15 or so, instead of 4). If we count the total number of
additions instead of multiplications, is Strassen's method
still better that the "obvious" algorithm?
CSE Home 