Noncommutative Bilinear Algorithms for $3 \times 3$ Matrix Multiplication
Rodney W. Johnson, Aileen M. McLoughlin · SIAM Journal on Computing · 1986
New noncommutative bilinear algorithms for $3 \times 3$ matrix multiplication are presented. These have the same complexity, 23 essential multiplications, as the one discovered by Laderman, but are inequivalent to it. Equivalence here refers to a certain group of transformations all of which map noncommutative bilinear matrix-multiplication algorithms into other such algorithms; “inequivalent” means not related by a transformation in the group. This group has been studied by de Groote, who has shown for the case of $2 \times 2$ matrix multiplication with 7 essential multiplications that all such algorithms are equivalent to Strassen’s. The new algorithms, by contrast, include infinitely many pairwise inequivalent algorithms. The computer search that led to the new algorithms is described.