An Exact 56-Addition, Rank-23 Scheme for General 3*3 Matrix Multiplication

Abstract

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.

Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.