Strassen's Matrix Multiplication
Introduction
Strassen's Matrix Multiplication is an efficient algorithm used to multiply two square matrices. It follows the Divide and Conquer technique by dividing large matrices into smaller sub-matrices and recursively multiplying them. Unlike the conventional matrix multiplication method, Strassen's Algorithm reduces the number of multiplications, making it faster for large matrices.
The traditional method requires 8 multiplications for multiplying two 2 × 2 matrices, whereas Strassen's Algorithm performs the same task using only 7 multiplications. This reduction significantly improves the overall time complexity.
Why Do We Need Strassen's Algorithm?
For very large matrices, the conventional matrix multiplication algorithm becomes computationally expensive. Strassen's Algorithm reduces the number of multiplication operations and improves performance, making it suitable for scientific computing and high-performance applications.
| Application | Purpose |
|---|---|
| Scientific Computing | Fast multiplication of large matrices. |
| Artificial Intelligence | Efficient matrix operations in machine learning. |
| Computer Graphics | Transformation and projection calculations. |
| Image Processing | Matrix-based image transformations. |
| Cryptography | High-speed matrix computations. |
Prerequisites
| Concept | Description |
|---|---|
| Matrix | A rectangular arrangement of numbers in rows and columns. |
| Square Matrix | A matrix having an equal number of rows and columns. |
| Divide and Conquer | Breaking a problem into smaller subproblems and solving them recursively. |
| Recursion | Repeatedly solving smaller instances of the same problem. |
Working Principle
Strassen's Algorithm divides each matrix into four equal-sized sub-matrices. Instead of performing eight recursive multiplications, it computes only seven intermediate products using carefully designed mathematical formulas. These intermediate products are then combined to produce the final result matrix.
Division of Matrices
Suppose two matrices A and B are divided into four equal parts as shown below.
| A11 | A12 |
| A21 | A22 |
| B11 | B12 |
| B21 | B22 |
Figure 1 : Division of matrices into four sub-matrices
Seven Intermediate Products
Instead of performing eight recursive multiplications, Strassen's Algorithm computes the following seven products.
| Product | Formula |
|---|---|
| P1 | (A11 + A22) × (B11 + B22) |
| P2 | (A21 + A22) × B11 |
| P3 | A11 × (B12 − B22) |
| P4 | A22 × (B21 − B11) |
| P5 | (A11 + A12) × B22 |
| P6 | (A21 − A11) × (B11 + B12) |
| P7 | (A12 − A22) × (B21 + B22) |
Construction of Result Matrix
After calculating the seven intermediate products (P1 to P7), the four sub-matrices of the resultant matrix are obtained using the following equations.
| Sub-Matrix | Formula |
|---|---|
| C11 | P1 + P4 − P5 + P7 |
| C12 | P3 + P5 |
| C21 | P2 + P4 |
| C22 | P1 − P2 + P3 + P6 |
Strassen's Algorithm
Strassen(A, B)
Step 1 : Divide matrices A and B into four equal sub-matrices.
Step 2 : Compute the seven products P1 to P7.
Step 3 : Compute C11, C12, C21 and C22.
Step 4 : Combine the four sub-matrices.
Step 5 : If the matrix size is greater than 2 × 2, apply recursion.
Step 6 : Display the resultant matrix.
Complexity Analysis
| Method | Time Complexity | Remarks |
|---|---|---|
| Conventional Matrix Multiplication | O(n³) | Uses eight recursive multiplications. |
| Strassen's Algorithm | O(n2.81) | Uses only seven recursive multiplications. |
| Space Complexity | O(n²) | Additional memory is required for intermediate matrices. |
Advantages of Strassen's Algorithm
- Faster than the conventional matrix multiplication method for large matrices.
- Reduces the number of multiplication operations from eight to seven.
- Uses the Divide and Conquer strategy effectively.
- Suitable for scientific and high-performance computing.
- Improves execution time for large datasets.
Limitations of Strassen's Algorithm
- More complex than the conventional multiplication method.
- Requires additional memory for intermediate matrices.
- Not efficient for very small matrices because of recursive overhead.
- Implementation is comparatively difficult.
Applications of Strassen's Algorithm
| Application | Description |
|---|---|
| Scientific Computing | Fast multiplication of very large matrices. |
| Machine Learning | Efficient matrix computations during model training. |
| Image Processing | Performing matrix-based image transformations. |
| Computer Graphics | Matrix transformations for 2D and 3D graphics. |
| Cryptography | Large matrix operations in encryption algorithms. |
Conventional Matrix Multiplication vs Strassen's Algorithm
| Conventional Method | Strassen's Algorithm |
|---|---|
| Uses 8 recursive multiplications. | Uses only 7 recursive multiplications. |
| Time Complexity: O(n³) | Time Complexity: O(n2.81) |
| Easy to implement. | More difficult to implement. |
| Suitable for small matrices. | Suitable for large matrices. |
| Less additional memory. | Requires extra memory. |
Summary
Strassen's Matrix Multiplication is an efficient Divide and Conquer algorithm that reduces the number of recursive multiplications from eight to seven. This optimization decreases the overall time complexity from O(n³) to O(n2.81), making it highly suitable for multiplying large matrices in scientific computing, artificial intelligence, computer graphics and other computationally intensive applications.