4-6 Lecture Notes for Chapter 4: Divide-and-Conquer
Recurrence for recursive case becomes
T .n/ D ‚.1/ C 2T .n=2/ C ‚.n/ C ‚.1/
D 2T .n=2/ C ‚.n/ (absorb ‚.1/ terms into ‚.n/) :
The recurrence for all cases:
(
‚.1/ if n D 1 ;
T .n/ D
2T .n=2/ C ‚.n/ if n > 1 :
Same recurrence as for merge sort. Can use the master method to show that it has
solution T .n/ D ‚.n lg n/.
Thus, with divide-and-conquer, we have developed a ‚.n lg n/-time solution.
Better than the ‚.n2 /-time brute-force solution.
[Can actually solve this problem in ‚.n/ time. See Exercise 4.1-5.]
Strassen’s algorithm for matrix multiplication
Input: Two n n (square) matrices, A D .aij / and B D .bij /.
Output: n n matrix C D .cij /, where C D A B, i.e.,
n
X
cij D ai k bkj
kD1
for i; j D 1; 2; : : : ; n.
Need to compute n2 entries of C . Each entry is the sum of n values.
Obvious method
[Using a shorter procedure name than in the book.]
S QUARE -M AT-M ULT .A; B; n/
let C be a new n n matrix
for i D 1 to n
for j D 1 to n
cij D 0
for k D 1 to n
cij D cij C ai k bkj
return C
Analysis: Three nested loops, each iterates n times, and innermost loop body takes
constant time ) ‚.n3 /.
Lecture Notes for Chapter 4: Divide-and-Conquer 4-7
Is ‚.n3 / the best we can do? Can we multiply matrices in o.n3 / time?
Seems like any algorithm to multiply matrices must take .n3 / time:
Must compute n2 entries.
Each entry is the sum of n terms.
But with Strassen’s method, we can multiply matrices in o.n3 / time.
Strassen’s algorithm runs in ‚.nlg 7 / time.
2:80 lg 7 2:81.
Hence, runs in O.n2:81 / time.
Simple divide-and-conquer method
As with the other divide-and-conquer algorithms, assume that n is a power of 2.
Partition each of A; B; C into four n=2 n=2 matrices:
A11 A12 B11 B12 C11 C12
AD ; BD ; C D :
A21 A22 B21 B22 C21 C22
Rewrite C D A B as
C11 C12 A11 A12 B11 B12
D ;
C21 C22 A21 A22 B21 B22
giving the four equations
C11 D A11 B11 C A12 B21 ;
C12 D A11 B12 C A12 B22 ;
C21 D A21 B11 C A22 B21 ;
C22 D A21 B12 C A22 B22 :
Each of these equations multiplies two n=2 n=2 matrices and then adds their
n=2 n=2 products.
Use these equations to get a divide-and-conquer algorithm: [Using a shorter pro-
cedure name than in the book.]
R EC -M AT-M ULT .A; B; n/
let C be a new n n matrix
if n == 1
c11 D a11 b11
else partition A, B, and C into n=2 n=2 submatrices
C11 D R EC -M AT-M ULT .A11 ; B11 ; n=2/ C R EC -M AT-M ULT .A12 ; B21 ; n=2/
C12 D R EC -M AT-M ULT .A11 ; B12 ; n=2/ C R EC -M AT-M ULT .A12 ; B22 ; n=2/
C21 D R EC -M AT-M ULT .A21 ; B11 ; n=2/ C R EC -M AT-M ULT .A22 ; B21 ; n=2/
C22 D R EC -M AT-M ULT .A21 ; B12 ; n=2/ C R EC -M AT-M ULT .A22 ; B22 ; n=2/
return C
[The book briefly discusses the question of how to avoid copying entries when par-
titioning matrices. Can partition matrices without copying entries by instead using
index calculations. Identify a submatrix by ranges of row and column matrices
4-8 Lecture Notes for Chapter 4: Divide-and-Conquer
from the original matrix. End up representing a submatrix differently from how
we represent the original matrix. The advantage of avoiding copying is that par-
titioning would take only constant time, instead of ‚.n2 / time. The result of the
asymptotic analysis won’t change, but using index calculations to avoid copying
gives better constant factors.]
Analysis
Let T .n/ be the time to multiply two n=2 n=2 matrices.
Base case: n D 1. Perform one scalar multiplication: ‚.1/.
Recursive case: n > 1.
Dividing takes ‚.1/ time, using index calculations. [Otherwise, ‚.n2 / time.]
Conquering makes 8 recursive calls, each multiplying n=2 n=2 matrices )
8T .n=2/.
Combining takes ‚.n2 / time to add n=2 n=2 matrices four times. [Doesn’t
even matter asymptotically whether we use index calculations or copy: would
be ‚.n2 / either way.]
Recurrence is
(
‚.1/ if n D 1 ;
T .n/ D 2
8T .n=2/ C ‚.n / if n > 1 :
Can use master method to show that it has solution T .n/ D ‚.n3 /.
Asymptotically, no better than the obvious method.
Constant factors and recurrences: When setting up recurrences, can absorb con-
stant factors into asymptotic notation, but cannot absorb a constant number of sub-
probems. Although we absorb the 4 additions of n=2n=2 matrices into the ‚.n2 /
time, we cannot lose the 8 in front of the T .n=2/ term. If we absorb the constant
number of subproblems, then the recursion tree would not be “bushy” and would
instead just be a linear chain.
Strassen’s method
Idea: Make the recursion tree less bushy. Perform only 7 recursive multiplications
of n=2 n=2 matrices, rather than 8. Will cost several additions of n=2 n=2
matrices, but just a constant number more ) can still absorb the constant factor
for matrix additions into the ‚.n=2/ term.
The algorithm:
1. As in the recursive method, partition each of the matrices into four n=2 n=2
submatrices. Time: ‚.1/.
2. Create 10 matrices S1 ; S2 ; : : : ; S10 . Each is n=2 n=2 and is the sum or dif-
ference of two matrices created in previous step. Time: ‚.n2 / to create all 10
matrices.
3. Recursively compute 7 matrix products P1 ; P2 ; : : : ; P7 , each n=2 n=2.
4. Compute n=2 n=2 submatrices of C by adding and subtracting various com-
binations of the Pi . Time: ‚.n2 /.
Lecture Notes for Chapter 4: Divide-and-Conquer 4-9
Analysis
Recurrence will be
(
‚.1/ if n D 1 ;
T .n/ D 2
7T .n=2/ C ‚.n / if n > 1 :
By the master method, solution is T .n/ D ‚.nlg 7 /.
Details
Step 2: Create the 10 matrices
S1 D B12 B22 ;
S2 D A11 C A12 ;
S3 D A21 C A22 ;
S4 D B21 B11 ;
S5 D A11 C A22 ;
S6 D B11 C B22 ;
S7 D A12 A22 ;
S8 D B21 C B22 ;
S9 D A11 A21 ;
S10 D B11 C B12 :
Add or subtract n=2 n=2 matrices 10 times ) time is ‚.n=2/.
Step 3: Create the 7 matrices
P1 D A11 S1 D A11 B12 A11 B22 ;
P2 D S2 B22 D A11 B22 C A12 B22 ;
P3 D S3 B11 D A21 B11 C A22 B11 ;
P4 D A22 S4 D A22 B21 A22 B11 ;
P5 D S5 S6 D A11 B11 C A11 B22 C A22 B11 C A22 B22 ;
P6 D S7 S8 D A12 B21 C A12 B22 A22 B21 A22 B22 ;
P7 D S9 S10 D A11 B11 C A11 B12 A21 B11 A21 B12 :
The only multiplications needed are in the middle column; right-hand column just
shows the products in terms of the original submatrices of A and B.
Step 4: Add and subtract the Pi to construct submatrices of C :
C11 D P5 C P4 P2 C P6 ;
C12 D P1 C P2 ;
C21 D P3 C P4 ;
C22 D P5 C P1 P3 P7 :
To see how these computations work, expand each right-hand side, replacing
each Pi with the submatrices of A and B that form it, and cancel terms: [We
expand out all four right-hand sides here. You might want to do just one or two of
them, to convince students that it works.]
4-10 Lecture Notes for Chapter 4: Divide-and-Conquer
A11 B11 C A11 B22 C A22 B11 C A22 B22
A22 B11 C A22 B21
A11 B22 A12 B22
A22 B22 A22 B21 C A12 B22 C A12 B21
A11 B11 C A12 B21
A11 B12 A11 B22
C A11 B22 C A12 B22
A11 B12 C A12 B22
A21 B11 C A22 B11
A22 B11 C A22 B21
A21 B11 C A22 B21
A11 B11 C A11 B22 C A22 B11 C A22 B22
A11 B22 C A11 B12
A22 B11 A21 B11
A11 B11 A11 B12 C A21 B11 C A21 B12
A22 B22 C A21 B12
Theoretical and practical notes
Strassen’s algorithm was the first to beat ‚.n3 / time, but it’s not the asymptotically
fastest known. A method by Coppersmith and Winograd runs in O.n2:376 / time.
Practical issues against Strassen’s algorithm:
Higher constant factor than the obvious ‚.n3 /-time method.
Not good for sparse matrices.
Not numerically stable: larger errors accumulate than in the obvious method.
Submatrices consume space, especially if copying.
Numerical stability problem is not as bad as previously thought. And can use index
calculations to reduce space requirement.
Various researchers have tried to find the crossover point, where Strassen’s algo-
rthm runs faster than the obvious ‚.n3 /-time method. Analyses (that ignore caches
and hardware pipelines) have produced crossover points as low as n D 8, and ex-
periments have found crossover points as low as n D 400.
Substitution method
1. Guess the solution.
2. Use induction to find the constants and show that the solution works.