An Exact 56-Addition, Rank-23 Scheme for General 3*3 Matrix Multiplication
For researchers in fast matrix multiplication, this provides a modest improvement in additive complexity for a fixed rank, though the rank itself remains unchanged from prior work.
This paper presents a rank-23 algorithm for general 3×3 matrix multiplication using 56 additions, improving upon previous 58-60 addition schemes. The algorithm works over arbitrary associative rings with ternary coefficients and is verified via Brent equations and additional tests.
We present a rank-$23$ algorithm for general $3\times3$ matrix multiplication that uses $56$ additions/subtractions and $23$ multiplications, for a total of $79$ scalar operations in the standard bilinear straight-line model. This improves the recent sequence of $60$-, $59$-, and $58$-addition rank-$23$ schemes. The algorithm works over arbitrary associative, possibly noncommutative, coefficient rings. Its tensor coefficients are ternary, meaning that every coefficient lies in $\{-1,0,1\}$. Correctness is certified by the $729$ Brent equations over $\mathbb{Z}$, and the verifier also expands the straight-line program and performs additional finite-field and noncommutative implementation tests.