Strassen.ppt

Design Analysis Algorithm

1. Strassen's Matrix
Multiplication
Sibel KIRMIZIGÜL

2. Basic Matrix Multiplication
Suppose we want to multiply two matrices of size N
x N: for example Ax B = C.
C
11
= a
11
b
11
+ a
12
b
21
C
12
= a
11
b
12
+ a
12
b
22
C
21
= a
21
b
11
+ a
22
b
21
C
22
= a
21
b
12
+ a
22
b
22
2x2 matrix multiplication can be
accomplished in 8 multiplication.(2
log
2
8
=2
3
)

3. Basic Matrix Multiplication)()( Thus
3
11
3
1
,
1
,,
NOcNcNT
baC
N
i
N
j
N
k
jk
N
k
kiji






void matrix_mult (){
for (i = 1; i <= N; i++) {
for (j = 1; j <= N; j++) {
compute C
i,j;
}
}}
algorithm
Time analysis

4. Strassens’s Matrix Multiplication
Strassen showed that 2x2 matrix multiplication
can be accomplished in 7 multiplication and 18
additions or subtractions. .(2
log
2
7
=2
2.807
)
This reduce can be done by Divide and Conquer
Approach.

5. Divide-and-Conquer
Divide-and conqueris a general algorithm design
paradigm:
Divide: divide the input data Sin two or more disjoint
subsets S
1, S
2, …
Recur: solve the subproblems recursively
Conquer: combine the solutions for S
1,S
2, …, into a
solution for S
The base case for the recursion are subproblems of
constant size
Analysis can be done using recurrence equations

6. Divide and Conquer Matrix Multiply
AB= R
A
0A
1
A
2A
3
B
0B
1
B
2B
3
A
0B
0+A
1B
2A
0B
1+A
1B
3
A
2B
0+A
3B
2A
2B
1+A
3B
3
 =
•Divide matrices into sub-matrices: A
0 , A
1, A
2etc
•Use blocked matrix multiply equations
•Recursively multiply sub-matrices

7. Divide and Conquer Matrix Multiply
 =a
0 b
0 a
0b
0
AB= R
•Terminate recursion with a simple base case

8. Strassens’s Matrix Multiplication
P
1
= (A
11
+ A
22
)(B
11
+B
22
)
P
2
= (A
21
+ A
22
) * B
11
P
3
= A
11
* (B
12
-B
22
)
P
4
= A
22
* (B
21
-B
11
)
P
5
= (A
11
+ A
12
) * B
22
P
6
= (A
21
-A
11
) * (B
11
+ B
12
)
P
7
= (A
12
-A
22
) * (B
21
+ B
22
)
C
11
= P
1
+ P
4
-P
5
+ P
7
C
12
= P
3
+ P
5
C
21
= P
2
+ P
4
C
22
= P
1
+ P
3
-P
2
+ P
6

9. C
11
= P
1
+ P
4
-P
5
+ P
7
= (A
11
+ A
22
)(B
11
+B
22
) + A
22
* (B
21
-B
11
) -(A
11
+ A
12
) * B
22
+
(A
12
-A
22
) * (B
21
+ B
22
)
= A
11
B
11
+ A
11
B
22
+ A
22
B
11
+ A
22
B
22
+ A
22
B
21
–A
22
B
11
-
A
11
B
22
-A
12
B
22
+A
12
B
21
+ A
12
B
22
–A
22
B
21
–A
22
B
22
= A
11
B
11
+A
12
B
21
Comparison

10. Strassen Algorithm
void matmul(int *A, int *B, int *R, int n) {
if (n == 1) {
(*R) += (*A) * (*B);
} else {
matmul(A, B, R, n/4);
matmul(A, B+(n/4), R+(n/4), n/4);
matmul(A+2*(n/4), B, R+2*(n/4), n/4);
matmul(A+2*(n/4), B+(n/4), R+3*(n/4), n/4);
matmul(A+(n/4), B+2*(n/4), R, n/4);
matmul(A+(n/4), B+3*(n/4), R+(n/4), n/4);
matmul(A+3*(n/4), B+2*(n/4), R+2*(n/4), n/4);
matmul(A+3*(n/4), B+3*(n/4), R+3*(n/4), n/4);
}
Divide matrices in
sub-matrices and
recursively multiply
sub-matrices

11. Time Analysis