Description of fast matrix multiplication algorithm: ⟨4×4×4:48⟩

Algorithm type

16 X^{2} Y^{2} Z^{2} + 32 X Y Z

Algorithm definition

The algorithm ⟨4×4×4:48⟩ is taken from:

Alexander Novikov, Ngân Vũ, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borislav Kozlovskii, Francisco J. R. Ruiz, Abbas Mehrabian, M. Pawan Kumar, Abigail See, Swarat Chaudhuri, George Holland, Alex Davies, Sebastian Nowozin, Pushmeet Kohli, and Matej Balog. AlphaEvolve: A coding agent for scientific and algorithmic discovery. Technical report, Google DeepMind, May 2025. [ .pdf ] [ arXiv ]

Algorithm description

Algorithm symmetries

The following group of 64 isotropies acts as a permutation group on algorithm tensor representation:

maple tensor representation (compressed by bzip2);

These encodings are given in compressed text format using the maple computer algebra system. In each cases, the last line could be understood as a description of the encoding with respect to classical matrix multiplication algorithm. As these outputs are structured, one can construct easily a parser to its favorite format using the maple documentation without this software.

Commentaries

The original algorithm introduced by Novikov et ali (AlphaEvolve 2025) involves complex-valued multiplications.

The variant of this algorithm presented here matches the current best-known tensor rank while removing the reliance on complex coefficients. It is taken from (Dumas, Pernet and Sedoglavic 2025) and its currently best known complexity is $\frac{347}{32} n^{2 + {log}_{4} 3} + o (n^{2 + {log}_{4} 3})$ .

Another more accurate variant is presented in (Dumas, Pernet and Sedoglavic 2026) and its currently best known complexity is $\frac{79}{8} n^{2 + {log}_{4} 3} + o (n^{2 + {log}_{4} 3})$ .