Strassen's matrix multiplication

Multiplying two n-by-n matrices the obvious way computes each of the n^2 output entries as a dot product of length n, costing n^3 scalar multiplications. Strassen's algorithm, from 1969, was the shock result that you can do it with fewer than n^3 operations — applying the same Karatsuba-style trick of buying fewer multiplications with extra additions, but to matrices.

Partition each n-by-n matrix into four (n/2)-by-(n/2) blocks. The block product needs the four output blocks, and computing them the naive way requires EIGHT multiplications of half-size matrices: T(n) = 8 T(n/2) + O(n^2) = O(n^3), no improvement. Strassen found a set of SEVEN cleverly chosen products of sums and differences of the blocks (for example M1 = (A11 + A22)(B11 + B22), and six more like it), from which all four output blocks can be reconstructed using only additions and subtractions. Seven recursive multiplications instead of eight give T(n) = 7 T(n/2) + O(n^2), which the Master Theorem solves to O(n^(log2 7)) = O(n^2.807). The combine step (the O(n^2)) is the matrix additions assembling the result.

Strassen broke the long-assumed n^3 barrier and launched the whole field of fast matrix multiplication; today's theoretical record is around O(n^2.37), though those algorithms are impractical. Strassen itself is used in high-performance libraries for very large matrices. Be honest about the costs: it needs extra memory for the intermediate sums, its many additions hurt numerical stability slightly, and the constant factors mean it only beats the cubic method above a crossover size (often a few hundred rows), below which the simple triple loop wins.