IX · Linear algebra
Matrix multiplication complexity
What it is
Naive: O(n³). Strassen (1969): O(n^2.807). State of the art (Alman-Williams 2024): O(n^2.371). Conjectured exponent ω = 2.
Where it lives
Every neural-net forward pass, every linear regression, every iterative solver. The single most-tuned numerical kernel.
The key insight
GPUs and TPUs achieve their advantage by parallelising matmul. The cuBLAS GEMM kernel hits within 5% of theoretical peak FLOPS on every NVIDIA generation.