Strassen Matrix Multiplication

Strassen Matrix Multiplication uses Divide & Conquer to multiply large matrices efficiently. Learn the algorithm, steps, time complexity, advantages, and applications.

Strassen Matrix Multiplication

(Strassen’s Matrix Multiplication Method)

1. Introduction

Strassen’s Matrix Multiplication Algorithm is an efficient Divide and Conquer–based algorithm used to multiply two square matrices faster than the traditional method.

In the traditional matrix multiplication, the time complexity is O(n³).
Strassen improved this by reducing the time complexity to:

O(nlog⁡27)≈O(n2.81)O(n^{\log_2 7}) \approx O(n^{2.81})O(nlog2​7)≈O(n2.81)

This improvement makes the algorithm suitable for large matrices.

2. Need for Strassen’s Algorithm

When the size of matrices is large, the traditional method becomes very slow due to a large number of multiplications.

Strassen’s Algorithm:

• Reduces the number of multiplications
• Improves performance for large matrices
• Uses the Divide & Conquer technique effectively

3. Divide and Conquer Approach

Strassen’s Algorithm follows the Divide and Conquer strategy.

Divide Step

Let there be two matrices A and B of size n × n.
Each matrix is divided into four equal sub-matrices.

Matrix A:

A = | A11  A12 |

    | A21  A22 |

Matrix B:

B = | B11  B12 |

    | B21  B22 |

4. Traditional Method vs Strassen Method

Traditional Matrix Multiplication

• 8 multiplications
• 4 additions
• Time Complexity: O(n³)

Strassen Method

• Only 7 multiplications
• Some extra additions and subtractions
• Time Complexity: O(n^log₂7)

5. Strassen’s Seven Multiplications

Strassen computes the following seven intermediate products:

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)

6. Final Result Matrix (Combine Step)

The result matrix C is obtained as follows:

C11 = M1 + M4 − M5 + M7

C12 = M3 + M5

C21 = M2 + M4

C22 = M1 − M2 + M3 + M6

7. Algorithm Steps

1. If the matrix size is 1 × 1, perform direct multiplication (Base Case).
2. Divide both matrices into four sub-matrices.
3. Compute the seven recursive multiplications.
4. Combine the results to form the final result matrix.

8. Time Complexity Analysis

The recurrence relation is:

T(n)=7T(n/2)+O(n2)T(n) = 7T(n/2) + O(n^2)T(n)=7T(n/2)+O(n2)

Using the Master Theorem:

T(n)=O(nlog⁡27)≈O(n2.81)T(n) = O(n^{\log_2 7}) \approx O(n^{2.81})T(n)=O(nlog2​7)≈O(n2.81)

This is significantly better than the traditional O(n³) complexity.

9. Advantages

1. Reduces the number of multiplications
2. Faster for large matrices
3. Efficient use of Divide & Conquer technique
4. Useful in high-performance computing

10. Disadvantages

1. Not efficient for small matrices
2. Requires additional memory and extra additions
3. Implementation is complex
4. Numerical stability issues may arise

11. Applications

• Scientific computing
• Computer graphics
• Image processing
• Machine learning and Artificial Intelligence
• High-performance computing systems

12. Conclusion

Strassen’s Matrix Multiplication Algorithm is a powerful Divide & Conquer–based technique that significantly reduces the time required for matrix multiplication.
Although it is not suitable for small matrices, it performs much better than the traditional method for large matrices.

Strassen’s Algorithm reduces the time complexity of matrix multiplication from O(n³) to O(n^log₂7).

• POP- Introduction to Programming Using ‘C’
• DS – Data structure Using C
• OOP – Object Oriented Programming 
• Java Programming
• DBMS – Database Management System
• RDBMS – Relational Database Management System
• https://defineinfoloop.blogspot.com/?m=1