Definition
The Strassen algorithm is a divide-and-conquer method for multiplying two square matrices that reduces the typical $O(n^{3})$ time complexity of conventional matrix multiplication to approximately $O(n^{\log_{2}7}) \approx O(n^{2.81})$. It achieves this improvement by recursively partitioning matrices and computing a set of seven matrix products instead of the usual eight.
Overview
Developed by German mathematician Volker Strassen in 1969, the algorithm was the first to demonstrate that matrix multiplication could be performed in subcubic time. The method operates on two $2^{k} \times 2^{k}$ matrices (or on padded matrices of that size) by dividing each matrix into four equally sized submatrices:
$$ A = \begin{pmatrix}A_{11}&A_{12}\A_{21}&A_{22}\end{pmatrix},\qquad B = \begin{pmatrix}B_{11}&B_{12}\B_{21}&B_{22}\end{pmatrix}. $$
Instead of calculating the eight products $A_{ij}B_{jk}$ required by the standard algorithm, Strassen computes seven auxiliary products $M_{1}$ through $M_{7}$ using specific linear combinations of the submatrices. The resulting subblocks of the product matrix $C = AB$ are then expressed as linear combinations of these seven products. By applying the same procedure recursively to the submatrices, the overall number of scalar multiplications required grows as $7^{\log_{2} n}$, yielding the reduced asymptotic complexity.
In practice, the algorithm is often combined with conventional multiplication for small submatrix sizes, because the overhead of the additional additions and subtractions can outweigh the theoretical speedup for modest $n$.
Etymology/Origin
The algorithm is named after its discoverer, Volker Strassen, who published the result in his 1969 paper “Gaussian Elimination is Not Optimal.” The naming follows a common convention in computer science of attributing algorithms to their originators (e.g., Euclidean algorithm, Dijkstra’s algorithm).
Characteristics
- Complexity: Time complexity $O(n^{\log_{2}7})$; space complexity typically $O(n^{2})$ for storing intermediate submatrices.
- Recursive Structure: Naturally expressed as a recursive function; the recursion depth is $\log_{2} n$.
- Numerical Stability: The algorithm introduces additional rounding errors due to the increased number of addition/subtraction operations, making it less numerically stable than classical multiplication for floating‑point matrices.
- Parallelism: The seven independent products at each recursion level are amenable to parallel execution, which has motivated various parallel and distributed implementations.
- Variants: Subsequent research has produced algorithms that further reduce the exponent (e.g., Coppersmith–Winograd, Le Gall) and practical refinements such as the Strassen–Winograd algorithm, which minimizes the number of addition operations.
Related Topics
- Matrix multiplication
- Divide-and-conquer algorithms
- Computational complexity of linear algebra
- Coppersmith–Winograd algorithm
- Fast Fourier Transform (FFT) based matrix multiplication
- Parallel algorithms for linear algebra
- Numerical stability in matrix computations
References
- Strassen, V. (1969). “Gaussian Elimination is Not Optimal.” Numerische Mathematik, 13, 354–356.
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
- Demmel, J., et al. (2007). “Best Practices for Implementing Fast Matrix Multiplication.” SIAM Review, 49(2), 303–327.