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

• The paper focuses on fast matrix multiplication, additive complexity, and ternary coefficients.Source: MULTIPLICATION · p. 1

• For 3×3 matrices, rank 23 is the lowest known in the non-commutative case, while additions affect software implementation efficiency.A rank-23 scheme requires 23 essential multiplications of linear combinations.Source: §1 · p. 1
• Prior rank-23 schemes used 98 additions for Laderman, 61 with a change of basis, 62, and 60 without one [1].Source: §1 · p. 1
• This work reports a new rank-23 scheme using only 58 additions, achieved without a change of basis, and employing exclusively ternary coefficients {−1, 0, 1}.The authors say this ensures portability and efficiency across arbitrary fields.Source: §1 · p. 1

2.1 Matrix Multiplication Schemes

• A rank-r scheme uses coefficient tensors U, V, and W to compute r intermediate scalar products and reconstruct C = AB.This work studies n = 3 and r = 23, restricting all tensor coefficients to {−1, 0, 1}.Source: §2.1 · pp. 1–2

2.2 Ternary Flip-Graph Search

• Ternary flip-graph search traverses valid 3×3 schemes using local tensor changes that preserve correctness and rank.The plus operator raises rank by one while preserving correctness and ternary coefficients, helping the walk escape irreducible states.Source: §2.2 · p. 2

2.3 Greedy Intersection Reduction

• Greedy intersection reduction scores candidate xi ± xj subexpressions, replaces the highest-scoring choice with a fresh variable, and repeats while additions decrease.The search applies this common-subexpression-elimination step to the U, V, and W linear forms.Source: §2.3 · p. 2

• The search starts from the naive rank-27 3×3 multiplication scheme with coefficients {0, 1}.The algorithm description identifies this as its input scheme.Source: §3 · pp. 2–3
• Random flips move the scheme toward rank 23; when no useful flip is possible, or with 5% probability, the plus operator raises rank by one.At rank 23, greedy intersection reduction replaces common subexpressions with fresh variables, repeating to lower the addition count.Source: §3 · p. 3
• A random flip changes the scheme in Phase 3, with a 5% chance of using the plus operator when the current rank is below 25.The three phases run in a continuous loop until the search is manually stopped.Source: §3 · p. 3

4 Discovered 58-Addition Scheme

• 58 additive operations—34 additions and 24 subtractions—complete the rank-23 scheme.The expressions require no variable inversions; each defining equation’s first non-zero coefficient is +1.Source: §4 · p. 4
• Common subexpression elimination reduces the initial 120 naive additions by introducing 20 reusable intermediate variables.The intermediates comprise four for A, eight for B, and eight for combining products.Source: §4 · p. 4
• The algorithm forms 23 scalar products from its input combinations, then uses eight product-combination intermediates to reconstruct the output matrix.The listed equations specify the product combinations and the final entries of C.Source: §4 · p. 4

5 Discussion

• 58 additions, down from 60, were found after about 30 minutes on an Intel Core i7-9750H laptop CPU.The paper frames the reduction as lowering operation cost in repeatedly used computer-graphics and scientific-computing applications.Source: §5 · p. 4
• Coefficients restricted to {−1, 0, 1} keep the scheme to additions and subtractions and support portability across hardware and numerical fields.The passage identifies ternary coefficients as a practical strength of the scheme.Source: §5 · p. 5
• The authors attribute the result to ternary search restrictions and a greedy heuristic for reducing additive complexity.They describe this combination as validating their flip-graph and heuristic search methodology.Source: §5 · p. 5
• Whether 58 additions is minimal for rank 23 remains open, and production-BLAS implementation is proposed to measure real-world performance.The paper also identifies searches on other small matrix formats as future work.Source: §5 · p. 5

6 Conclusion

• 58 additions improve the previous 60-addition state of the art without a change of basis, reducing total scalar operations from 83 to 81.The scheme uses coefficients from {−1, 0, 1}.Source: §6 · p. 5
• An automated search combined a ternary-restricted flip-graph walk with greedy intersection reduction for common subexpression elimination.Source: §6 · p. 5
• Future work could seek a lower bound for rank-23 additive complexity, search other matrix formats, and implement the scheme in production BLAS software.The paper presents implementation as a way to benchmark practical performance.Source: §6 · p. 5

A Python verification Script

• Symbolic substitution reconstructs U, V, and W and confirms the Brent equations, establishing correctness for all 3×3 matrices over any field.Source: A Python verification Script · p. 5
• The Python script’s results matched standard multiplication on 10,000 random matrix pairs.Source: A Python verification Script · p. 5
• The implementation flattens the two input matrices and forms four A-side and eight B-side linear-combination intermediates.Source: A Python verification Script · p. 5
• The intermediates feed 23 scalar products and eight product-combination variables before the output entries are assembled.Source: A Python verification Script · pp. 5–6
• The validator asserts that the returned matrix equals standard multiplication for randomly generated integer inputs.The script constructs the result as a 3×3 array.Source: A Python verification Script · p. 6