Scribd
Upload
12 views14 pages

Strassen's Matrix Multiplication

Strassen's Matrix Multiplication is an efficient algorithm that reduces the number of multiplications needed for matrix multiplication from 8 to 7 using a divide and conquer approach. The algorithm divides matrices into smaller submatrices and combines their results, achieving a time complexity of O(N^log2(7)). This method is more efficient than the standard O(N^3) matrix multiplication algorithm, making it a significant advancement in computational mathematics.

Uploaded by

joshiharshita234
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views14 pages

Strassen's Matrix Multiplication

Strassen's Matrix Multiplication is an efficient algorithm that reduces the number of multiplications needed for matrix multiplication from 8 to 7 using a divide and conquer approach. The algorithm divides matrices into smaller submatrices and combines their results, achieving a time complexity of O(N^log2(7)). This method is more efficient than the standard O(N^3) matrix multiplication algorithm, making it a significant advancement in computational mathematics.

Uploaded by

joshiharshita234
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Strassen's Matrix Multiplication

(A Divide and Conquer approach)


Basic Matrix Multiplication

Suppose we want to multiply two matrices of size N


x N: for example A x B = C.

C11 = a11b11 + a12b21


C12 = a11b12 + a12b22
C21 = a21b11 + a22b21
C22 = a21b12 + a22b22
Basic Matrix Multiplication
void matrix_mult (){
for (i = 1; i <= M; i++) {
for (j = 1; j <= N; j++) {
for (k = 1; k <= M; k++) { algorithm
C[i][j]+=A[i][k]*B[k][j];
}
}
}}

N
Ci , j =  ai ,k bk , j
k =1
N N N
Thus T ( N ) =  c = cN 3 = O( N 3 )
Time analysis

i =1 j =1 k =1
Strassens’s Matrix Multiplication

• Strassen showed that 2x2 matrix multiplication can


be accomplished in 7 multiplication and 18 additions
or subtractions.(2log27 =22.807)

• This can be done by Divide and Conquer Approach.


Divide-and-Conquer
• Divide-and conquer is a general algorithm design
paradigm:
– Divide: divide the input data S in two or more disjoint
subsets S1, S2, …
– Recur: solve the subproblems recursively
– Conquer: combine the solutions for S1, S2, …, into a
solution for S
• The base case for the recursion are subproblems of
constant size
• Analysis can be done using recurrence equations
Divide and Conquer Matrix Multiply
A  B = R
A0 A1 B0 B1 A0B0+A1B2 A0B1+A1B3
 =
A2 A3 B2 B3 A2B0+A3B2 A2B1+A3B3
Divide and Conquer Matrix Multiply

A  B = R
a0  b0 = a0  b0
Strassens’s Matrix Multiplication

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)
Comparison
C11 = P1 + P4 - P5 + P7
= (A11+ A22)(B11+B22) + A22 * (B21 - B11) - (A11 + A12) * B22+
(A12 - A22) * (B21 + B22)
= A11 B11 + A11 B22 + A22 B11 + A22 B22 + A22 B21 – A22 B11 -
A11 B22 -A12 B22 + A12 B21 + A12 B22 – A22 B21 – A22 B22

= A11 B11 + A12 B21


Comparison
C12 = P3 + P5

= A11 * (B12 - B22) + (A11 + A12) * B22


= A11 B12 – A11 B22 + A11 B22 + A12 B22

= A11 B12 + A12 B22


Comparison
C21 = P2 + P4

= (A21 + A22) * B11 + A22 * (B21 - B11)


= A21 B11 + A22 B11 + A22 B21 – A22 B11

= A21 B11 + A22 B21


Comparison
C22 = P1 + P3 - P2 + P6
= (A11+ A22)(B11+B22) + A11 * (B12 - B22) - (A21 + A22) * B11
+ (A21 - A11) * (B11 + B12)

= A22 B22 + A21 B11


Comparison

C11 = A11 B11 + A12 B21

C12 = A11 B12 + A12 B22


C21 = A21 B11 + A22 B21
C22 = A22 B22 + A21 B11

Only 7 multiplication
required
Time Analysis

You might also like