Strassens Matrix Multiplication

Design and Analysis of Algorithm
Strassen’s Matrix Multiplication
Bheekya D
Basic or brute force Matrix Multiplication
Let A and B two N×N matrices. The product C = AB is also

an N×N matrix.
void matrix_mult (){

for (i = 1; i <= N; i++) {
for (j = 1; j <= N; j++) {
for(k=1; k<=N; k++){
C[i,j]=C[i,j]+A[i,k]*B[k,j];
}
}}
Time complexity of above algorithm is

T(n)=O(n3)
Divide and Conquer Matrix Multiplication
• strassen’s Matrix Multiplication is divide and conquer technique.
• Compute the product of two matrices is C = A * B, where each of
A,B, and C are n×n matrices.
• Assume n is a power of 2.
• If n is not a power of 2, add enough rows and columns of zeros.
• We divide each of A,B, and C into four n/2×n/2 matrices,
rewriting the equation C=AB as follows:
Then,
C11=A11B11+A12B21
C12=A11B12+A12B22
C21=A21B11+A22B21
C22=A21B12+A22B22
• Each of these four equations specifies two multiplications of n/2×n/2
matrices and the addition of their n/2×n/2 products.
• We can derive the following recurrence relation for the time T(n) to
multiply two n×n matrices:
T(n)= c1 if n<=2
8T(n/2)+ c2n2 if n>2
T(n) = O(n3)
• This method is no faster than the ordinary method.

T(n)= 8T(n/2)+ c2n2
=8 8T(n/4)+ c2(n/2)2 + c2n2
= 82 T(n/4)+ c22n2 +
c 2 n2
=82 8T(n/8)+ c2(n/4)2 + c22n2 + c2n2
=83 T(n/8)+ c24n2 + c22n2 + c2n2

:
=8kT(1)+ ………………+ c24n2 + c22n2 + c2n2
= log n
8 2 c1 + c n2
.
8
=nlog2 c1 + c n2 = n3 c1+ cn2 = O(n3 )
Strassen’s Matrix Multiplication
• Matrix multiplications are more expensive than matrix additions
or subtractions
• Time complexity of matrix multiplication: O(n3)
• Time complexity of matrix addition: O(n2).
• Strassen has discovered a way to compute the multiplication

using only 7 multiplications and 18 additions or subtractions.
• His method involves computing 7 n×n matrices

M1,M2,M3,M4,M5,M6, and M7, then cij’s are calculated using these
matrices.
Formulas for Strassen’s matrix multiplication
Algorithm
M1 = (A11 + A22) * (B11 + B22)
M2 = (A21 + A22) * B11
M3 = A11 * (B12 – B22)
M4 = A22 * (B21 – B11)
M5 = (A11 + A12) * B22
M6 = (A21 – A11) * (B11 + B12)
M7 = (A12 – A22) * (B21 + B22)
C11=M1 + M4 - M5 + M7
C12= M3 + M5
C21= M2 + M4
C22=M1 + M3 - M2 + M6
Formulas for Strassen’s matrix multiplication
Algorithm
C11 C12 A11 A12 B11 B12
= *
C21 C22 A21 A22 B21 B22
M1 + M 4 - M 5 + M 7 M3 + M 5
=
M2 + M 4 M 1 + M3 - M 2 + M6
The resulting recurrence relation for T(n) is
T(n)= c1 n<=2
7T(n/2) +c2n2 n>2

Master’s Theorem
• Master Method is a direct way to get the solution. The master method
works only for following type of recurrences or for recurrences that can be
transformed to following type.
T(n) = aT(n/b) + f(n)
We assume that a >= 1, b > 1 and f(n) = Θ(nk logpn)
• There are following three cases based on the values of a and bk:
• If a>bk then T(n) = Θ(nLogba)
• If a = bk then it has the following cases:
• if p>-1 then T(n) = Θ(nk logp+1n))
• if p=-1 then T(n)= Θ(nk log log n))
• if p<-1 then T(n) = Θ(nk)
• If a < bk then it has the following cases:
• if p>=0 then T(n) = Θ(f(n))
• if p<0 then T(n) = Θ(nk)
T(n)= 7kT(1) + c2n2 1+ 7/4 + (7/4)2 + (7/4) 3+……………..+ (7/4)k-1
= 7log2n c1 +c2 n2 (7/4)log2n
= nlog27 + nlog24 ( n log27-log24 )
= 2 nlog27 = O(nlog27) ~ O( n2.81)

Div. & Conq. : Strassen’s Matrix Multiplication
ALGORITHM Strassen(A, B, n)
//Input: A and B are n×n matrices Recurrence for
//where n is a power of two # of multiplications is
//Output: C = A*B
M(n) = 7M(n/2) for n > 1
if n = 1
M(1) = ?
return C = A*B
else For n = 2m,
A00 A01 B00 B01
M(n) = 7M(n/2) = 72M(n/22)
Partition A = and B =
A10 A11 B10 B11 M(n) = 7m M(n/2m)
where the blocks Aij and Bij are (n/2)-by-(n/2) = 7m = 7lgn
= nlg7 ≈ n2.807
M1 <- Strassen(A00+A11, B00+B11, n/2)
M2 <- Strassen(A10+A11, B00, n/2) For # of adds/subs,
M3 <- Strassen(A00, B01-B11, n/2)
M4 <- Strassen(A11, B10-B00, n/2) A(n) = 7A(n/2)+18(n/2)2 for n > 1
M5 <- Strassen(A00+A01, B11, n/2) A(1) = 0
M6 <- Strassen(A10-A00, B00+B01, n/2)
M7 <- Strassen(A01-A11, B10+B11, n/2) Using Master thm,
C00 <- M1+M4-M5+M7 A(n) є Θ(nlg7) better
C01 <- M3+M5 than brute-force’s Θ(n3)
C10 <- M2+M4
C11 <- M1+M3-M2+M6
C00 C01
return C = DONE WITH STRASSEN!
C10 C11
• How do we multiply two 2×2 matrices ?
1 2 3 5 = 1*3+2*1=5 1*5+2*4=13
3 4 1 4 3*3+4*1=13 3*5+4*4=31
How many multiplications

and additions did we need?
By using Strassen method
a00 a01 b00 b01 c00 c01 m1+m4-m5+m7 m3+m5

= =
a10 a11 b10 b11 c10 c11 m2+m4 m1+m3-m2+m6
m1 = (a00+a11)*(b00+b11) = 35
m2 = (a10+a11)*b00 =21 35-8-12-10=5 1+12=13
m3 = a00*(b01-b11) = 1
21-8=13 35+1-21+16=31
m4 = a11*(b10-b00) = -8
m5 = (a00+a01)*b11 = 12
m6 = (a10-a00)*(b00+b01) = 16 7 mults
18 adds/subs
m7 = (a01-a11)*(b10+b11) = -10
STRESSEN’S MATRIX MULTIPLICATION
1 2 3 4 1 0 0 0 1 2 3 4
5 6 7 8 0 1 0 0 5 6 7 8
9 10 11 12
9 10 11 12 x 0 0 1 0
=
13 14 15 16 0 0 0 1 13 14 15 16
P1 = (A11+ A22)(B11+B22) C11 = P1 + P4 - P5 + P7

P2 = (A21 + A22) * B11 C12 = P3 + P5
P3 = A11 * (B12 - B22) C21 = P2 + P4
P4 = A22 * (B21 - B11) C22 = P1 + P3 - P2 + P6
P5 = (A11 + A12) * B22
P6 = (A21 - A11) * (B11 + B12)
P7 = (A12 - A22) * (B21 + B22)
1 2 3 4 9 10 11 12
A11 A12 A21 A22
= 5 6 = 7 8 = 13 14 = 15 16
1 0 0 0 0 0 1 0
B11= B12 B21 B22
0 1 0 0 = 0 0 = 0 1
=
P1 = (A11+ A22)(B11+B22) C11 = P1 + P4 - P5 + P7

P2 = (A21 + A22) * B11 C12 = P3 + P5
P3 = A11 * (B12 - B22) C21 = P2 + P4
P4 = A22 * (B21 - B11) C22 = P1 + P3 - P2 + P6
P5 = (A11 + A12) * B22
P6 = (A21 - A11) * (B11 + B12)
P7 = (A12 - A22) * (B21 + B22)
A11 A12 B11 B12 C11 C12

x =
A21 A22 B21 B22 C21 C22
P1 = (A11+ A22)(B11+B22)
C11 = P1 + P4 - P5 + P7
P2 = (A21 + A22) * B11
C12 = P3 + P5
P3 = A11 * (B12 - B22)
C21 = P2 + P4
P4 = A22 * (B21 - B11)
C22 = P1 + P3 - P2 + P6
P5 = (A11 + A12) * B22
P6 = (A21 - A11) * (B11 + B12)
P7 = (A12 - A22) * (B21 + B22)
A11 A12 B11 B12 C11 C12

+ =
A21 A22 B21 B22 C21 C22
C11 = A11+B11
C12 = A12+B12
C21 = A21+B21
C22 = A22+B22
• Let us see how we can apply Strassen’s idea for multiplying

two n×n matrices
Let A and B be two n×n matrices where n is a power of 2
A00 A01 B00 B01 C00 C01

=
A10 A11 B10 B11 C10 C11
Each block is (n/2)×(n/2)

E.g., In Strassen’s
method,
You can treat blocks
M1 = (A00+A11)*(B00+B11)
as if they were numbers
M2 = (A10+A11)*B00
to get the C = A*B
etc.

Strassens Matrix Multiplication

Uploaded by

Copyright:

Available Formats

Strassens Matrix Multiplication

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Strassens Matrix Multiplication

Uploaded by

Copyright:

Available Formats

Design and Analysis of Algorithm

Strassen’s Matrix Multiplication

Let A and B two N×N matrices. The product C = AB is also

void matrix_mult (){

Time complexity of above algorithm is

• This method is no faster than the ordinary method.

=82 8T(n/8)+ c2(n/4)2 + c22n2 + c2n2

=83 T(n/8)+ c24n2 + c22n2 + c2n2

• Strassen has discovered a way to compute the multiplication

• His method involves computing 7 n×n matrices

The resulting recurrence relation for T(n) is

7T(n/2) +c2n2 n>2

= 7log2n c1 +c2 n2 (7/4)log2n

= nlog27 + nlog24 ( n log27-log24 )

= 2 nlog27 = O(nlog27) ~ O( n2.81)

• How do we multiply two 2×2 matrices ?

How many multiplications

By using Strassen method

a00 a01 b00 b01 c00 c01 m1+m4-m5+m7 m3+m5

P1 = (A11+ A22)(B11+B22) C11 = P1 + P4 - P5 + P7

P1 = (A11+ A22)(B11+B22) C11 = P1 + P4 - P5 + P7

A11 A12 B11 B12 C11 C12

A11 A12 B11 B12 C11 C12

• Let us see how we can apply Strassen’s idea for multiplying

A00 A01 B00 B01 C00 C01

Each block is (n/2)×(n/2)

You might also like