Strassen's 7 multiplications vs 8: how matrix multiplication hits O(n^2.81)
Franc0Fernand0 · x · 2026-10-14
Splitting matrix multiplication into blocks doesn't speed it up — removing one multiplication does. Naive multiplication is O(n³); divide-and-conquer still needs 8 sub-multiplications per recursion level, so it stays O(n³). Strassen's algorithm recombines the same blocks with only 7 multiplications per step, dropping complexity to O(n^2.81) — a small constant win that matters greatly at large sizes. The attached image shows the seven product formulas from Strassen's 1969 paper.
More from Research
- RFD4-Proteina's 'underrated' docs detail partial diffusion for protein redesign — AllThingsApx · 2026-10-23
- MPI-Sec PhD Thesis on Vulnerability Detection Benchmarks Includes Pre-LLM Classic "Top Score on the Wrong Exam" — mboehme_ · 2026-10-23
- LiveNerf's 29-day data finds no nerfing of Claude Opus 5.5 — TheOnlyVibemaster · 2026-10-23
- New paper makes 9 falsifiable predictions toward a major AI-enabled terror attack by 2027-2028 — StephenLCasper · 2026-10-23
- HumanoidPose recovers humanoid robots' full-body joint states from RGB video alone — cholz · 2026-10-23
- Sophont's Holon-S1 predicts genes and biomarkers from routine pathology slides — iScienceLuvr · 2026-10-23