Pith. sign in

REVIEW 1 major objections 6 minor 67 references

Towards Faster Feasible Matrix Multiplication by Trilinear Aggregation

T0 review · 1 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims a 44-by-44-by-44 matrix multiplication algorithm using 36,110 multiplications, with complexity $O(n^{2.773203})$, the fastest among feasible base cases under 1000.

desk verdict The reader's proof objection is correct, but the theorem is repairable; the new feasible matrix multiplication exponents likely stand, and the paper deserves peer review with a mandatory corrected Appendix A. read the letter →

arxiv 2508.01748 v1 pith:AJPFGAKK submitted 2025-08-03 cs.DS

Oded Schwartz , Eyal Zwecher This is my paper · ORCID
classification cs.DS MSC 68Q1768Q2515A69
keywords fastmatrixmultiplicationtrilinearaggregationfeasiblealgorithmstensorrankboundkinrowsleadingcoefficientexponentimplicitcanceling
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper aims to make fast matrix multiplication work at 'feasible' input sizes, where the recursive base case is small enough to run on real hardware. It constructs two families of trilinear-aggregation algorithms; the first contains a $44\times44\times44$ algorithm using 36,110 multiplications, with complexity $O(n^{2.773203})$, and the second, at base case 1936, achieves $O(n^{2.773177})$. These are claimed to be the best exponents among known algorithms whose base cases are smaller than 1000, and for the second family among all known feasible algorithms. The construction chooses variants of the 7-multiplication $2\times2$ algorithm with prescribed first rows, creates duplicate 'kin' rows shared between the aggregation and cancellation steps, and unites each pair to save one multiplication. The paper also reports a sparse decomposition that reduces the leading coefficient from about 736 to about 8, a step toward practical applicability.

What carries the argument

The carrying object is the trilinear aggregation scheme of the 1982 algorithm, written as encoding/decoding matrices $\langle U,V,W\rangle$. In the cancellation step, the scheme computes a sum of traces, each a $2\times2$ matrix product that any 7-multiplication algorithm can compute. The paper's move is to pick, for the diagonal traces, an equivalent 7-multiplication algorithm whose first $U$-row is $(-1/\gamma_{i,i}, 1, 1, 0)$ and whose first $V$-row is $(1, \gamma_{i,i}, 1, 0)$, with $\gamma_{i,i} = 1 - 9/(n_0/2 + 1)$; these rows reproduce the aggregation-step rows, creating $n_0/2 + 1$ disjoint kin pairs. Uniting each pair removes one multiplication per pair, cutting the count from $t_{\mathrm{Pan}}$ to $t_{\mathrm{New}}$. The second family exploits the observation that two recursive calls of the first family contain $\langle4,4,4;49\rangle$ subtensors and replaces each by a $\langle4,4,4;48\rangle$ algorithm to trim additional multiplications.

What would settle it

Verify Appendix A on a concrete instance: take $K_U = \begin{pmatrix}-1/\gamma & 1\\1 & 0\end{pmatrix}$ and $K_V = \begin{pmatrix}1 & \gamma\\1 & 0\end{pmatrix}$ with $\gamma = 1 - 9/(n_0/2+1)$, apply the two row-rewriting steps, and check whether the final algorithm has $M([U]_0)=K_U$ and $M([V]_0)=K_V$. If the second step overwrites the first, the kin pairing of Corollary 3.2 fails and the $\langle44,44,44;36110\rangle$ bound must be re-examined. Independently, the supplemental $\langle44,44,44;36110\rangle$ encoding/decoding matrices can be tested directly against the trace equations of matrix multiplication: if the equations hold with 36,110 rows, the rank bound and exponent stand regardless of the intermediate proof.

Watch

Extended reading notes

Core claim

On its own terms, the central discovery is that the trilinear aggregation method can be sharpened by replacing the generic 7-multiplication $2\times2$ base algorithm inside the cancellation step with an equivalent algorithm whose first encoding and decoding rows match rows already present in the aggregation step. Because the paper argues all such $2\times2$ algorithms lie in one equivalence class, it claims the first rows can be prescribed at will (Theorem 2.22). The matched rows become kin rows, meaning two rows of the encoding/decoding triple that coincide in two of the three matrices, and Lemma 2.20 removes one multiplication per disjoint kin pair. This yields the family TA-New25 with $t = n_0^3/3 + 15n_0^2/4 + 61n_0/6 + 8$ multiplications for even $n_0 \neq 16$, whose exponent is minimized at $n_0 = 44$: a $\langle 44,44,44; 36110\rangle$-algorithm with complexity $O(n^{2.773203})$. Squaring the base case and replacing the resulting $\langle 4,4,4;49\rangle$ subtensors by $\langle 4,4,4;48\rangle$ algorithms gives a second family whose best exponent at base case 1936 is $O(n^{2.773177})$.

Load-bearing premise

The load-bearing premise is that any two invertible $2\times2$ matrices $K_U$ and $K_V$ can be realized as the first encoding and decoding rows of a 7-multiplication $2\times2$ algorithm (Theorem 2.22). The proof in Appendix A applies the row-rewriting step twice, and the second application appears to overwrite the row set by the first, so the resulting algorithm may have $K_V^{-1}$ in the first encoding row instead of $K_U$. The claimed saving of $n_0/2 + 1$ multiplications, and therefore the exponents $2.773203$ and $2.773177$, depend on this premise.

Editorial extensions

If this is right

  • It establishes $\mathrm{Rank}(\langle 44,44,44\rangle) \le 36110$, so multiplying $n\times n$ matrices by recursion on this base case runs in $O(n^{2.773203})$.
  • Among algorithms with base cases smaller than 1000, this is the fastest claimed asymptotic complexity, improving on the previous 2.773372 exponent from 1982.
  • The same construction yields the best known exponents for many even base cases $n_0 \ge 28$, not only $n_0 = 44$.
  • The second family, with base case $44^2 = 1936$, reaches $O(n^{2.773177})$, claimed to be the best exponent of any known feasible algorithm.
  • A sparse decomposition brings the leading coefficient of the new algorithms from about 736 down to about 8, comparable to the best prior coefficient reductions.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the prescribed-first-row theorem can be repaired, the same kin-row trick could apply to rectangular or odd-dimension algorithms through the symmetrization and padding techniques the paper discusses, possibly improving exponents for base cases below 28 as well.
  • Iterating the subtensor replacement on higher powers of the base case may squeeze the exponent further, at the price of larger base cases; nothing in the paper rules out or quantifies such a limit.
  • Because the exponent gain over the 1982 algorithm is only about 0.00017 while the sparse decomposition raises communication costs, the practical payoff is an empirical question about constants and I/O behavior, which the paper leaves open.
  • A direct computer search over the equivalence class of 7-multiplication $2\times2$ algorithms could verify the prescribed-first-row property independently of the proof's bookkeeping.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 6 minor

Summary. The paper proposes two families of matrix multiplication algorithms over the same feasible base-case sizes as Pan's 1982 algorithms. The first family uses de Groote-equivalent variants of Strassen's 2x2 algorithm inside the trilinear aggregation framework to create kin rows, reducing the number of multiplications by (n0/2+1) for even n0>=28, n0 != 16; for n0=44 this yields a ⟨44,44,44;36110⟩-algorithm with exponent log44(36110) ≈ 2.773203. The second family applies two recursive steps and replaces ⟨4,4,4;49⟩ sub-algorithms by ⟨4,4,4;48⟩-algorithms, yielding a ⟨1936,1936,1936;1303676064⟩-algorithm with exponent ≈ 2.773177. The paper also reports leading-coefficient reduction via sparse decomposition, with leading coefficient about 8. All exponents are claimed to improve over Pan's 1982 baselines.

Significance. If the construction is valid, these are the best known exponents among algorithms with base cases below 1000, improving Pan's 1982 algorithm for many feasible sizes. The contribution is a mathematical derivation rather than a parameter fit: the rank bounds are explicit formulas, and the authors provide supplemental encoding/decoding matrices. The counting arguments, including the h^2 count of embedded ⟨4,4,4;49⟩ tensors in Section 4, are internally consistent. The main caveat is that the proof of the key existence lemma (Theorem 2.22) is defective as written, so the central rank bounds are not yet established by the submitted manuscript.

major comments (1)
  1. [Appendix A, Theorem 2.22] The proof of Theorem 2.22 does not work. After the first application of Lemma A.2, we have M([U1]_0)=KU and M([V1]_0) invertible. The proof then cyclically rotates to ⟨V1,U1,W1⟩ and applies Lemma A.2 again with target KV. In that second application the 'U' matrix is V1 and the 'V' matrix is U1, so the lemma transforms the first row of the second matrix (i.e., U1) to R^{-T}M([U1]_0), where R is defined from M([V1]_0); explicitly M([U2]_0) = M([V1]_0)^{-1} KV KU, which need not equal KU. Rotating back gives a final triplet with [U]_0 = vec(M([V1]_0)^{-1} KV KU), not vec(KU). Thus the asserted simultaneous prescription of [U]_0 and [V]_0 is not established. This is load-bearing: Claim 3.3 uses Theorem 2.22 to obtain the required Strassen variant, and Theorem 3.4's reduction by (n0/2+1) multiplications, the rank bounds in Table 1, and Corollary 3.6's exponent all depend on it. The lemma itself is plausible (a two-step construction different from the one in the appendix can achieve the goal, or an explicit ⟨2,2,2;7⟩-algorithm can be certified), so I am not recommending rejection; rather, the proof needs to be corrected, or the claimed existence should be supported by an explicit machine-checkable certificate.
minor comments (6)
  1. [Appendix A, proof of Theorem 2.22] There is a typographical error: the text reads 'M([U'']_0) = KU' where it should read 'M([U']_0) = KU'.
  2. [Corollary 4.3 proof] The last line says 'the minimum is indeed obtained for n0 = 44', but the variable in that proof is m0 (with n0=m0^2); it should say m0=44.
  3. [Theorem 4.2 statement] The displayed formula has '244n3_0 1.5', which appears to be missing a denominator; the proof and Corollary 4.3 use 244 m0^3/3 = 244 n0^{1.5}/3. Please correct the typesetting.
  4. [Section 3] The word 'wereas' should be 'whereas' in the sentence 'However, wereas Pan utilizes a single ⟨2,2,2;7⟩-algorithm...'.
  5. [Section 4, Definition 4.1 and Theorem 4.2] Definition 4.1 states informally that each occurrence of a ⟨4,4,4;49⟩-algorithm in the composed algorithm can be replaced by a ⟨4,4,4;48⟩-algorithm. This is a standard tensor-product substitution, but the paper should spell out the embedding: after two recursive steps, the h^2 pairs of intact 2x2 algorithms produce independent sub-tensors, and replacing each decomposition reduces the total rank by one per pair. The arithmetic in the proof of Theorem 4.2 is consistent with this reading, but the formal justification is only one sentence and should be expanded.
  6. [Corollary 3.6 proof] The claim 'Checking all even values ... we see' is a finite computation; please include the data or a script in the supplemental material to make the check reproducible.

Circularity Check

0 steps flagged · score 2.0 of 10

No significant circularity: the claimed rank-bound and exponent improvements follow from explicit algebraic constructions, and the same-group citations are used as published external baselines rather than as self-justifying definitions.

full rationale

The paper's central derivation is a constructive mathematical argument: it takes Pan's trilinear-aggregation algorithm (as reformulated by Hadas and Schwartz [26]) and reduces the number of multiplications by n0/2+1 via carefully chosen kin rows. The kin rows are obtained from special (2,2,2;7)-algorithms whose first encoding rows are prescribed (Theorem 2.22), and those algorithms are constructed using the de Groote equivalence and Strassen's base algorithm. No parameter is fitted to data, no quantity is defined in terms of the claimed prediction, and no benchmark is used to tune the construction. The comparison tables are evaluations of the derived formulas, not curve fits. The paper does rely on prior work by co-author Schwartz ([5], [26], [34]), but that reliance is ordinary dependency on published, externally checkable results, not circular justification. In particular, [26] supplies the starting construction with the same exponent as Pan, while the improvement is proved by the paper's own equations (Corollary 3.2, Theorem 3.4). The only substantive concern is a correctness gap in the Appendix A proof of Theorem 2.22: after rotating and applying Lemma A.2 a second time, the first row fixed in the first application is not preserved as the proof's notation suggests. This is a proof defect, not circularity; the theorem is plausibly repairable by a two-step de Groote change of variables, and the claimed rank bound (36110) and exponent (2.773203) are not shown to be circularly derived from the inputs. Therefore, the circularity burden is low.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted: all constants come from closed-form counts. The axioms are standard cited results; the fragile one is the use of de Groote equivalence to claim simultaneous prescribed first rows, which the paper's proof does not establish.

assumptions (4)
  • standard math de Groote's theorem: all ⟨2,2,2;7⟩-algorithms lie in one equivalence class under the de Groote group action.
    Invoked in the proof sketch of Theorem 2.22 and in Section 2.2, relying on refs [18,19]. The theorem itself is standard, but the paper uses it to infer the existence of an algorithm with prescribed simultaneous first rows, which is the contested step.
  • domain assumption The Hadas-Schwartz construction [26] is a correct ⟨n0,n0,n0;t_Pan⟩-algorithm with the aggregation tables and cancellation structure described.
    The paper builds directly on [26] and takes t_Pan and the aggregation terms as given; no proof is repeated. [26] is co-authored by Schwartz, a self-citation, but published in ISSAC 2023.
  • domain assumption There exists a ⟨4,4,4;48⟩-algorithm over the relevant field, from refs [32,44,22].
    Used in Definition 4.1 and Theorem 4.2 to replace ⟨4,4,4;49⟩ sub-tensors; cited to Kaporin, Novikov et al., and Dumas et al.
  • domain assumption The sparse decomposition method and its leading coefficient formula from ref [5] are correct.
    Used in Appendix D to reduce the leading coefficient; cited to Beniamini and Schwartz (self-citation).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Towards Faster Feasible Matrix Multiplication by Trilinear Aggregation." pith.science (2026). https://pith.science/paper/AJPFGAKK

@misc{pith2026250801748,
  author       = {Pith},
  title        = {Pith review of: Towards Faster Feasible Matrix Multiplication by Trilinear Aggregation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AJPFGAKK}},
  note         = {Machine review of arXiv:2508.01748}
}
abstract

Matrix multiplication is a fundamental kernel in high performance computing. Many algorithms for fast matrix multiplication can only be applied to enormous matrices ($n>10^{100}$) and thus cannot be used in practice. Of all algorithms applicable to feasible input, Pan's $O(n^{2.773372})$ algorithm (1982) is asymptotically the fastest. We obtain an $O(n^{2.773203})$ algorithm applicable to the same input sizes as Pan's algorithm. This algorithm is the fastest matrix multiplication algorithm with base case smaller than $1000$. Further, our method obtains the best asymptotic complexity for many small base cases, starting at $n_0=28$. We also obtain better exponents for larger base cases. To construct our algorithm, we use the trilinear aggregation method. We find parts of the algorithms that are equivalent to matrix multiplication with smaller base case, and use the de Groote equivalence to replace these parts in a way that allows further optimization of our algorithms. Finally, we improve the additive complexity of our algorithms by finding a sparse decomposition and reducing the leading coefficient. These mark a fundamental step towards outperforming existing fast matrix multiplication algorithms in practice.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

67 extracted references · 57 canonical work pages

  1. [26]

    Towards practical fast matrix multiplication based on trilinear aggregation

    Tor Hadas and Oded Schwartz. “Towards practical fast matrix multiplication based on trilinear aggregation”. In: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation. 2023, pp. 289–297

    work page 2023

  2. [1]

    A Refined Laser Method and Faster Matrix Multiplication

    Josh Alman and Virginia Vassilevska Williams. “A Refined Laser Method and Faster Matrix Multiplication”. In: TheoretiCS Volume 3 (Sept. 2024). issn: 2751-4838. doi: 10 . 46298 / theoretics . 24 . 21. url: http : //dx.doi.org/10.46298/theoretics.24.21

    doi:10.46298/theoretics.24.21 2024

  3. [2]

    More Asymmetry Yields Faster Matrix Multiplication

    Josh Alman et al. “More Asymmetry Yields Faster Matrix Multiplication”. In: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2025, pp. 2005–2039.doi: 10.1137/1.9781611978322

    doi:10.1137/1.9781611978322 2025

  4. [3]

    Fast matrix multiplication: limitations of the Coppersmith- Winograd method

    Andris Ambainis, Yuval Filmus, and François Le Gall. “Fast matrix multiplication: limitations of the Coppersmith- Winograd method”. In: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing. 2015, pp. 585–593

    work page 2015

  5. [4]

    Adaptive flip graph algorithm for matrix multiplication

    Yamato Arai, Yuma Ichikawa, and Koji Hukushima. “Adaptive flip graph algorithm for matrix multiplication”. In: Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation. 2024, pp. 292–298

    work page 2024

  6. [5]

    Faster Matrix Multiplication via Sparse Decomposition

    Gal Beniamini and Oded Schwartz. “Faster Matrix Multiplication via Sparse Decomposition”. In: The 31st ACM Symposium on Parallelism in Algorithms and Architectures . SPAA ’19. Phoenix, AZ, USA: Association for Computing Machinery, 2019, pp. 11–22. isbn: 9781450361842. doi: 10.1145/3323165.3323188 . url: https://doi.org/10.1145/3323165.3323188

    work page arXiv 2019

  7. [6]

    Sparsifying the Operators of Fast Matrix Multiplication Algorithms

    Gal Beniamini et al. “Sparsifying the Operators of Fast Matrix Multiplication Algorithms”. In: arXiv e-prints (2020), arXiv–2008

    work page 2020

  8. [7]

    A framework for practical parallel fast matrix multiplication

    Austin R Benson and Grey Ballard. “A framework for practical parallel fast matrix multiplication”. In: ACM SIGPLAN Notices 50.8 (2015), pp. 42–53. 12

    work page 2015

Show all 67 references
  1. [8]

    Relations between exact and approximate bilinear algorithms. Applications

    Dario Bini. “Relations between exact and approximate bilinear algorithms. Applications”. In: Calcolo 17.1 (1980), pp. 87–97

    1980

  2. [9]

    O(n2.7799) complexity for n × n approximate matrix multiplication

    Dario Bini et al. “ O(n2.7799) complexity for n × n approximate matrix multiplication”. In: Information pro- cessing letters 8.5 (1979), pp. 234–235

    1979

  3. [10]

    A 5 2 n2-Lower Bound for the Multiplicative Complexity of n × n-Matrix Multiplication

    Markus Bläser. “A 5 2 n2-Lower Bound for the Multiplicative Complexity of n × n-Matrix Multiplication”. In: STACS 2001: 18th Annual Symposium on Theoretical Aspects of Computer Science, Dresden, Germany, February 15-17, 2001. Proceedings. Springer. 2003, p. 99

    2001

  4. [11]

    A Strassen-like matrix multiplication suited for squaring and higher power computation

    Marco Bodrato. “A Strassen-like matrix multiplication suited for squaring and higher power computation”. In: Proceedings of the 2010 international symposium on symbolic and algebraic computation . 2010, pp. 273–280

    2010

  5. [12]

    Richard P. Brent. Algorithms for matrix multiplication . Citeseer, 1970

    1970

  6. [13]

    On the additive complexity of 2 × 2 matrix multiplication

    Nader H. Bshouty. “On the additive complexity of 2 × 2 matrix multiplication”. In: Information processing letters 56.6 (1995), pp. 329–335

    1995

  7. [14]

    On the arithmetic complexity of Strassen-like matrix multiplications

    Murat Cenk and M Anwar Hasan. “On the arithmetic complexity of Strassen-like matrix multiplications”. In: Journal of Symbolic Computation 80 (2017), pp. 484–501

    2017

  8. [15]

    A group-theoretic approach to fast matrix multiplication

    Henry Cohn and Christopher Umans. “A group-theoretic approach to fast matrix multiplication”. In: 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. IEEE. 2003, pp. 438–449

    2003

  9. [16]

    Matrix multiplication via arithmetic progressions

    Don Coppersmith and Shmuel Winograd. “Matrix multiplication via arithmetic progressions”. In: Proceedings of the nineteenth annual ACM symposium on Theory of computing . 1987, pp. 1–6

    1987

  10. [17]

    Improved bound for complexity of matrix multiplica- tion

    Alexander Munro Davie and Andrew James Stothers. “Improved bound for complexity of matrix multiplica- tion”. In: Proceedings of the Royal Society of Edinburgh Section A: Mathematics 143.2 (2013), pp. 351–369

    2013

  11. [19]

    On varieties of optimal algorithms for the computation of bilinear mappings II. optimal algorithms for 2× 2-matrix multiplication

    Hans F. de Groote. “On varieties of optimal algorithms for the computation of bilinear mappings II. optimal algorithms for 2× 2-matrix multiplication”. In:Theoretical Computer Science 7.2 (1978), pp. 127–148.issn: 0304-

    1978

  12. [20]

    Optimization techniques for small matrix multi- plication

    Charles-Éric Drevet, Md. Nazrul Islam, and Éric Schost. “Optimization techniques for small matrix multi- plication”. In: Theoretical Computer Science 412.22 (May 2011), pp. 2219–2236. issn: 0304-3975. doi: 10 . 1016 / j . tcs . 2010 . 12 . 012. url: https : / / www . sciencedi...

    2011

  13. [21]

    Faster matrix multiplication via asymmetric hashing

    Ran Duan, Hongxun Wu, and Renfei Zhou. “Faster matrix multiplication via asymmetric hashing”. In: 2023 IEEE 64th annual symposium on Foundations of Computer Science (FOCS) . IEEE. 2023, pp. 2129–2138

    2023

  14. [22]

    A non-commutative algorithm for multi- plying 4x4 matrices using 48 non-complex multiplications

    Jean-Guillaume Dumas, Clément Pernet, and Alexandre Sedoglavic. A non-commutative algorithm for multi- plying 4x4 matrices using 48 non-complex multiplications . 2025. arXiv: 2506.13242 [cs.SC] . url: https: //arxiv.org/abs/2506.13242

    2025 arXiv

  15. [23]

    Strassen’s algorithm is not optimally accurate

    Jean-Guillaume Dumas, Clément Pernet, and Alexandre Sedoglavic. “Strassen’s algorithm is not optimally accurate”. In: Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation . 2024, pp. 254–263

    2024

  16. [24]

    Discovering faster matrix multiplication algorithms with reinforcement learning

    Alhussein Fawzi et al. “Discovering faster matrix multiplication algorithms with reinforcement learning”. In: Nature 610.7930 (2022), pp. 47–53

    2022

  17. [25]

    Algebraic Complexity Theory

    Joachim von zur Gathen. “Algebraic Complexity Theory”. In: Annual Review of Computer Science 3.1 (1988), pp. 317–348

    1988

  18. [27]

    Local search for fast matrix multiplication

    Marijn J.H. Heule, Manuel Kauers, and Martina Seidl. “Local search for fast matrix multiplication”. In: Theory and Applications of Satisfiability Testing–SAT 2019: 22nd International Conference, SAT 2019, Lisbon, Portugal, July 9–12, 2019, Proceedings 22 . Springer. 2019, pp. ...

    2019

  19. [28]

    New ways to multiply 3 × 3-matrices

    Marijn J.H. Heule, Manuel Kauers, and Martina Seidl. “New ways to multiply 3 × 3-matrices”. In: Journal of Symbolic Computation 104 (2021), pp. 899–916. issn: 0747-7171. doi: https://doi.org/10.1016/j.jsc. 2020.10.003. url: https://www.sciencedirect.com/science/article/pii/S07...

    2021 doi

  20. [29]

    On minimizing the number of multiplications necessary for matrix multiplication

    John E. Hopcroft and Leslie R. Kerr. “On minimizing the number of multiplications necessary for matrix multiplication”. In: SIAM Journal on Applied Mathematics 20.1 (1971), pp. 30–36

    1971

  21. [30]

    Duality applied to the complexity of matrix multiplications and other bilinear forms

    John E. Hopcroft and Jean Musinski. “Duality applied to the complexity of matrix multiplications and other bilinear forms”. In: Proceedings of the fifth annual ACM symposium on Theory of computing . 1973, pp. 73–87

    1973

  22. [31]

    Noncommutative Bilinear Algorithms for 3*3 Matrix Multi- plication

    Rodney W Johnson and Aileen M McLoughlin. “Noncommutative Bilinear Algorithms for 3*3 Matrix Multi- plication”. In: SIAM Journal on Computing 15.2 (1986), pp. 595–603

    1986

  23. [32]

    Finding complex-valued solutions of Brent equations using nonlinear least squares

    Igor E. Kaporin. “Finding complex-valued solutions of Brent equations using nonlinear least squares”. In: Computational Mathematics and Mathematical Physics 64.9 (2024), pp. 1881–1891

    2024

  24. [33]

    The aggregation and cancellation techniques as a practical tool for faster matrix multiplica- tion

    Igor E. Kaporin. “The aggregation and cancellation techniques as a practical tool for faster matrix multiplica- tion”. In: Theoretical Computer Science 315.2-3 (2004), pp. 469–510

    2004

  25. [34]

    Matrix Multiplication, a Little Faster

    Elaye Karstadt and Oded Schwartz. “Matrix Multiplication, a Little Faster”. In: J. ACM 67.1 (Jan. 2020). issn: 0004-5411. doi: 10.1145/3364504. url: https://doi.org/10.1145/3364504

    2020 doi

  26. [35]

    Flip Graphs for Matrix Multiplication

    Manuel Kauers and Jakob Moosbauer. “Flip Graphs for Matrix Multiplication”. In: Proceedings of the 2023 International Symposium on Symbolic and Algebraic Computation . ISSAC ’23. Tromsø, Norway: Association for Computing Machinery, 2023, pp. 381–388. isbn: 9798400700392. doi: ...

    2023

  27. [36]

    Some New Non-Commutative Matrix Multiplication Algorithms of Size (n, m, 6)

    Manuel Kauers and Jakob Moosbauer. “Some New Non-Commutative Matrix Multiplication Algorithms of Size (n, m, 6)”. In: ACM Commun. Comput. Algebra 58.1 (Jan. 2025), pp. 1–11. issn: 1932-2232. doi: 10.1145/ 3712020.3712021. url: https://doi.org/10.1145/3712020.3712021

    2025

  28. [37]

    A noncommutative algorithm for multiplying 3*3 matrices using 23 multiplications

    Julian D. Laderman. “A noncommutative algorithm for multiplying 3*3 matrices using 23 multiplications”. In: American Mathematical Society 82.1 (1976)

    1976

  29. [38]

    On practical algorithms for accelerated matrix multipli- cation

    Julian D. Laderman, Victor Pan, and Xuan-He Sha. “On practical algorithms for accelerated matrix multipli- cation”. In: Linear Algebra and Its Applications 162 (1992), pp. 557–588

    1992

  30. [39]

    Powers of tensors and fast matrix multiplication

    François Le Gall. “Powers of tensors and fast matrix multiplication”. In: Proceedings of the 39th international symposium on symbolic and algebraic computation . 2014, pp. 296–303

    2014

  31. [40]

    Communication-avoiding parallel Strassen: Implementation and performance

    Benjamin Lipshitz et al. “Communication-avoiding parallel Strassen: Implementation and performance”. In: SC’12: Proceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis. IEEE. 2012, pp. 1–11

    2012

  32. [41]

    The Number of the Beast: Reducing Additions in Fast Matrix Multiplication Algorithms for Dimensions up to 666

    Erik Mårtensson and Paul Stankovski Wagner. The Number of the Beast: Reducing Additions in Fast Matrix Multiplication Algorithms for Dimensions up to 666 . Cryptology ePrint Archive, Paper 2024/2063. 2024. url: https://eprint.iacr.org/2024/2063

    2024

  33. [42]

    Flip Graphs with Symmetry and New Matrix Multiplication Schemes

    Jakob Moosbauer and Michael Poole. “Flip Graphs with Symmetry and New Matrix Multiplication Schemes”. In: arXiv preprint arXiv:2502.04514 (2025)

    2025 arXiv

  34. [43]

    Multiplying 2 × 2 Sub-Blocks Using 4 Multiplications

    Yoav Moran and Oded Schwartz. “Multiplying 2 × 2 Sub-Blocks Using 4 Multiplications”. In: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures . 2023, pp. 379–390

    2023

  35. [44]

    AlphaEvolve: A coding agent for scientific and algorithmic discovery

    Alexander Novikov et al. AlphaEvolve: A coding agent for scientific and algorithmic discovery . Tech. rep. 2025

    2025

  36. [45]

    On schemes for the computation of products and inverses of matrices

    Victor Ya Pan. “On schemes for the computation of products and inverses of matrices”. In: Russian Math. Surveys 27.5 (1972), pp. 249–250

    1972

  37. [46]

    New Fast Algorithms for Matrix Operations

    Victor Ya. Pan. “New Fast Algorithms for Matrix Operations”. In: SIAM Journal on Computing 9.2 (1980), pp. 321–342. doi: 10 . 1137 / 0209027. eprint: https : / / doi . org / 10 . 1137 / 0209027. url: https : //doi.org/10.1137/0209027

    1980 doi

  38. [47]

    Strassen’s algorithm is not optimal trilinear technique of aggregating, uniting and cancel- ing for constructing fast algorithms for matrix operations

    Victor Ya. Pan. “Strassen’s algorithm is not optimal trilinear technique of aggregating, uniting and cancel- ing for constructing fast algorithms for matrix operations”. In: 19th Annual Symposium on Foundations of Computer Science (sfcs 1978) . 1978, pp. 166–176. doi: 10.1109/...

    1978 doi

  39. [48]

    Trilinear aggregating with implicit canceling for a new acceleration of matrix multiplication

    Victor Ya. Pan. “Trilinear aggregating with implicit canceling for a new acceleration of matrix multiplication”. In: Computers & Mathematics with Applications 8.1 (1982), pp. 23–34. issn: 0898-1221. doi: https://doi. org/10.1016/0898-1221(82)90037-2 . url: https://www.scienced...

    1982

  40. [49]

    On the additive complexity of matrix multiplication

    Robert L Probert. “On the additive complexity of matrix multiplication”. In: SIAM Journal on Computing 5.2 (1976), pp. 187–203

    1976

  41. [50]

    Correction of ‘J. Laderman, V. Pan, X.–H. Sha, On practical Algorithms for Accelerated Matrix Multiplication, Linear Algebra and its Applications. Vol. 162-164 (1992) pp. 557-588’

    Jerzy S Respondek. “Correction of ‘J. Laderman, V. Pan, X.–H. Sha, On practical Algorithms for Accelerated Matrix Multiplication, Linear Algebra and its Applications. Vol. 162-164 (1992) pp. 557-588’”. In: Linear and Multilinear Algebra (2024), pp. 1–11

    1992

  42. [51]

    Partial and Total Matrix Multiplication

    Arnold Schönhage. “Partial and Total Matrix Multiplication”. In: SIAM Journal on Computing 10.3 (1981), pp. 434–455. doi: 10 . 1137 / 0210032. eprint: https : / / doi . org / 10 . 1137 / 0210032. url: https : //doi.org/10.1137/0210032

    1981 doi

  43. [52]

    Pebbling game and alternative basis for high performance matrix multipli- cation

    Oded Schwartz and Noa Vaknin. “Pebbling game and alternative basis for high performance matrix multipli- cation”. In: SIAM Journal on Scientific Computing 45.6 (2023), pp. C277–C303

    2023

  44. [53]

    The bilinear complexity and practical algorithms for matrix multiplication

    Alexey V. Smirnov. “The bilinear complexity and practical algorithms for matrix multiplication”. In: Compu- tational Mathematics and Mathematical Physics 53 (2013), pp. 1781–1795

    2013

  45. [54]

    Gaussian elimination is not optimal

    Volker Strassen. “Gaussian elimination is not optimal”. In: Numerische mathematik 13.4 (1969), pp. 354–356

    1969

  46. [55]

    The asymptotic spectrum of tensors and the exponent of matrix multiplication

    Volker Strassen. “The asymptotic spectrum of tensors and the exponent of matrix multiplication”. In: 27th Annual Symposium on Foundations of Computer Science (sfcs 1986) . IEEE. 1986, pp. 49–54

    1986

  47. [56]

    Vermeidung von Divisionen

    Volker Strassen. “Vermeidung von Divisionen.” ger. In: Journal für die reine und angewandte Mathematik 264 (1973), pp. 184–202. url: http://eudml.org/doc/151394

    1973

  48. [57]

    Private communication with Austing R

    Petr Tichavsk `y and Teodor Kováč. Private communication with Austing R. Benson and Grey Ballard. 2015

    2015

  49. [58]

    Multiplying matrices faster than Coppersmith-Winograd

    Virginia Vassilevska Williams. “Multiplying matrices faster than Coppersmith-Winograd”. In: Proceedings of the forty-fourth annual ACM symposium on Theory of computing . 2012, pp. 887–898

    2012

  50. [59]

    New Bounds for Matrix Multiplication: from Alpha to Omega

    Virginia Vassilevska Williams et al. New Bounds for Matrix Multiplication: from Alpha to Omega . 2023. arXiv: 2307.07970 [cs.DS]. url: https://arxiv.org/abs/2307.07970

    2023 arXiv

  51. [60]

    Private communication with Robert L

    Shmuel Winograd. Private communication with Robert L. Probert [49]. 1976. 15 A ⟨2, 2, 2; 7⟩-algorithms We next prove Theorem 2.22, which states the given two invertible matricesKU , KV ∈ R2×2, there exists a ⟨2, 2, 2; 7⟩-algorithm with encoding/decoding matrices ⟨U, V, W⟩ such...

    1976

  52. [63]

    url: https://epubs.siam.org/doi/abs/10.1137/1.9781611978322.63

    doi

  53. [64]

    For ease of notation, we omit the parameters n0, m0 when they are clear from context

    The matrix represented by v is Mm0,n0(v) ∈ Fmℓ 0×nℓ 0 satisfying− − − − − − − →Mm0,n0(v) = v. For ease of notation, we omit the parameters n0, m0 when they are clear from context. To simplify notation further, if v ∈ F1×mℓ 0·nℓ 0, we denote Mm0,n0(v) = Mm0,n0(vT ). We next int...

    1936

  54. [65]

    Denote the transformed inputs as ˜A, ˜B

    Apply fast basis transformations ϕ, ψon inputs A, B. Denote the transformed inputs as ˜A, ˜B

  55. [66]

    Apply a recursive bilinear algorithm ⟨Uϕ, Vψ, Wν⟩ on ˜A, ˜B and obtain ˜C

  56. [67]

    For ease of notation, if ϕ = ψ = ν we simply denote ⟨Uϕ, Vϕ, Wϕ⟩ϕ

    Apply a fast basis transformation νT to ˜C to obtain the result C. For ease of notation, if ϕ = ψ = ν we simply denote ⟨Uϕ, Vϕ, Wϕ⟩ϕ. Definition D.2 ([5]). Let φ1 : Rs1 → Rs2 be a linear transformation. Let l ∈ N and denote S1 = (s1)l, S2 = (s2)l. Let v ∈ Rs1. Denote v(i) = v ...

  57. [68]

    Theorem D.8 ([5])

    = qφ s1 − s2 (sl 1 − sl 2) Using the previous claims, we can give an exact formula for the runtime of a recursive bilinear algo- rithm. Theorem D.8 ([5]). Let ALG = ⟨Uϕ, Vϕ, Wϕ⟩ϕ be a decomposed recursive matrix multiplication algorithm, where Uφ, Vφ, Wφ ∈ Rt0×s0 and φ ∈ Rs0×n2

  58. [69]

    Then FALG(n) = qUϕ + qVϕ + qWϕ t0 − s0 + 1 nω0 + 2qϕ + qϕT s0 − n2 0 − qUϕ + qVϕ + qWϕ t0 − s0 nlogn0 s0 − 2qϕ + qϕT s0 − n2 0 n2 Corollary D.9 ([5])

    Denote ω0 = logn0 t0. Then FALG(n) = qUϕ + qVϕ + qWϕ t0 − s0 + 1 nω0 + 2qϕ + qϕT s0 − n2 0 − qUϕ + qVϕ + qWϕ t0 − s0 nlogn0 s0 − 2qϕ + qϕT s0 − n2 0 n2 Corollary D.9 ([5]). The leading coefficient is qUϕ +qVϕ +qWϕ t0−s0 + 1. D.3 Decomposing TA-New25 Algorithms We next reduce t...

    1982

  59. [3975]

    url: https://www.sciencedirect

    doi: https://doi.org/10.1016/0304-3975(78)90045-2 . url: https://www.sciencedirect. com/science/article/pii/0304397578900452

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.