Divide Conquer and Combine Algorithm
Matrix Multiplication
3
Matrix Multiplication
Cost = O(n3)
Matrix Multiplication
Matrix multiplication. Given two n-by-n matrices A and B, compute C = AB.
Grade-school. (n3) arithmetic operations.
c11 c12 c1n a11 a12 a1n b11 b12 b1n
c21 c22 c2n a
= 21
a22 a2n b b
21 22
b2n
cn1 cn2 cnn an1 an2 ann bn1 bn2 bnn
.59 .32 .41 .70 .20 .10 .80 .30 .50
.31 .36 .25 = .30 .60 .10 .10 .40 .10
.45 .31 .42 .50 .10 .40 .10 .30 .40
Q. Can we perform matrix multiplication more effeciantly
5
MATRIX-MULTIPLY-RECURSIVE(A, B, C, n)
if n == 1
// Base case.
c_11 = c_11 + a_11 · b_11
return
// Divide.
partition A, B, and C into n/2 × n/2 submatrices A_11,
A_12, A_21, A_22; B_11, B_12, B_21, B_22;
and C_11, C_12, C_21, C_22; respectively
// Conquer.
MATRIX-MULTIPLY-RECURSIVE(A_11, B_11, C_11, n/2)
MATRIX-MULTIPLY-RECURSIVE(A_11, B_12, C_12, n/2)
MATRIX-MULTIPLY-RECURSIVE(A_21, B_11, C_21, n/2)
MATRIX-MULTIPLY-RECURSIVE(A_21, B_12, C_22, n/2)
MATRIX-MULTIPLY-RECURSIVE(A_12, B_21, C_11, n/2)
MATRIX-MULTIPLY-RECURSIVE(A_12, B_22, C_12, n/2)
MATRIX-MULTIPLY-RECURSIVE(A_22, B_21, C_21, n/2)
MATRIX-MULTIPLY-RECURSIVE(A_22, B_22, C_22, n/2)
Block Matrix Multiplication
A11 A12 B11
C11
152 158 164 170 0 1 2 3 16 17 18 19
504 526 548 570 = 4 5 6 7 20 21 22 23
856 894 932 970 8 9 10 11 24 25 26 27
1208 1262 1316 1370 12 13 14 15 28 29 30 31
B21
0 1 16 17 2 3 24 25 152 158
C11 = A11 B11 + A12 B21 =
+
=
4 5 20 21 6 7 28 29 504 526
9
Matrix Multiplication: Warmup
To multiply two n-by-n matrices A and B:
Divide: partition A and B into ½n-by-½n blocks.
Conquer: multiply 8 pairs of ½n-by-½n matrices, recursively.
Combine: add appropriate products using 4 matrix additions.
C11 C12 A11 A12 B11 B12 C11 = (A11 B11 ) + (A12 B21 )
= = (A11 B12 ) + (A12 B22 )
21
C C22 A21 A22 B21 B22 C12
C21 = (A21 B11 ) + (A22 B21 )
C22 = (A21 B12 ) + (A22 B22 )
T (n) = 8T (n /2 ) + (n 2 ) T (n) = (n 3 )
recursive calls add, form submatrices
10
Divide Conquer and Combine Algorithm
Strassen Matrix multiplication Fast way to multiply
:
2 matrices
Fast Matrix Multiplication
Key idea. multiply 2-by-2 blocks with only 7 multiplications.
C11 C12 A11 A12 B11 B12
= P1 = A11 ( B12 − B22 )
C21 C22 A21 A22 B21 B22
P2 = ( A11 + A12 ) B22
P3 = ( A21 + A22 ) B11
C11 = P5 + P4 − P2 + P6 P4 = A22 ( B21 − B11 )
C12 = P1 + P2 P5 = ( A11 + A22 ) ( B11 + B22 )
C21 = P3 + P4 P6 = ( A12 − A22 ) ( B21 + B22 )
C22 = P5 + P1 − P3 − P7 P7 = ( A11 − A21 ) ( B11 + B12 )
7 multiplications.
18 = 8 + 10 additions and subtractions.
12
Fast Matrix Multiplication
To multiply two n-by-n matrices A and B: [Strassen 1969]
Divide: partition A and B into ½n-by-½n blocks.
Compute: 14 ½n-by-½n matrices via 10 matrix additions.
Conquer: multiply 7 pairs of ½n-by-½n matrices, recursively.
Combine: 7 products into 4 terms using 8 matrix additions.
Analysis.
Assume n is a power of 2.
T(n) = # arithmetic operations.
T (n) = 7T (n /2 )+ (n 2 ) T (n) = (n log 2 7 ) = O(n 2.81 )
recursive calls add, subtract
13
Thank You
