Strassen Seven-Product Multiplication
Reconstruct a matrix product from seven carefully combined multiplications.
By Riano · Published · Updated · Report a correction
Strassen Seven-Product Multiplication
Matrix multiplication is famously cubic—multiplying two n×n matrices classically requires eight multiplications for a 2×2 block, scaling as O(n³). In 1969, Volker Strassen discovered a clever algebraic reorganization that computes the product using only seven multiplications, leading to an asymptotic complexity of O(n^log₂(7)) ≈ O(n²·⁸¹).
Reconstructing the Product
Consider the 2×2 matrices A and B. By carefully adding and subtracting the elements of A and B before multiplying, we can form 7 products (M1 through M7). We then combine these 7 products using additions and subtractions to find the four elements of the final matrix C.
| Matrix C Cell | Reconstruction Formula |
|---|---|
| C11 | M1 + M4 - M5 + M7 |
| C12 | M3 + M5 |
| C21 | M2 + M4 |
| C22 | M1 - M2 + M3 + M6 |
Tracing the Algorithm
Use the interactive module to see exactly how the elements of A and B are combined to form the 7 products, and how those products reconstruct C.
- Select the Matrix pair control to choose between General, Signed, Zero, or Identity presets.
- Adjust the Left scale to see how scaling a matrix affects the intermediate products.
- Observe how the 7 products are derived and verify the arithmetic for the reconstruction of C.
Explore the full trace in the Strassen Seven-Product Multiplication module.
Numerical Tradeoffs and Overhead
While Strassen's algorithm reduces the number of multiplications, it significantly increases the number of additions and subtractions (from 4 to 18 for a 2×2 block). On modern hardware, additions are generally faster than multiplications, but the extra operations add significant overhead for small matrices. Therefore, classical multiplication is often faster in practice until the matrices reach a certain size (typically n > 64 or 128), at which point algorithms switch from Strassen back to classical for the smaller sub-blocks. Furthermore, the extra additions can introduce numerical instability and larger rounding errors when dealing with floating-point numbers compared to classical multiplication.
Primary References
For a deeper dive into the algorithm and its derivation, consult the following resources:
- MIT 6.890 Lecture 19: Matrix Multiplication - Detailed lecture notes on the derivation and analysis of Strassen's algorithm.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Strassen Seven-Product Multiplication module.
Try Strassen Seven-Product Multiplication on Riano →