Strassen’s 1969 Algorithm: A Breakthrough in Matrix Multiplication

Introduction: Matrix Multiplication in the 1960s

Matrix multiplication – computing the product of two tables of numbers – is a fundamental operation in mathematics and computing. The process involves combining rows of one matrix with columns of another, and the straightforward “schoolbook” method requires on the order of n³ arithmetic operations for two n×n matrices. For decades, this cubic time complexity was taken for granted. In practical terms, as matrix sizes grew, the number of calculations exploded – a serious concern in the 1960s when computers were slow and expensive. Improving the efficiency of matrix multiplication was not an idle curiosity: it promised benefits across scientific computing, engineering, economics, and other fields that rely on heavy linear algebra. In that era of limited computing power, even a small reduction in the exponent of complexity could make previously infeasible computations attainable.

By the mid-20th century, matrix multiplication’s Θ(n³) algorithm had been taught and used for generations, much like long multiplication for numbers. Many believed this was essentially the best one could do – after all, every element of the result seemed to require pairing up entire rows and columns. The prevailing sentiment was that “no shortcut” existed, an assumption comparable to a famous conjecture made in 1956 by mathematician Andrey Kolmogorov about multiplying numbers. (Kolmogorov had guessed the standard grade-school method for multiplying two numbers was optimal, only to be proven spectacularly wrong a few years later by Anatoly Karatsuba’s 1962 algorithm that beat the quadratic time barrier. This served as a timely reminder that even entrenched beliefs about computational complexity could crumble.) In the 1960s, a similar question loomed for matrices: Could one do better than n³? The answer, as it would turn out in 1969, was yes – and it arrived as a shock to the mathematical and computing community.

Historical Background: Challenging the Cubic Barrier

Leading up to the late 1960s, the field of algorithm analysis was just beginning to blossom. Researchers were starting to formalize the idea of algorithmic complexity and to seek more efficient methods for fundamental problems. Early hints that “obvious” algorithms might be improved came from outside linear algebra – notably, Karatsuba’s fast integer multiplication method (published in 1962) showed that multiplying two large numbers didn’t actually require Θ(n²) single-digit multiplications as long thought. This breakthrough primed the intellectual atmosphere: if multiplication of one-dimensional numbers could be accelerated, perhaps the two-dimensional case of matrix multiplication also held hidden shortcuts. Still, no one had explicitly demonstrated a faster-than-cubic matrix multiply. The task was daunting; it wasn’t even clear where to begin, since multiplying matrices seemed to inherently demand combining every pair of entries across rows and columns.

Against this backdrop, the work of a German mathematician named Volker Strassen emerged. Strassen, born in 1936, was an eclectic thinker who had started his career in areas like probability theory and information theory. By the late 1960s, he was a professor at the University of Zürich and had begun turning his attention to computational problems. In 1968, Strassen approached the matrix multiplication question from a skeptical angle: he actually set out to prove that the standard algorithm’s n³ operations were optimal – in other words, that no method could use fewer multiplications. He attempted to verify this at least for the simplest nontrivial case (2×2 matrices) as a sub-problem. It was a reasonable conjecture for the time; even Strassen expected to confirm the impossibility of improvement. Instead, to his surprise, he discovered the opposite: a clever way to multiply 2×2 blocks using only 7 multiplications instead of the usual 8. In Strassen’s own words, his attempt at an impossibility proof turned into a “spectacular failure” – the good kind of failure, which opened up a whole new area of research.

When Strassen published his result in 1969, it landed like a bombshell. He famously titled the paper “Gaussian Elimination is not Optimal”, a nod to the fact that the standard method for solving linear systems (which entails matrix multiplication) could be beaten. This bold title encapsulated the paradigm shift: the O(n³) barrier had been broken. Perhaps the first real shock in algorithmic complexity theory, Strassen’s discovery overturned a long-held assumption and demonstrated that matrix multiplication could be done in roughly O(n^{2.81}) time instead of O(n³). As one historical account put it, “the first real surprise in algorithm analysis” was Strassen’s new method. Colleagues quickly recognized the significance: if you could shave off even a constant fraction of the work required for basic operations, it would reverberate through all of computational mathematics. Strassen’s algorithm showed definitively that many fundamental computations might be ripe for improvement, sparking an intensive race to push the complexity even lower.

It’s worth noting that despite its asymptotic advantage, Strassen’s method was not immediately advantageous for every problem size. The algorithm had more intricate logic and a larger constant overhead (due to extra addition steps) than the naive approach. In fact, for small matrices the classic method is often faster, and only beyond a certain matrix dimension does Strassen’s algorithm pull ahead. Early analyses pegged this crossover point at around n ≈ 64 or more on 1970s hardware, though modern implementations often see benefits for n on the order of a few hundred. In practice, however, this threshold is easily surpassed in applications that use very large matrices. Consequently, within a few years of its publication, Strassen’s algorithm found its way into computational libraries and became a standard tool for large-scale linear algebra. The sheer surprise of the result also had an enduring educational impact – today, “few students in computer science have not encountered Strassen’s multiplication algorithm in their undergraduate program” as a classic example of clever algorithm design.

The 1969 Breakthrough: Volker Strassen’s Story

Volker Strassen’s journey to the fast matrix multiplication algorithm is a tale of intellectual curiosity and serendipity. Strassen was not originally an “algorithms guy” by training – in the early 1960s he was publishing in mathematical statistics (he formulated a famous result in probability, the Strassen invariance principle, and the so-called law of the iterated logarithm). After stints in academia in Germany and the United States, he shifted toward theoretical computer science in the late ’60s, intrigued by questions of computational complexity. The matrix multiplication problem attracted him as a fundamental challenge: it sat at the intersection of pure math (algebra) and the practical realities of computation. As mentioned, Strassen initially approached the problem by assuming the conventional wisdom was true – that is, assuming any correct algorithm must perform at least n³ scalar multiplications. He examined the simplest case (2×2 matrices multiplied by 2×2 matrices) to see if he could formally prove no algorithm could use fewer than 8 multiplications for that task. To his great surprise, during this investigation he discovered a set of equations that accomplished the 2×2 multiplication with only 7 multiplications. In essence, Strassen found a shortcut where none was expected. It was as if a magician had shown that you could tear one card less from a deck and still complete the trick – a result no one in the audience anticipated.

Strassen’s method hinged on a clever use of algebraic identities. He realized that by adding and subtracting certain submatrices of the inputs in advance, one multiplication could be “reused” to contribute to two parts of the result, thus saving a whole multiplication at the cost of a few extra additions. Once he found this key insight for 2×2 blocks, he generalized it recursively to handle larger matrices. When he announced the result, it was met with both astonishment and excitement. Here was a clear refutation of the assumed optimality of Gaussian elimination-based methods. The paper “Gaussian Elimination is not Optimal” (Numerische Mathematik, 1969) was only a few pages long, but its content was revolutionary. It demonstrated a concrete algorithm for any n×n matrix multiplication that would asymptotically beat the conventional method. For large n, the new algorithm would perform significantly fewer operations than n³. As Strassen showed, for n > 654 the new method uses fewer total arithmetic operations than the classic method (accounting for both multiplication and addition operations). In practical terms, the break-even point can be much smaller with optimized implementations.

The significance of Strassen’s discovery was immediately recognized. Not only did it make certain large computations faster, but it also transformed a theoretical landscape. It proved that the exponent of matrix multiplication (sometimes called ω) was not 3 or more, but at most ~2.8074 (since log₂7 ≈ 2.8074). This raised a profound question: what is the true minimal exponent? Could it be 2 (which would mean matrix multiplication is as fast – up to constant factors – as matrix addition, an astounding possibility), or something in between 2 and 3? Strassen’s result opened the door to investigating this mystery. As one retrospective note observed, his work “touched off an intensive search for asymptotically better matrix multiplication algorithms”. In the years that followed, dozens of computer scientists and mathematicians set their sights on whittling down the exponent further – a quest directly ignited by Strassen’s 1969 paper. Volker Strassen himself instantly became a notable figure in computer science. He would go on to receive multiple honors, including the ACM Knuth Prize, for his contributions to algorithms. The award citations praise how his “innovations enabled fast and efficient computer algorithms” and note that his discoveries “opened up new areas” of research. Indeed, Strassen is often regarded as a founding father of algebraic complexity theory – the field that studies the inherent complexity of algebraic computations like matrix multiplication and convolution.

How Strassen’s Algorithm Works (Divide-and-Conquer Magic)

At its core, Strassen’s algorithm is a divide-and-conquer technique that cleverly reduces the number of multiplications needed to multiply matrices, at the expense of a slight increase in addition operations. To understand how it works, let’s first consider how the naive algorithm multiplies two 2×2 matrices. Suppose we have: ··· $A = \begin{pmatrix} a & b \\ c & d \end{pmatrix}, \qquad B = \begin{pmatrix} e & f \\ g & h \end{pmatrix},$ ··· where a, b, c, d and e, f, g, h can themselves be numbers or submatrices (we’ll treat them as single elements for now). The standard multiplication rule gives the 2×2 product $C = A \times B = \begin{pmatrix} r_{11} & r_{12} \\ r_{21} & r_{22} \end{pmatrix}$ as:

$r_{11} = a \times e + b \times g$
$r_{12} = a \times f + b \times h$
$r_{21} = c \times e + d \times g$
$r_{22} = c \times f + d \times h$ .

This method uses 8 multiplications (each term like $a \times e$ is a multiplication) and 4 additions to compute the four entries of C. Strassen’s insight was that the same result can be obtained with only 7 multiplications, by computing certain blended quantities that can be combined to yield all $r_{ij}$ . He devised seven intermediate products (often denoted $M_1$ through $M_7$ ) as follows:

M1 = (a + d) × (e + h)
M2 = (c + d) × e
M3 = a × (f – h)
M4 = d × (g – e)
M5 = (a + b) × h
M6 = (c – a) × (e + f)
M7 = (b – d) × (g + h)

Each M_i is itself a multiplication of two numbers (or submatrices). Remarkably, with these seven products computed, one can then combine them (using addition and subtraction) to get the final entries of C:

$r_{11} = M1 + M4 - M5 + M7$
$r_{12} = M3 + M5$
$r_{21} = M2 + M4$
$r_{22} = M1 - M2 + M3 + M6$ .

One can verify that these formulas for $r_{11}, r_{12}, r_{21}, r_{22}$ indeed simplify to the standard results given earlier for the naive method. In other words, the combination of $M1 \ldots M7$ above is algebraically equivalent to the 8 products $a e, b g, a f, b h, c e, d g, c f, d h$ that we would normally compute – it’s just a different way of “packaging” the arithmetic. The advantage is that we had to perform only 7 multiplications instead of 8. The trade-off is that we introduced more additions and subtractions (notice we computed various sums and differences like a + d, f – h, etc., and then again added/subtracted the M’s to get results). Strassen’s original version uses 18 addition/subtraction operations in total to pull off this trick. (Subsequent refinements by Shmuel Winograd in 1971 reduced the number of extra additions to 15 while still using 7 multiplications, making the scheme even more efficient in practice.) The key point, however, is that for large matrices, multiplications are typically much more expensive than additions, so a reduction in the number of multiplications has an outsized benefit.

Strassen’s Algorithm

Visualization of Strassen’s 2×2 block multiplication scheme. The leftmost column (labeled with C₁₁, C₁₂, etc.) shows which combinations of the input submatrices contribute to each entry of the result in a normal 2×2 matrix multiplication (green indicates a multiplication that adds to an entry, red a subtraction). The other seven columns correspond to the 7 products in Strassen’s algorithm (M1 through M7), each yielding a mix of terms that will be added or subtracted (as indicated by green and red cells) to form the result. By summing the matrices in columns M1–M7, one recovers the full product matrix with only 7 multiplications instead of 8.

Strassen’s algorithm generalizes this idea to larger matrices by recursive application. If we need to multiply two n×n matrices, we: (1) recursively split each matrix into four n/2 × n/2 submatrices (assume n is a power of 2 for simplicity; if not, we can pad with zeroes), (2) use the above 7-multiplication procedure to compute the product of these block matrices, and (3) combine the results appropriately. In each recursion level, the number of submatrix multiplications is cut down to 7 for what would have been 8 in a naive divide-and-conquer approach. This yields the famous recurrence for the time complexity:

$T(n) = 7\,T(n/2) + O(n^2),$

which by the Master Theorem solves to $T(n) = O(n^{\log_2 7}) ≈ O(n^{2.8074})$ . In contrast, the standard method would give $(T(n) = 8\,T(n/2) + O(n^2)$ , resolving to $O(n^3)$ . Thus, Strassen’s algorithm proved that matrix multiplication can be done in sub-cubic time. For large n, the difference is dramatic: an O(n^2.81) algorithm will outperform an O(n^3) algorithm by arbitrarily large factors as n grows (since $n^{2.81}$ grows slower than $n^3$ ). Even for moderate-sized matrices, the reduction in exponent translates to noticeable speedups. Empirically, one typically switches to Strassen’s method when matrix sizes exceed a certain threshold (to overcome the overhead of the extra additions and recursive structure). That threshold might be on the order of a few tens or hundreds, depending on hardware and implementation. Beyond that point, Strassen’s algorithm “wins” and yields faster execution than the classical method. Indeed, it has been implemented in optimized numerical linear algebra libraries and is used for multiplying large dense matrices in practice. (One must be a bit careful when using Strassen’s method in numerical computations with floating-point numbers – the reordering of operations can introduce slightly larger numerical errors or stability issues in some cases. However, for many applications and certainly for exact arithmetic over integers or finite fields, these concerns are not problematic.)

The beauty of Strassen’s algorithm is how it balances simplicity with ingenuity. On one hand, the idea can be explained with basic algebra, as above, and doesn’t require advanced mathematics to grasp. On the other hand, coming up with those 7 products and their combinations was anything but obvious – it required a leap of insight. This divide-and-conquer trick became a template for a whole genre of “fast algorithms” in later years. For example, Strassen’s approach is analogous to Karatsuba’s method (which splits numbers and uses a clever recombination to reduce multiplications), and it foreshadowed the development of many other algorithms where a problem is split into parts that are solved with fewer recursive sub-calls than a brute-force divide-and-conquer would use.

Aftermath and Legacy: Strassen’s Impact on Computing

Strassen’s 1969 breakthrough did not end the story – in fact, it was just the beginning of a long quest to further speed up matrix multiplication. His result immediately “touched off an intensive search” for algorithms with an even lower complexity exponent. In the ensuing years and decades, researchers devised a succession of ever-faster (and increasingly complex) matrix multiplication algorithms. Only two years after Strassen, Shmuel Winograd in 1971 refined the 2×2 method’s addition steps as mentioned, and also proved theoretical limits for how much one could reduce additions for a given multiplication count. In 1973, the trio of Pan, Bini, and others began publishing methods to multiply larger blocks (beyond 2×2), pushing the exponent down further (albeit with diminishing returns). A major milestone came in 1987 when Coppersmith and Winograd developed an algorithm with exponent ≈ 2.376. This stood as the record for over two decades. In the 2010s, a flurry of breakthroughs by Stothers, Vassilevska Williams, Le Gall, and others shaved the exponent slightly more, to the current state-of-the-art exponent of about 2.371552. As of 2025, the best announced upper bound on matrix multiplication’s complexity is $O(n^{2.3715})$ – substantially better than Strassen’s 2.807, yet still above the theoretical floor of 2. The optimal exponent (often denoted ω) remains unknown. In other words, we don’t yet know how fast matrix multiplication can be in principle, but thanks to Strassen we know it’s at most ~2.37 and not 3. Some experts conjecture that ω might be 2 (meaning an algorithm exists that is nearly linear in the amount of data), while others suspect there’s a barrier >2. The problem of determining or reducing ω is one of the great challenges in theoretical computer science.

It’s important to note that many of the ultra-fast matrix multiplication algorithms (those improving on Strassen) are galactic algorithms – a nickname for algorithms that are optimal asymptotically but impractical for any feasible matrix size due to huge hidden constants or very complicated steps. For instance, the Coppersmith-Winograd algorithm and its successors are rarely used in real-world applications; they’re more of theoretical interest unless one is multiplying matrices that are astronomically large. In contrast, Strassen’s algorithm strikes a useful balance between theory and practice. It offers a tangible speedup for moderately large matrices without exorbitant overhead, which is why it has been incorporated into software libraries and even hardware-optimized routines. In domains like large-scale simulations, graphics, and machine learning (where one might multiply very large matrices), Strassen’s method can provide noticeable performance gains. It’s telling that even over 50 years later, Strassen’s 7-multiplication idea is still a “method of choice” for dense matrix multiplication beyond a certain size on modern machines.

Beyond the specific algorithm, Volker Strassen’s work had a profound conceptual impact. It introduced the world to the idea of algebraic complexity: studying how many algebraic operations (like additions and multiplications) are intrinsically required to compute something. This spawned a rich field of research. Strassen himself continued to be a leader in this area – in 1971 he co-developed the Schönhage–Strassen algorithm for fast integer multiplication (achieving near-linear time multiplication of huge numbers, a record that stood for decades), and in 1977 he co-introduced the Solovay–Strassen primality test, one of the first efficient randomized algorithms for testing prime numbers. These achievements underscore a career devoted to finding speed-ups for fundamental computations. For his contributions, Strassen received numerous accolades, and in the citations he is lauded for “groundbreaking” work linking mathematics and computing, and for algorithms that “resulted in some of the most important algorithms used today”. In particular, the 2008 ACM Knuth Prize highlighted how Strassen’s matrix multiplication and related innovations “fundamentally altered” the landscape of computer algorithms.

To this day, the legacy of Strassen’s 1969 algorithm is evident. Every computer science student learns of it as a tour-de-force example of creative thinking in algorithms, often marveling at how such a simple rearrangement of terms yields such a big savings. Researchers building on Strassen’s idea have formed a long lineage of improvements – a true testament to the depth of the discovery. And intriguingly, the final chapter is not yet written: the race towards the elusive O(n²) matrix multiply continues, with occasional breakthroughs (even AI has been recently deployed to search for new multiplication schemes) building on the foundations Strassen laid.

In closing, Strassen’s algorithm is far more than just a faster way to multiply matrices – it’s a case study in innovative problem-solving. It teaches us that by challenging assumptions and cleverly re-examining a problem, we can sometimes achieve what experts thought impossible. This message resonates beyond mathematics: the pursuit of knowledge and self-improvement often involves questioning the “obvious” and thinking outside the box. Volker Strassen’s 1969 breakthrough remains a shining example of how human ingenuity can redefine the limits of computation, and its story continues to inspire new generations of learners in mathematics and computer science.

2025 Milestone: AlphaEvolve Pushes Strassen’s Legacy Forward

Strassen showed in 1969 that a 4 × 4 matrix product could be done with 49 multiplications (7 for each 2 × 2 block), already far below the naïve 64. For more than half a century no general-field algorithm did better.

DeepMind’s AlphaEvolve—an LLM-driven evolutionary search system—discovered a 48-multiplication routine for the same task, trimming the count by a crucial single multiply. Although the numerical gap seems small, complexity theorists note that shaving even one multiplication from such a tiny instance had resisted exhaustive human effort since Strassen’s paper.

The new algorithm works over any characteristic-0 field (hence over the complex numbers) and closes an open question highlighted in numerous surveys of algebraic complexity. AlphaEvolve also improved best-known formulas in 14 other small-matrix settings, but the 4 × 4 complex case is its headline achievement because it dethroned the longest-standing Strassen-derived record.

How AlphaEvolve Builds on Strassen’s Ideas

Strassen as the baseline. AlphaEvolve starts its evolutionary search from human-crafted seeds—chiefly Strassen-style recursive decompositions—then mutates and recombines them, scoring candidates by the number of multiplications they need. Thus Strassen’s 7-multiplication template remains the genetic “primordial soup” for AI exploration.
Divide-and-conquer DNA. The new 48-multiplication circuit still follows Strassen’s divide-merge philosophy; what changes is the algebraic identity mix that lets one multiplication serve multiple sub-entries. In essence, the AI found a subtler way to reuse products—precisely the trick Strassen pioneered in 1969.
Automated verification. Researchers have published independent code that reconstructs and checks the 48-step schedule symbolically, confirming its correctness and reproducibility—just as mathematicians verified Strassen’s 7-product scheme decades ago.

Why One Multiply Matters

For practical HPC libraries the constant factors still favour Strassen (or Winograd-Strassen) for moderate matrix sizes, but the symbolic victory is profound: it demonstrates that human-optimal may no longer be AI-optimal, validating Strassen’s deeper message that “obvious” lower bounds can fall. Commentators across specialist forums hailed the result as “insane” and “historic,” emphasising how it reignites the race toward the elusive ω = 2 frontier.

Broader Implications

Algorithm-design automation. AlphaEvolve’s success suggests that many other Strassen-inspired open problems—e.g., tighter bounds for 5 × 5 or for rectangular matrices—may be tractable to AI search. This could accelerate discovery cycles that once spanned decades.
Educational echo. Just as every CS curriculum teaches Strassen’s 2 × 2 trick, the 48-step 4 × 4 schedule is poised to enter textbooks as the first AI-discovered improvement on a classical algorithm, offering a fresh classroom showcase of algebraic creativity.
Continuity of influence. Volker Strassen’s conceptual framework remains the lingua franca of matrix-multiplication research; even state-of-the-art AI “thinks” within the boundaries he established. In that sense, Strassen’s impact is not only historical—it is the coordinate system for future breakthroughs.

Takeaway

More than half a century after Strassen shocked the community with 7 instead of 8, the quest he ignited has leapt forward again—this time with an AI agent trimming the 4 × 4 count to 48. Both events share a common moral: complexity frontiers move when someone dares to look for the unlikely shortcut. Strassen taught us to expect the unexpected; AlphaEvolve just proved we still should.