Strassen’s Matrix Multiplication�

​

• Given two square matrices A and B of size

N x N each, find their multiplication matrix.

Amity School of Engineering & Technology

Naive Method

void multiply(int A[][N], int B[][N], int C[][N])

{

for (int i = 0; i < N; i++)

{

for (int j = 0; j < N; j++)

{

C[i][j] = 0;

for (int k = 0; k < N; k++)

{

C[i][j] += A[i][k]*B[k][j];

}

}

}

}

​

Amity School of Engineering & Technology

​

​

​

• Time Complexity of above method is O(N³).

Amity School of Engineering & Technology

Divide and Conquer

• Following is simple Divide and Conquer method to multiply two square matrices.�

Divide matrices A and B in 4 sub-matrices of size N/2 x N/2 as shown in the below diagram.

�

Amity School of Engineering & Technology

Amity School of Engineering & Technology

• In the above method, we do 8 multiplications for matrices of size N/2 x N/2 and 4 additions. Addition of two matrices takes O(N²) time. So the time complexity can be written as

T(N) = 8T(N/2) + O(N²)

time complexity of above method is O(N³) which is unfortunately same as the above naive method.

Amity School of Engineering & Technology

In the above divide and conquer method, the main component for high time complexity is 8 recursive calls. The idea of Strassen’s method is to reduce the number of recursive calls to 7. Strassen’s method is similar to above simple divide and conquer method in the sense that this method also divide matrices to sub-matrices of size N/2 x N/2 as shown in the above diagram, but in Strassen’s method, the four sub-matrices of result are calculated using following formulae.

Amity School of Engineering & Technology

Amity School of Engineering & Technology

P = (A₁₁+ A₂₂) *(B₁₁+B₂₂) �Q = (A₂₁ + A₂₂) * B₁₁ �R = A₁₁ * (B₁₂ - B₂₂) �S = A₂₂ * (B₂₁ - B₁₁) �T= (A₁₁ + A₁₂) * B₂₂ �U = (A₂₁ - A₁₁) * (B₁₁ + B₁₂) �V= (A₁₂ - A₂₂) * (B₂₁ + B₂₂)

​

Amity School of Engineering & Technology

C₁₁ = P + S - T+ V�C₁₂ = R+ T �C₂₁ = Q + S �C₂₂ = P + R - Q + U

​

​

Amity School of Engineering & Technology

Time Complexity of Strassen’s Method

• Addition and Subtraction of two matrices takes O(N²) time. So time complexity can be written as

T(N) = 7T(N/2) + O(N²)

​

time complexity of above method is O(N^lg7) which is approximately O(N^2.8074)

Amity School of Engineering & Technology

Problem-1

Amity School of Engineering & Technology

Answer

Amity School of Engineering & Technology

Problem-2

Amity School of Engineering & Technology

Answer

Amity School of Engineering & Technology