A 58-Addition, Rank-23 Scheme for General 3×3 Matrix Multiplication

Andrew I. Perminov · 2025

Read A 58-Addition, Rank-23 Scheme for General 3×3 Matrix Multiplication by Andrew I. Perminov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-21980.txt.

Introduction

Multiplying three-by-three matrices over a general non-commutative ring can be done with twenty-three multiplications, and the remaining cost is additions. A. I. Perminov presents a rank-23 scheme using only fifty-eight scalar additions, improving the previous best of sixty additions achieved without a change of basis.

The scheme came from an automated search combining ternary-restricted flip-graph exploration with greedy intersection reduction for common subexpression elimination. All its coefficients are minus one, zero, or one, which keeps it efficient and portable across arbitrary fields. The total scalar operation count drops from eighty-three to eighty-one. For a problem where progress is measured one addition at a time, the result sets a new state of the art for exact three-by-three multiplication.

Catalog record

CREATORAndrew I. Perminov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE17 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-21980

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A 58-Addition, Rank-23 Scheme for General 3×3 Matrix Multiplication Andrew I. Perminov Abstract This paper presents a new state-of-the-art algorithm for exact 3×3 matrix multiplication over general non-commutative rings, achieving a rank-23 scheme with only 58 scalar additions. This improves the previous best additive complexity of 60 additions [ 10 ] without a change of basis. The result was discovered through an automated search combining ternary-restricted flip-graph exploration with greedy intersection reduction for common subexpression elimination. The resulting scheme uses only coefficients from { − 1 , 0 , 1 } \{-1,0,1\} , ensuring both efficiency and portability across arbitrary fields. The total scalar operation count is reduced from 83 to 81. Keywords Fast matrix multiplication \cdot Additive complexity \cdot Ternary coefficients set 1 Introduction The computational complexity of matrix multiplication remains a fundamental problem in theoretical computer science and numerical linear algebra. Since Strassen’s discovery of a sub-cubic time algorithm [ 11 ] , the search for practical, low-complexity schemes for small matrix formats has been a persistent research direction. For 3×3 matrices, the lowest known rank (in non-commutative case) is 23 [ 4 ] . Any scheme of this rank requires 23 essential multiplications of linear combinations of input elements. However, the total number of scalar additions (and subtractions) needed to form these combinations is a crucial practical metric, as it directly impacts the efficiency of software implementations like the Basic Linear Algebra Subprograms (BLAS). Significant effort has focused on reducing the additive complexity of rank-23 schemes. Laderman’s original construction used 98 additions [ 4 ] . Recent advances have dramatically lowered this count: Schwartz and Vaknin achieved 61 additions using a change of basis [ 9 ] , Mårtensson and Wagner achieved 62 [ 5 ] , and Stapleton recently set a new record of 60 additions without a change of basis [ 10 ] . This work reports a further reduction to 58 additions, achieved without a change of basis. The result is obtained through a parallel heuristic search algorithm based on an extension of the flip-graph approach with ternary restrictions [ 7 ] and a greedy intersection reduction strategy [ 8 ] . The main result is a new rank-23 scheme using only 58 additions and employing exclusively ternary coefficients \{-1,0,1\} . This ensures the scheme’s portability and efficiency across arbitrary fields. 2 Methodology 2.1 Matrix Multiplication Schemes A matrix multiplication scheme for multiplying matrices A\in\mathbb{F}^{n\times n} and B\in\mathbb{F}^{n\times n} over a field \mathbb{F} with rank r is defined by three coefficient tensors U\in\mathbb{F}^{r\times n\times n} , V\in\mathbb{F}^{r\times n\times n} and W\in\mathbb{F}^{r\times n\times n} . It computes r intermediate scalar products: \displaystyle m_{1}=(u^{(1)}_{11}a_{11}+\dots+u^{(1)}_{nn}a_{nn})\;\cdot\; \displaystyle(v^{(1)}_{11}b_{11}+\dots+v^{(1)}_{nn}b_{nn}) \displaystyle\vdots\; \displaystyle m_{r}=(u^{(r)}_{11}a_{11}+\dots+u^{(r)}_{nn}a_{nn})\;\cdot\; \displaystyle(v^{(r)}_{11}b_{11}+\dots+v^{(r)}_{nn}b_{nn}), and reconstructs the result matrix C , where C=AB , as: \displaystyle c_{ij}=w^{(1)}_{ij}m_{1}+\dots+w^{(r)}_{ij}m_{r}. The tensors U,V,W must satisfy the Brent equations [ 2 ] . This work focuses on the n=3 , r=23 case where all coefficients in U,V,W are restricted to the set \{-1,0,1\} . 2.2 Ternary Flip-Graph Search The search operates on the space of valid 3×3 multiplication schemes of varying rank. This space is navigated using an extension of the flip-graph approach [ 3 ] , constrained by ternary restrictions [ 7 ] . A flip is a local transformation applied to the tensors U,V,W . It modifies the coefficients while preserving the correctness of the scheme (i.e., satisfaction of the Brent equations) and maintaining its current rank. Flips enable traversal between different schemes with equal rank. The ternary restriction enforces that all coefficients in U,V,W remain within the set \{-1,0,1\} throughout the search. This constraint focuses the exploration on schemes that are directly implementable over any field. Many existing flip-graph methods [ 3 , 6 ] first search for schemes over the binary field \mathbb{Z}_{2} , which is computationally efficient, and later attempt to "lift" the found coefficients to integer or rational values to ensure validity over rings such as \mathbb{Z} or \mathbb{Q} . The ternary approach avoids this lifting step entirely by working directly with the target coefficient set. The core discovery process is a random walk on this ternary flip graph. To escape irreducible states where no applicable flip can improve the scheme, a plus operator is used. This operator, defined in [ 1 ] , increases the rank of a scheme by one while preserving correctness and the ternary coefficient property. After its application, the flip-graph walk continues, often enabling further optimization that can later reduce the rank back to the target value. 2.3 Greedy Intersection Reduction After obtaining a candidate rank-23 scheme, its additive complexity is minimized using a common subexpression elimination (CSE) algorithm [ 8 ] . During the main search loop, the CSE step uses a single heuristic randomly chosen from a collection of strategies, including the Greedy-Intersections method. The algorithm identifies all candidate subexpressions of the form x_{i}\pm x_{j} within the linear forms defined by the U , V and W tensors. A heuristic scoring function evaluates every identified candidate. The subexpression with the highest score is selected, replaced by a fresh variable, and eliminated throughout the entire scheme. After each substitution, the algorithm identifies all new candidate subexpressions in the updated scheme and selects the next best one. The process continues until no remaining candidate subexpression would reduce the total addition count. 3 Discovery Algorithm The discovery algorithm integrates the ternary flip-graph search and greedy intersection reduction into a three-phase iterative process. The search begins by initializing a naive scheme for 3×3 matrix multiplication. This naive scheme has a rank of 27 and uses only coefficients from \{0,1\} (the standard matrix multiplication algorithm). The core procedure then executes the continuous loop described in Algorithm 1 . Input: a naive 3×3 multiplication scheme S with coefficients \{0,1\} and rank 27 . Output: a scheme S with minimal addition count discovered during search. while search not manually stopped do // flip to target rank while rank(S)\neq 23 do flip(S) ; if no flip is possible or random()<0.05 then plus(S) ; // reduce additions with greedy intersection Execute greedy intersection reduction algorithm on S ; Check for improvements in addition count; // random change flip(S) ; while rank(S)<25 and random()<0.05 do plus(S) ; Algorithm 1 Search loop for low-addition schemes Phase 1 (flip to target rank): the algorithm uses random flips to change the scheme until it reaches rank 23. Each flip converts the scheme to another scheme. If a flip creates a tensor component with all zero coefficients, the rank of the scheme is reduced by one. If no useful flip is possible, or with a 5% chance even if a flip is possible, the plus operator is used. This operator increases the rank by one, which helps to continue the search when stuck. Phase 2 (reduce additions with greedy intersection): after reaching rank 23, the greedy intersection reduction algorithm runs. It finds common subexpressions in the formulas from the U , V and W tensors. These common parts are replaced with new variables. This step repeats, choosing the best replacement each time, to lower the total number of additions. Phase 3 (random change): to keep searching new options and avoid getting stuck, a random flip is applied to change the scheme a bit. Also, with a

Read the complete text