New faster method multiplies 3 by 3 matrices using fewer additions
A 55-Addition Rank-23 Scheme for $3\times3$ Matrix Multiplication via Exact Two-Sided Minimization
Mathematical SoftwareComputational ComplexityData Structures and AlgorithmsSymbolic Computation
Summary
Multiplying two 3×3 matrices usually takes many steps. The authors found a way to do it with one less addition operation than the previous best method, making the process slightly more efficient. Their approach uses exact math techniques and even verified the method using a computer proof checker. This means computers can multiply matrices a bit faster without changing how the data is arranged.
What this means in practice
- •For high-performance computing teams: Improve matrix multiplication routines to run faster with fewer operations in numerical simulations and scientific computing.
- •For graphics engine developers: Implement more efficient 3×3 matrix multiplications to optimize transformations in rendering and animation pipelines.
Authors
Greg Sidebottom
Abstract
We give a scheme that multiplies two $3\times3$ matrices with 23 multiplications and 55 additions over any ring, one addition below the previous record of 56 (Sun, 2026) and the first below 56 for exact non-commutative $3\times3$ multiplication without a change of basis. The scheme forms 13 signed combinations of the entries of A and 14 of B, takes 23 products, and recombines them with 28 further additions; its correctness is machine-checked in Lean 4. The previous records, from 60 down to 56, were obtained by greedy common-subexpression elimination, which only bounds each side of a scheme from above. We minimize both input sides exactly by chain covering, and the output side exactly through the transposition principle: the 9-by-23 output map costs its transpose plus 14, and the transpose is a 9-input map that the input-side minimizer solves exactly. Applied to Perminov's cn122 scheme (class i19w225c4efh, published at 58 additions) this gives 55 = 13 + 14 + 28, where greedy elimination reaches only 29 on the output side. The same method shows that Sun's representative is output-optimal at 56, and an exact orbit-wide computation over the Heule-Kauers-Seidl database shows that the record class is the only database class attaining 55.