Faster matrix-multiplication algorithms found by reinforcement learning
Faster matrix-multiplication algorithms found by reinforcement learning is graded peer reviewed on whataifound.org, with the AI's role graded search scaffold.
AlphaTensor discovered matrix-multiplication schemes using fewer scalar multiplications than any previously known, including a way to multiply 4×4 matrices over GF(2) in 47 multiplications versus the 49 of two-level Strassen.
- Verification
- Peer reviewed
- Autonomy
- Search scaffold
- Lab
- Google DeepMind
- Model
- AlphaTensor (AlphaZero-based)
- Field
- Computer science
- Date
- 2022-10-05
- Problem posed
- 1969 · open 53 yrs
- Notability
- 7 Wikipedia language editions
What was found
AlphaTensor recast the search for matrix-multiplication algorithms as a single-player game of decomposing a 3-D tensor into rank-one terms, then trained an AlphaZero-style agent to play it. It matched or beat the best known rank for many matrix sizes, and over GF(2) found a 4×4 scheme using 47 multiplications, improving on the 49 obtained by applying Strassen's 1969 algorithm twice. Every decomposition it returns is an exact identity checkable by hand. Published in Nature.
Novelty check
Fast matrix multiplication has an exhaustively catalogued literature going back to Strassen (1969) and Laderman (1976). AlphaTensor's schemes were checked against the standing per-size records; the 4×4 result over GF(2) was new at publication.
Caveats
The 4×4 improvement is specific to characteristic-2 arithmetic and the practical speedup is limited. Within about a week, Kauers and Moosbauer used a classical computer search to improve the 5×5 GF(2) case from AlphaTensor's 96 multiplications to 95, showing conventional methods remained competitive. 'Discovered' here means an RL search over decompositions, not an autonomous mathematical insight.
Independent checks
Kauers & Moosbauer (computer-algebra search): verified and shortly improved on the 5×5 case · link ↗
Sources
Community discussion
How this is graded
whataifound.org grades every entry on two axes: verification (how solid the result is, from a machine-checked proof down to refuted) and autonomy (how much the AI did versus its human collaborators). This finding is peer reviewed and search scaffold. Full definitions are in the methodology.
Cite this entry
whataifound.org (2022). Faster matrix-multiplication algorithms found by reinforcement learning. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2022-10-05-alphatensor