Volker Strassen and the Shock of Subcubic Matrix Multiplication
Volker Strassen’s 1969 algorithm showed that ordinary cubic matrix multiplication was not asymptotically optimal, opening a long-running search for faster algebraic algorithms and changing complexity theory’s expectations.
Matrix multiplication looked cubic because the obvious algorithm was cubic
Multiplying two n by n matrices in the straightforward way computes n squared output entries, each as an inner product of length n. That leads naturally to a running time proportional to n cubed, and for many years the procedure looked so fundamental that the exponent could seem built into the operation itself.
Volker Strassen’s 1969 result broke that intuition.
Strassen showed that Gaussian elimination was not asymptotically optimal
His short paper, “Gaussian elimination is not optimal,” appeared in Numerische Mathematik in 1969.[1] The title reflected a broader consequence: a faster matrix multiplication method could also accelerate related linear-algebra operations such as inversion and solving systems under suitable reductions.
The historical shock was not a small constant-factor optimization. It was a proof that the familiar cubic exponent was not a lower bound.
Seven recursive products replace eight
For 2 by 2 block matrices, the naive recursive scheme performs eight block multiplications. Strassen found algebraic combinations that require only seven, paying for the saved multiplication with additional additions and subtractions.
Recursion turns one saved multiplication into a new exponent
Applying the seven-product construction recursively yields a running time proportional to n raised to log base 2 of 7, approximately n^2.807. The original paper states a bound below the cubic cost of conventional multiplication.[1]
The improvement becomes asymptotically larger as n grows because the exponent itself has changed.
The result taught algorithm designers to question “obvious” arithmetic counts
The usual formula described one way to multiply matrices, not the unique way. Strassen’s construction showed that algebraic rearrangement could reduce the number of expensive bilinear products.
The algorithm connected numerical linear algebra to complexity theory
Later collections of classic computer-science papers treat Strassen’s result as a turning point because it reframed matrix multiplication as a complexity frontier rather than a settled primitive.[2]
Researchers began asking for the smallest possible exponent ω such that matrix multiplication can be performed in roughly O(n^ω) operations.
Later algorithms pushed the theoretical exponent lower
Work by researchers including Don Coppersmith and Shmuel Winograd developed increasingly sophisticated constructions with better asymptotic bounds.[3] These methods are mathematically important even when their constants and complexity make them unattractive for ordinary software.
The history therefore split into two tracks: algorithms that improve the theoretical exponent and implementations that improve actual matrix multiplication on real hardware.
Asymptotic superiority does not guarantee practical superiority at modest sizes
Strassen-style recursion creates extra additions, temporary storage and data movement, and it can interact with floating-point error. High-performance libraries therefore use thresholds, blocked layouts and hardware-aware kernels rather than blindly recursing to scalar size.
Numerical stability became part of the engineering discussion
Matrix algorithms operate on finite-precision numbers, so arithmetic count is only one measure of quality. Faster multiplication can change how rounding errors accumulate, and practical implementations must balance speed, memory traffic and numerical behavior.
This is a recurring lesson in scientific computing: the mathematically fastest operation count may not be the best implementation for a particular machine or accuracy requirement.
Matrix multiplication is a systems problem as well as an algebra problem
Modern processors make memory hierarchy, vector units and accelerators central to performance. A theoretically slower algorithm with better locality can beat an asymptotically faster one in the range that applications actually use.
The search for new multiplication algorithms is still active
IBM’s historical research record on matrix multiplication documents later advances in the exponent, while recent work such as AlphaTensor used machine learning to discover exact multiplication schemes for specific matrix sizes.[3][4] Nature’s discussion of AlphaTensor explicitly places the new work in the lineage that begins with Strassen.[5]
The persistence of the problem shows how one 1969 result created a research program rather than closing a question.
Why Strassen belongs in the CodeHistory timeline
Strassen changed the intellectual status of a basic operation. Matrix multiplication went from “obviously cubic” to a central open problem in algorithmic complexity.[1]
His deeper legacy is methodological: when an algorithm seems forced by the definition of a problem, it may still be worth searching for an alternative algebraic representation that performs less work.
Works Cited
- 01
- 02
- 03IBM Research — Matrix Multiplication via Arithmetic Progressions research.ibm.com
- 04
- 05
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead