Strassen's algorithm

Strassen’s algorithm

ByAbdul Wahab Junaid

The Strassen algorithm is an efficient algorithm for matrix multiplication that reduces the computational complexity compared to the standard algorithm. It was developed by Volker Strassen in 1969 and is particularly useful for large matrices.

Standard Matrix Multiplication Complexity

The standard method of multiplying two ( n \times n ) matrices requires ( n^3 ) scalar multiplications and ( n^2(n-1) ) additions, resulting in an overall time complexity of ( O(n^3) ).

Strassen’s Algorithm Overview

Strassen’s algorithm reduces the number of multiplications required by recursively dividing the matrices into smaller submatrices. Instead of the usual 8 multiplications used in the standard method, Strassen’s method uses only 7 multiplications, combined with 18 additions and subtractions. This reduces the time complexity to approximately ( O(n^{\log_2 7}) ), which is about ( O(n^{2.81}) ).

How Strassen’s Algorithm Works

For simplicity, consider two ( 2 \times 2 ) matrices ( A ) and ( B ):

[A = \begin{pmatrix} a_{11} & a_{12} \ a_{21} & a_{22} \end{pmatrix}, \quadB = \begin{pmatrix} b_{11} & b_{12} \ b_{21} & b_{22} \end{pmatrix}]

The product matrix ( C = AB ) is:

[C = \begin{pmatrix} c_{11} & c_{12} \ c_{21} & c_{22} \end{pmatrix}]

In the standard algorithm, ( c_{ij} ) is computed as follows:

[c_{11} = a_{11}b_{11} + a_{12}b_{21}]
[c_{12} = a_{11}b_{12} + a_{12}b_{22}]
[c_{21} = a_{21}b_{11} + a_{22}b_{21}]
[c_{22} = a_{21}b_{12} + a_{22}b_{22}]

This requires 4 multiplications and 4 additions.

In contrast, Strassen’s algorithm computes the result using the following 7 products ( P_1 ) to ( P_7 ):

[P_1 = (a_{11} + a_{22})(b_{11} + b_{22})]
[P_2 = (a_{21} + a_{22})b_{11}]
[P_3 = a_{11}(b_{12} - b_{22})]
[P_4 = a_{22}(b_{21} - b_{11})]
[P_5 = (a_{11} + a_{12})b_{22}]
[P_6 = (a_{21} - a_{11})(b_{11} + b_{12})]
[P_7 = (a_{12} - a_{22})(b_{21} + b_{22})]

The elements of the resulting matrix ( C ) are then computed as:

[c_{11} = P_1 + P_4 - P_5 + P_7]
[c_{12} = P_3 + P_5]
[c_{21} = P_2 + P_4]
[c_{22} = P_1 + P_3 - P_2 + P_6]

Recursive Implementation

Strassen’s algorithm is particularly powerful when applied recursively to matrices larger than ( 2 \times 2 ). For larger matrices, the algorithm divides each matrix into four submatrices, each of size ( n/2 \times n/2 ), and then applies the same Strassen multiplication process.

Time Complexity

The time complexity of Strassen’s algorithm is ( O(n^{\log_2 7}) ), which simplifies to approximately ( O(n^{2.81}) ). This is a significant improvement over the standard ( O(n^3) ) complexity, particularly for large matrices.

Practical Considerations

  • Recursive Overhead: For small matrices, the overhead of recursion can make Strassen’s algorithm slower than the standard algorithm. Therefore, it’s often used for large matrices, switching to standard multiplication when submatrices are small.
  • Numerical Stability: Strassen’s algorithm can be less numerically stable compared to the standard method, especially in cases involving floating-point arithmetic.

Applications

Strassen’s algorithm is widely used in applications where matrix multiplication of large matrices is required, such as:

  • Scientific computing
  • Computer graphics
  • Machine learning (e.g., large-scale neural networks)

Summary

Strassen’s algorithm offers a more efficient approach to matrix multiplication by reducing the number of multiplications needed, making it faster for large matrices. However, it requires careful implementation to manage the trade-offs between speed, numerical stability, and recursion overhead.

Discover more from Science blog by awjunaid

Subscribe to get the latest posts sent to your email.

Leave a Reply