◄ WORLD V · SONNY 5DART 081 · a helldive at the net

STRASSEN'S ALGORITHM seven multiplications where eight seemed required

Multiply two 2×2 matrices and you seem to need eight scalar multiplications. Strassen found a way with seven — and because you can apply it recursively to blocks, matrix multiplication drops from n3 to about n2.807. It was the shock that opened the whole field of fast matrix multiplication, still open today.

THE TECHNIQUE seven products, then recombine

From the eight entries of A and B, form seven cleverly chosen products M1..M7 (each one multiplication of two sums/differences), then add and subtract them to get the four entries of C — using only 7 multiplications instead of 8, at the cost of more additions. Edit the matrices; the seven products and the result update live. live demo

HISTORY & CREDIT he set out to prove it impossible

“Strassen set out to speed matrix multiply and proved 7 is optimal” — he was trying to prove 8 is optimal, and it was Winograd who proved 7 is the floor. cited

1968–69 · Volker Strassen, while trying to show 8 multiplications are necessary, finds 7 instead (“Gaussian elimination is not optimal,” Numer. Math. 13:354–356). O(n2.807).
1971 · Shmuel Winograd proves 6 is impossible — 7 is optimal for 2×2. The lower bound is his, not Strassen’s.
the coded version · the popular 7-mult / 15-addition form is Winograd’s variant; Strassen’s original used 18 additions. Fairly it is Strassen–Winograd.
the retrofit · “Strassen was inspired by Karatsuba” (dart 041) is a modern teaching analogy — the 1969 paper cites no such influence. The kinship is real; the direct-inspiration story is not documented.

The best possible exponent for matrix multiply is a famous open problem — still creeping toward 2. Strassen 1969, bound Winograd 1971

RECOMMEND FOR I-13 seven scalar products, on the array

The seven products are pure scalar arithmetic; the matrices are 2-D arrays — and it runs bit-for-bit like the schoolbook product:

$ i13 run strassen.i13 # [[1,2],[3,4]] x [[5,6],[7,8]] m1=65 ... m7=-30 -> C = [[19,22],[43,50]] # identical to the 8-mult product, with 7
Recommend: the seven products and the recombination are add/subtract/multiply — the grounded run gives the exact matrix. The natural container is a 2-D array (a matrix), PS-004 again; today the 4 entries live in a flat length-4 array, and recursion on blocks would use index arithmetic. It is the matrix analogue of Karatsuba (041): both buy a cheaper multiply with extra additions.
Note: a genuine 2-D array (or arrays-of-arrays) would let the recursive block form read verbatim — the strongest single case yet for PS-004.