(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 "+" 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.)
- Suppose "*" in this algorithm is computed by the "obvious"
algorithm suggested in the first paragraph. How many scalar
multiplications are performed by the algorithm MMult when
multiplying two n x n matrices?
- Now 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 #44 of the D&C slides.
- Solve the recurrence directly, using one of the methods
outlined in lecture or the text (excluding the "master
recurrence"; i.e., grind through the algebra...)
- Around 1969, V. Strassen figured out a way to do MMult 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). Repeat steps a, b, and c (but
not d) assumming that the body of MMult is replaced by this
more clever method.
- 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 