Break the cubic barrier of matrix multiplication by computing seven compound products instead of eight.
- Call the number of quadrant products needed to compute a 2×2 matrix before seeing Strassen's formulas
- Trace the seven compound valve products to watch the parasitic cross-terms cancel
- Take the boss round bet on why Winograd's rank-7 theorem proves eight was always a lie
After thisYou will conquer high-dimensional linear algebra, tensor rank decompositions, and the frontier of omega.
Short on timeReview the seven valve formulas in the mental image plate to see how addition cancels the cross-terms.
Seven products that broke the cubic wall
3 minthe hook
At , eight scalar products per block leave leaf products. Seven leave , a 55× saving for the same answer.
In 1968, Volker Strassen set out to prove that Gaussian elimination was optimal. Calculating by hand in Frankfurt, he found seven equations that shattered that assumption instead.
Take two matrices and multiply them both ways.
A = [ 1 2 ] B = [ 5 6 ]
[ 3 4 ] [ 7 8 ]
textbook a·e+b·g a·f+b·h eight products: ae bg af bh ce dg cf dh
c·e+d·g c·f+d·h C = [ 19 22 ]
[ 43 50 ]
Strassen M1 = (1+4)(5+8) = 65 c11 = M1 + M4 - M5 + M7 = 65 + 8 - 24 - 30 = 19
M2 = (3+4)·5 = 35 c12 = M3 + M5 = -2 + 24 = 22
M3 = 1·(6-8) = -2 c21 = M2 + M4 = 35 + 8 = 43
M4 = 4·(7-5) = 8 c22 = M1 - M2 + M3 + M6 = 65 - 35 - 2 + 22 = 50
M5 = (1+2)·8 = 24
M6 = (3-1)(5+6) = 22
M7 = (2-4)(7+8) = -30
Count the multiplication signs. The schoolbook recipe demands eight scalar products; Strassen finds every entry of the output with seven. No intermediate product is recycled from the schoolbook list—every single term is an exotic combination.
The picture is the seven measurements: seven compound products through , four outputs through , and a sign wherever a measurement is added or removed.
You need four numbers for the output matrix C. Each entry is an inner product of two 2-vectors, requiring 2 multiplications, giving 4 × 2 = 8. How can seven scalar products possibly compute four independent outputs?
That single missing product is the entire engine of the revolution. Everything that follows unfolds when you apply that decrement recursively to half-size blocks.
NextWhy does standard matrix multiplication require eight multiplications for 2×2 blocks?
The fallacy of the loop reorder
2 minthe trap
The schoolbook algorithm is defined by the triple loop: c[i][j] += a[i][k] * b[k][j] across all i, j, k. It spends multiplications and additions.
Programmers often suspect loop reordering, cache blocking, or vectorization could lower the multiplication count. But reordering terms can never change their quantity: each of the eight index triples still demands an independent product .
To beat , you must abandon the requirement that factors are individual matrix entries. The true question permits factors to be any linear combinations of entries, asking for the minimum number of products whose linear combination yields .
NextHow does Strassen's rank-7 tensor decomposition compute 2×2 products using seven multiplications?
Bilinear maps and the hidden tensor rank
2 minthe invariant
Fix a field and a size . Matrix multiplication is the bilinear map:
Bilinear means linear in each argument separately. Every bilinear map can be written as a structure tensor, an array of coefficients describing how each monomial contributes to each output entry .
For matrix multiplication, the tensor is a sum of rank-one components:
At , this sum has eight terms, representing the textbook algorithm. The tensor rank is the fewest rank-one tensors needed to sum to :
Vector forms a linear combination of entries from , from , and directs where their product lands in . Thus, an -term decomposition is an algorithm using scalar multiplications. The minimum multiplication count is identical to tensor rank.
NextHow does the recurrence drop the matrix multiplication exponent from 3 to 2.807?
The seven identities and the Winograd floor
2 minthe algebra
For general blocks, Strassen’s seven products are:
The four output entries recombine these products using additions and subtractions:
Expand and watch the unwanted cross-terms evaporate: , , , and all cancel out in pairs. What survives is , the exact inner product required.
Winograd (1971) proved that seven products are an absolute mathematical floor. No bilinear algorithm can multiply two matrices with six products. Therefore, exactly.
Strassen trades 1 fewer multiplication for 18 additions (which Winograd later trimmed to 15). At large n, won't the avalanche of additions wipe out the savings?
Because tensor rank is submultiplicative (), recursing on half-size blocks yields:
The recurrence relation is:
Since , the master theorem places this firmly in the leaf-dominated case:
| n | log n | note |
|---|---|---|
| 2¹⁰ | 10 | 8¹⁰ = 1.07×10⁹ against 7¹⁰ = 2.8×10⁸ (3.8× fewer) |
| 2²⁰ | 20 | 1.2×10¹⁸ against 8.0×10¹⁶ (14× fewer) |
| 2³⁰ | 30 | 1.2×10²⁷ against 2.3×10²⁵ (55× fewer) |
| 2⁴⁰ | 40 | 1.3×10³⁶ against 6.3×10³³ (208× fewer) |
Scalar products for a full recursion down to scalars, 8^k against 7^k at n = 2^k. The log n column is the recursion depth k, one level per halving. Additions and classical base cases are omitted.
Emphasised column: log n · highlighted row: n = 2³⁰
Notice how the gap widens by every ten doublings. That multiplying advantage is the entire difference between an exponent of 3 and 2.807.
NextWhy does Winograd's theorem prove that rank 7 is the absolute theoretical minimum for 2×2 matrices?
The cascade: how one missing product bends the exponent
2 minthe simulation
Inspect the recurrence visually. At , , and , the leaves outrun the root overhead.
T(n) = 7·T(n/2) + n2 — seven half-size products, plus the additions at each node
Levels with more than 40 nodes are drawn as a band marked ×count rather than one dot per node.
Geometric sum: Σk=0…4 ak·(n/bk)d = nd · Σ rk = nd·(rL+1−1)/(r−1) = 5,261 (closed form 5,261)
n = bL = 16, L = 4, logb a = 2.80735, d = 2, r = a/bd = 1.75. The heaviest level is k = 4.
Leaf-dominated: T(n) = Θ(n^{log_b a}) = Θ(n^{2.807})
log_b a = 2.807 > d = 2. Each level multiplies its work by r = a/b^d = 1.75 > 1, so the level totals grow geometrically and the deepest (leaf) level holds the most. The leaves dominate.
- logb a > d — leaf-dominated, T(n) = Θ(nlogb a)
- logb a = d — balanced, T(n) = Θ(nd log n)
- logb a < d — root-dominated, T(n) = Θ(nd)
The panel opens on a = 7, the value Strassen's rank gives. Drag a to 8 to see the schoolbook cubic wall Θ(n³). Drag a down to 4 to see the balanced Θ(n² log n) threshold, or raise d to 3 to see the additions dominate.
Watch a: drag it from 7 to 8 and the leaf count jumps at every level, because the seven-product identity is exact, not an approximation.
Level holds subproblems of size , each costing addition work. The work per level grows by each step down, making the bottom level the heaviest.
Drag the -slider from 7 to 8. The printed asymptotic jumps from straight to . That single tick of the slider captures the whole gulf between Strassen and three centuries of matrix algebra.
Now slide down to 4. Because matches , every level does equal work, yielding .
NextWhat numerical stability and cache memory crossovers govern Strassen's use in deep learning?
The price of speed: precision and practical crossover
2 minsystems
Speed is not free. Strassen’s algorithm introduces numerical subtraction of large, nearly equal intermediate terms.
1 minboss round
Strassen's recurrence gives Θ(n^2.807) operations. Why do high-performance libraries (like BLAS) still use the classical cubic loop for matrices smaller than n ≈ 512?
Over exact algebraic structures—like finite fields in cryptography or modular arithmetic in computer algebra—rounding errors do not exist. In those domains, the rank drop is pure gain.
Every modern high-performance implementation runs a hybrid: recurse using Strassen for massive blocks, then transition to classical cubic GEMM once blocks fit inside L1/L2 cache.
The unfinished race for omega
Matrix multiplication is the universal engine of computational mathematics. Inversion, determinants, and LUP decomposition all share the exact same asymptotic complexity exponent :
The trivial boundaries are : reading the inputs requires steps, while the textbook loop takes . Strassen proved .
For fifty years, mathematicians have hunted for lower-rank tensor decompositions of larger blocks. Coppersmith and Winograd (1990) used the laser method on arithmetic progressions to prove . Alman and Williams (2021) trimmed this to .
Yet those modern constructions are purely galactic: their hidden constants are so colossal that they would only surpass Strassen on matrices larger than the observable universe. Strassen’s algorithm remains the only sub-cubic method fast enough to run on real hardware.
Historical provenance and attributions
- Strassen 1969 — Gaussian elimination is not optimal: introduced the 7-product identity, established , and reduced inversion and determinants to matrix multiplication.
- Winograd 1971 — On multiplication of 2×2 matrices: proved is minimal, and constructed the 15-addition variant.
- Coppersmith and Winograd 1990 — Matrix multiplication via arithmetic progressions: proved , standing as the frontier for two decades.
- Alman and Williams 2021 — A refined laser method and faster matrix multiplication: advanced the theoretical bound to .
- Higham 2002 — Accuracy and Stability of Numerical Algorithms, §23.2: authoritative numerical stability analysis of Strassen’s recurrence.
- Huang, Smith, Henry and van de Geijn 2016 — Strassen’s Algorithm for Matrix Multiplication: empirical benchmarks pinning down practical crossover points on contemporary architectures.