Source-linked AI summary
Fast matrix multiplication via recursive $\langle$ 4x4x4:48 $\rangle$ algorithms into practice
Jean-Guillaume Dumas, Clément Pernet, Alexandre Sedoglavic, Joshua Stapleton, Petr Tichavský
TL;DR
The paper addresses the cost of recursively multiplying matrices with a 48-product 4×4 algorithm. It reduces the leading complexity constant through alternative basis encodings, while retaining 48 bilinear products and accounting for conversion costs as lower-order terms.
Problem
The paper focuses on reducing the leading constant in the complexity bound for matrix multiplication.
Source: §1 · p. 2Method
The authors optimize a 48-multiplication 4×4 algorithm and develop square and rectangular alternative-basis encodings.
Source: §1 · p. 2, §4.1 · p. 8Results
The 4×4 algorithm uses 48 multiplications and 204 other operations, and its recursive bound’s leading constant is further reduced by alternative-basis variants.
Source: §5 · p. 12Takeaways & Limitations
All presented variants retain 48 bilinear products, and the encoded bounds include lower-order conversion costs.
Source: §5 · p. 12A complete geometric understanding remains open, so further improvements may be possible; the results claim arithmetic bounds, not optimality or measured runtime gains.
Source: §5 · p. 12
Abstract
from arXiv · showhide
We present a fast algorithm for multiplying two 4x4 matrices using 48 multiplications and 204 other operations (addition, subtraction or scaling by a constant) over any ring containing an inverse of 2. Applied recursively, this algorithm reaches a cost bound with leading term (7+3/8)n^{\log_4(48)}. Alternative basis decompositions of this algorithm further reduce this to (6+13/32)n^{\log_4(48)}, with square change of bases, and then to (5+2/3)n^{\log_4(48)}, using rectangular encodings with inner dimensions 24 and 32. The conversion costs of these alternative basis variants are included as lower-order terms.
1 Introduction
The paper targets the leading constant in recursive matrix-multiplication complexity, presenting a 48-multiplication 4×4 algorithm and variants that reduce the bound through alternative representations and basis changes.
1 Introduction
- The paper focuses on the leading-term constant: the first straight-line program in [8] requires 315 scalar additions, subtractions, and constant scalings, yielding a recursive algorithm.The authors explore sparse lrp representations, aim to maximize canonical-basis-vector counts in L, R, and P, and use alternative bases to reduce the arithmetic-complexity constant.Source: §1 · p. 2, §1.2 · p. 3
- The 4×4 algorithm uses 48 bilinear multiplications and 204 additions, subtractions, or scalings over rings containing an inverse of 2.Applied recursively, it yields a cost bound with a leading term.Source: §1 · p. 2
- A rectangular encoding mixing inner dimensions d = 24 and d = 32 reduces the third part to 32 residual operations and 63 conversion operations, yielding a leading term.Source: §1 · p. 2
- 8.1875 is the reported complexity-bound constant for the sparsest variant, realized with a straight-line program of 230 scalar operations.That variant has 624 nonzero elements, including 104 non-units.Source: §1.2 · p. 3
- 7.375 is the reported complexity-bound constant for the variant with 30 canonical-basis vectors, realized with 200 additions/subtractions and four halvings.Its L and R straight-line programs are equivalent up to a permutation and whole row/column sign swaps.Source: §1.2 · p. 3
- Alternative-basis versions of the two variants yield further improvements in the constants, to 6.78125 and approximately 6.4375, respectively.Source: §1.2 · p. 3
2 Sparse and canonical tensor decomposition
The paper searches within the de Groote orbit for tensor decompositions that balance sparsity with canonical-basis vectors, then reports a decomposition with 30 such vectors across L, R, and P.
2 Sparse and canonical tensor decomposition
- The de Groote isotropy group maps tensor decompositions to equivalent algorithms that can differ in arithmetic complexity constants.This provides the search space for changing an algorithm’s representation without changing its complexity exponent.Source: §2 · p. 4
2.1 Sparse tensor decomposition in the de Groote orbit
- The sparsest identified decomposition has 202, 202, and 220 nonzero elements in L, R, and P, respectively, totaling 624.The total includes 104 non-units.Source: §2.1 · p. 4
2.2 Maximizing the number of vectors from the canonical basis
- Distinct non-canonical rows of L and R and columns of P each require at least one operation, motivating the search for more canonical-basis vectors.Canonical-basis vectors are counted up to sign.Source: §2.2 · p. 4
- Maximizing canonical-basis vectors in L, R, and P gives a decomposition with 10 in each matrix, 30 overall.Its L, R, and P representations have 256, 256, and 248 nonzero elements, respectively, including 136 non-units overall.Source: §2.2 · p. 4
3 Short straight-line programs
The paper develops and refines straight-line programs for the algorithm’s linear maps. Its canonical representation uses 204 linear operations in addition to 48 bilinear products.
3 Short straight-line programs
- PLinOpt combines heuristics for finding short programs with common-subexpression elimination, kernel methods, and refinements using linear dependencies and subprogram optimization.A complementary search proposes sums or differences of existing intermediate values and rebuilds the program; exact replay verifies operation counts.Source: §3 · p. 5
3.1 SLPs for the sparse LRP representation
- The sparse LRP representation’s programs require 230 operations: 63 additions and two scalings each for L and R, and 99 additions and one scaling for P.The reported scalings are binary shifts.Source: §3.1 · p. 7
3.2 SLPs for the canonical LRP representation
- 204 linear operations—200 additions/subtractions and four halvings—accompany the canonical representation’s 48 bilinear products.The input and output programs act directly on ordinary matrix entries, with no basis conversion.Source: §3.2 · pp. 7–8
4 Alternative basis
Factoring the algorithm’s matrices into conversion and residuum components trades conversion overhead against the operations repeated recursively. The section evaluates square and rectangular encodings with different inner dimensions.
4 Alternative basis
- The alternative basis factors each matrix as X = Xalt · Xcob, using Xcob as an encoder for L and R and a decoder for P.The residuum Xalt can use fewer operations, reducing the dominant term; conversion costs contribute lower-order terms.Source: §4 · p. 8
4.1.1 Sparse square alternative basis
- The sparse square alternative basis uses 185 operations, with 99 more for the square change of basis, yielding a theoretical complexity bound.Its residuum matrices have 131, 131, and 156 nonzero elements; the conversion matrices have 68, 65, and 70.Source: §4.1.1 · pp. 8–9
4.1.2 Canonical square alternative basis
- The canonical square encoding uses 173 residuum operations and 109 conversion operations, with the residuum cost governed by a recurrence over 48 products and a 16^(k−1) operation term.The global conversion cost is excluded from the recurrence and added separately.Source: §4.1.2 · p. 9
4.2 An intermediate canonical encoding with inner dimension d=24
- 122 residual and 151 conversion operations produce a redundant d=24 encoding, whose global conversions leave its one-level cost at 321 versus 252 for the ordinary program and 304 for the square encoding.The conversions are performed globally rather than afresh inside each recursive call.Source: §4.2 · pp. 10–11
4.3 An intermediate canonical encoding of P with inner dimension d=32
- For the output matrix P, a d=32 encoding uses 32 additions or subtractions with no scaling gates, giving a lower contribution than the d=24 output encoding.The d=24 output residuum uses 58 operations.Source: §4.3 · p. 11
4.4 Sparse and canonical rectangular decompositions with inner dimension d=47
- The d=47 constructions yield approximately 7n^2.7925, worse than the square alternatives; their recursively applied decoder also costs more than the d=32 decoder.The comparison is limited to the reported d=47 constructions, not all rectangular encodings.Source: §4.4 · p. 12
5 Conclusion
The paper presents a 4×4 matrix multiplication algorithm using 48 multiplications and 204 other operations over rings containing an inverse of 2. Alternative basis variants reduce the recursive arithmetic bounds, while the geometric understanding remains incomplete.
5 Conclusion
- 48 multiplications and 204 other operations suffice for 4×4 matrix multiplication over any ring containing an inverse of 2.The other operations are additions, subtractions, or scalings by a constant.Source: §5 · p. 12
- Alternative basis variants reduce the recursive leading-term constant, with square and rectangular changes of basis and conversion costs included as lower-order terms.The paper reports attained arithmetic bounds, not optimality or measured runtime improvement.Source: §5 · p. 12
- A complete geometric understanding remains open, and the paper identifies more efficient straight-line programs as a possible source of further improvements.Numerical experiments are proposed to study practical efficiency and benefits.Source: §5 · p. 12