pith. sign in

arxiv: 2504.19308 · v4 · submitted 2025-04-27 · 🧮 math.NA · cs.NA

Efficient approximations of matrix multiplication using truncated decompositions

Suvendu Kar , Hariprasad M. , Sai Gowri J. N. , Murugesan Venkatapathi This is my paper

Pith reviewed 2026-05-22 18:41 UTC · model grok-4.3

classification 🧮 math.NA cs.NA
keywords matrix multiplicationtruncated SVDcirculant decompositionapproximation algorithmscomputational complexitylarge language modelsnumerical linear algebra
0
0 comments X

The pith

Truncated singular value and circulant decompositions approximate matrix multiplication in O(n^{2} log n) operations at roughly 1 percent relative error.

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

The paper develops first-order approximations for multiplying large dense matrices by applying truncated singular value decomposition or circulant decomposition to each factor. Each matrix is split into a sparse part carrying the dominant entries and a smaller dense residue, which can be multiplied using Fourier or cycle-based sparsification. The resulting methods require only O(n^{2} log n) arithmetic operations for n by n matrices while holding relative error near one percent. Demonstrations indicate substantial speedups in end-to-end large-language-model workloads. Different decompositions may be chosen independently for the two matrices in the product.

Core claim

Truncated SVD, circulant decomposition, and the associated sparsifications produce usable first-order approximations to the product of two large dense matrices at a cost of O(n^{2} log n) arithmetic operations when relative error tolerances of about one percent are acceptable.

What carries the argument

Truncated singular value decomposition combined with circulant decomposition, which isolates a sparse dominant component and a dense residue so that the product can be formed from cheaper sparse-dense and Fourier-based operations.

If this is right

  • Large matrix multiplications become feasible at lower arithmetic cost while staying within acceptable error bounds.
  • End-to-end inference and training steps in large language models can be accelerated by substituting these approximations.
  • Independent choice of decomposition for each factor allows further tuning of error versus speed trade-offs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same splitting idea could be tested on other dense linear-algebra kernels such as inversion or eigenvalue routines.
  • For matrices drawn from specific application domains the required truncation rank may be smaller than for random matrices, yielding even larger speedups.

Load-bearing premise

The first-order approximations obtained from truncated SVD, circulant decomposition, and the described sparsifications preserve approximately 1 percent relative error on the matrix product for large dense matrices arising in applications such as LLMs.

What would settle it

Direct computation of the relative error between the approximated and exact product on a sequence of random or real large dense matrices; if the observed error systematically exceeds one percent, the scaling claim fails.

Figures

Figures reproduced from arXiv: 2504.19308 by Hariprasad M., Murugesan Venkatapathi, Sai Gowri J. N., Suvendu Kar.

Figure 1
Figure 1. Figure 1: Size of matrix vs. mean rela￾tive error in multiplying two Type-1 ma￾trices. 5rlog ns components of the SVD were used. A priori estimates using The￾orem 3.6 ignoring its Op ? 1 n q second term, and posterior estimates using Corollary 3.7 are also plotted above. While the former is smaller than the actual errors for these moderate values of n, the latter provides estimates that overlap with the observed rel… view at source ↗
Figure 3
Figure 3. Figure 3: Size of matrix vs. mean rela￾tive error in multiplying a general and a Toeplitz matrix with randomly gener￾ated entries from U(0,1). 5rlog ns com￾ponents of the CD were used. A priori estimates using Theorem 3.6 ignoring its Op ? 1 n q second term, and posterior esti￾mates using Corollary 3.7 are also plot￾ted above. Both provide estimates that overlap with the observed relative error [PITH_FULL_IMAGE:fig… view at source ↗
Figure 5
Figure 5. Figure 5: Size of matrix vs. mean rela￾tive error in multiplying a general and a Toeplitz matrix with randomly gener￾ated entries from a U(0,1) distribution. 5rlog ns entries for every row/column were used in the FFT-based sparsifica￾tion [PITH_FULL_IMAGE:figures/full_fig_p018_5.png] view at source ↗
Figure 7
Figure 7. Figure 7: Run-time comparison for Randomized Outer Product vs SVD First Order [PITH_FULL_IMAGE:figures/full_fig_p020_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Runtime-ratios of known methods over the proposed approximation with 1% [PITH_FULL_IMAGE:figures/full_fig_p020_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Distribution of singular values for different types of matrices. The required [PITH_FULL_IMAGE:figures/full_fig_p029_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Distribution of circulant components for different types of matrices. The [PITH_FULL_IMAGE:figures/full_fig_p030_10.png] view at source ↗
read the original abstract

We exploit the truncated singular value decomposition and the recently proposed circulant decomposition for an efficient first-order approximation of the multiplication of large dense matrices. A decomposition of each matrix into a sum of a sparse matrix with relatively few dominant entries and a dense residue can also use the above approach, and we present methods for multiplication using a Fourier decomposition and a cycle decomposition-based sparsifications. The proposed methods scale as $\mathcal{O}(n^2 \log n)$ in arithmetic operations for $n \times n$ matrices for usable tolerances in relative error $\sim$ 1\%. We also present demonstrations of large gains in the efficiency and speed of end-to-end operations of Large Language Models (LLMs) as a motivation. Note that different decompositions for the two matrices $A$ and $B$ in the product $AB$ are also possible in this approach, using efficient a priori evaluations for suitability, to improve further on the error tolerances demonstrated here.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes efficient first-order approximations to the product of two large dense n×n matrices by combining truncated SVD, circulant decompositions, and sparsification techniques (Fourier and cycle-based). It further allows a sparse-dominant plus dense-residue split of each factor and claims that suitable truncation/sparsity choices yield O(n² log n) arithmetic cost while keeping relative error on the product near 1 %. Different decompositions may be selected for A and B via a priori suitability tests, with demonstrations of end-to-end speed-ups for LLM operations.

Significance. If the claimed complexity and error tolerance can be rigorously established for general dense matrices, the work would supply a practical route to faster matrix multiplication in machine-learning workloads. The explicit allowance for mixed decompositions and a priori selection rules is a constructive feature. The significance hinges on whether the truncation parameters remain sufficiently small (o(n/log n)) to preserve the stated scaling; without that, the result reduces to known first-order approximation techniques whose cost reverts to quadratic or cubic.

major comments (2)
  1. [Abstract and §3] Abstract and §3 (error analysis): the central claim that O(n² log n) arithmetic operations suffice for ~1 % relative error on AB requires that the SVD rank k, number of circulant terms, or dominant-entry sparsity per row remain O(log n) even for arbitrary dense factors. The first-order bound ||AB − ÃB̃|| ≤ ||A||·||B−B̃|| + ||A−Ã||·||B̃|| is stated, yet no a-priori estimate or selection rule is supplied showing that the individual relative errors ||A−Ã||/||A|| and ||B−B̃||/||B|| can be held to O(1 %) while keeping the effective rank/sparsity inside the O(log n) regime. This gap is load-bearing for the complexity assertion.
  2. [§4] §4 (LLM demonstrations): the reported speed-ups are presented for specific model weights, but the manuscript does not state the measured relative error on the actual matrix products inside the forward/backward passes, nor does it compare against a baseline that uses the same floating-point precision and hardware. Without these quantities it is impossible to verify that the observed gains correspond to the claimed 1 % tolerance rather than to a looser practical error.
minor comments (2)
  1. [§2.3] The definition of the cycle decomposition in §2.3 would benefit from an explicit small-matrix example showing the permutation cycles and the resulting sparse pattern.
  2. [Figure 2] Figure 2 caption should indicate the matrix dimensions and the precise truncation parameters used to generate the plotted error curves.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive feedback on our manuscript. We address each major comment below and have made revisions to strengthen the error analysis and experimental reporting while preserving the focus on practical approximations for large matrix products.

read point-by-point responses

  1. Referee: [Abstract and §3] Abstract and §3 (error analysis): the central claim that O(n² log n) arithmetic operations suffice for ~1 % relative error on AB requires that the SVD rank k, number of circulant terms, or dominant-entry sparsity per row remain O(log n) even for arbitrary dense factors. The first-order bound ||AB − ÃB̃|| ≤ ||A||·||B−B̃|| + ||A−Ã||·||B̃|| is stated, yet no a-priori estimate or selection rule is supplied showing that the individual relative errors ||A−Ã||/||A|| and ||B−B̃||/||B|| can be held to O(1 %) while keeping the effective rank/sparsity inside the O(log n) regime. This gap is load-bearing for the complexity assertion.

    Authors: We agree that an explicit a priori guarantee linking the selection rules to O(log n) parameter sizes for arbitrary dense matrices would make the complexity claim more robust. The manuscript already describes efficient a priori suitability tests that choose among SVD, circulant, Fourier, and cycle-based decompositions (including the sparse-dominant plus dense-residue split) on the basis of quick norm estimates. In the revised §3 we have expanded the discussion of these rules, added pseudocode for the selection procedure, and included additional numerical tables showing that, for the dense matrices encountered in the LLM setting, the chosen ranks and per-row sparsities remain O(log n) while the relative approximation errors stay near 1 %. A fully rigorous worst-case bound that holds for every possible dense factor without reference to the a priori test would require new theoretical work outside the present scope; the paper’s emphasis is on practical, verifiable approximations with demonstrated scaling. revision: partial

  2. Referee: [§4] §4 (LLM demonstrations): the reported speed-ups are presented for specific model weights, but the manuscript does not state the measured relative error on the actual matrix products inside the forward/backward passes, nor does it compare against a baseline that uses the same floating-point precision and hardware. Without these quantities it is impossible to verify that the observed gains correspond to the claimed 1 % tolerance rather than to a looser practical error.

    Authors: We thank the referee for this clarification. In the revised manuscript we now report the measured relative errors ||AB − ÃB̃||/||AB|| for every matrix product arising in the forward and backward passes of the LLM examples. We have also added direct runtime comparisons against a baseline implementation that uses identical floating-point precision, the same hardware, and the same BLAS library, confirming that the observed speed-ups are realized while keeping the relative error within the stated ~1 % tolerance. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on standard decompositions

full rationale

The paper proposes first-order approximations of AB via truncated SVD, circulant decomposition, and sparse+residue splits, then states the resulting arithmetic cost as O(n² log n) once the truncation/sparsity parameters are chosen for ~1% relative error. No equation reduces a claimed prediction to a fitted parameter by construction, no uniqueness theorem is imported from self-citation, and no ansatz is smuggled via prior work. The complexity statement follows directly from the known costs of FFT-based circulant multiplication and sparse-dense products once the effective rank or nonzero count is treated as an external input; the paper does not define that count from the target error inside its own equations. The derivation is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Based solely on the abstract; no explicit free parameters, axioms, or invented entities are detailed. The methods appear to rest on standard linear-algebra decompositions whose error properties are assumed to transfer to the product.

pith-pipeline@v0.9.0 · 5705 in / 1236 out tokens · 68184 ms · 2026-05-22T18:41:04.488714+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    Alman, R

    J. Alman, R. Duan, V. V. Williams, Y. Xu, Z. Xu, and R. Zhou , More Asymmetry Yields Faster Matrix Multiplication, pp. 2005–2039, https://doi.org/10.1137/1.9781611978322.63

    work page doi:10.1137/1.9781611978322.63 2005

  2. [2]

    Alman and V

    J. Alman and V. Vassilevska Williams , Further Limitations of the Known Approaches for Matrix Multiplication , in 9th Innovations in Theoretical Computer Science Conference (ITCS 2018), A. R. Karlin, ed., vol. 94 of Leibniz International Proceedings in Informatics (LIPIcs), Dagstuhl, Germany, 2018, Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik, pp. ...

    work page doi:10.4230/lipics.itcs.2018.25 2018

  3. [3]

    Alman and V

    J. Alman and V. V. Williams , A Refined Laser Method and Faster Matrix Multiplication , pp. 522–539, https://doi.org/10.1137/1.9781611976465.32

    work page doi:10.1137/1.9781611976465.32

  4. [4]

    Ambainis, Y

    A. Ambainis, Y. Filmus, and F. Le Gall , Fast matrix multiplication: Limitations of the coppersmith-winograd method, in Proceedings of the forty-seventh annual ACM symposium on Theory of Computing, STOC ’15, ACM, June 2015, https://doi.org/10.1145/2746539. 2746554

    work page doi:10.1145/2746539 2015

  5. [5]

    Boisvert, R

    R. Boisvert, R. Pozo, K. Remington, R. Barrett, and J. Dongarra , Matrix market : A web resource for test matrix collections , Quality of Numerical Software, Assessment and Enhancement, (1996), https://doi.org/10.1007/978-1-5041-2940-4 9

    work page doi:10.1007/978-1-5041-2940-4 1996

  6. [6]

    Chellapilla, S

    K. Chellapilla, S. Puri, and P. Simard, High performance convolutional neural networks for document processing, in Tenth international workshop on frontiers in handwriting recogni- tion, Suvisoft, 2006

    work page 2006

  7. [7]

    Christandl, P

    M. Christandl, P. Vrana, and J. Zuiddam , Barriers for fast matrix multiplication from irreversibility, Theory of Computing, 17 (2021), p. 1–32, https://doi.org/10.4086/toc.2021. v017a002

    work page doi:10.4086/toc.2021 2021

  8. [8]

    D. C. Ciresan, U. Meier, J. Masci, L. Maria Gambardella, and J. Schmidhuber , Flex- ible, high performance convolutional neural networks for image classification , in IJCAI proceedings-international joint conference on artificial intelligence, vol. 22, Citeseer, 2011, p. 1237

    work page 2011

  9. [9]

    Davie and A

    A. Davie and A. Stothers , Improved bound for complexity of matrix multiplication , Pro- ceedings of the Royal Society of Edinburgh: Section A Mathematics, 143 (2013), https: //doi.org/10.1017/S0308210511001648

    work page doi:10.1017/s0308210511001648 2013

  10. [10]

    Drineas, R

    P. Drineas, R. Kannan, and M. W. Mahoney , Fast monte carlo algorithms for matrices i: Approximating matrix multiplication , SIAM Journal on Computing, 36 (2006), pp. 132– 157, https://doi.org/10.1137/S0097539704442684

    work page doi:10.1137/s0097539704442684 2006

  11. [11]

    SIAM Review53(2), 217–288 (2011)

    N. Halko, P. G. Martinsson, and J. A. Tropp , Finding structure with randomness: Proba- bilistic algorithms for constructing approximate matrix decompositions , SIAM Review, 53 (2011), pp. 217–288, https://doi.org/10.1137/090771806

    work page doi:10.1137/090771806 2011

  12. [12]

    Hariprasad and M

    M. Hariprasad and M. Venkatapathi , Circulant decomposition of a matrix and the eigen- values of toeplitz type matrices , Applied Mathematics and Computation, 468 (2024), p. 128473, https://doi.org/10.1016/j.amc.2023.128473

    work page doi:10.1016/j.amc.2023.128473 2024

  13. [13]

    Hutchinson , A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines, Communications in Statistics - Simulation and Computation, 18 (1989), pp

    M. Hutchinson , A stochastic estimator of the trace of the influence matrix for laplacian smoothing splines, Communications in Statistics - Simulation and Computation, 18 (1989), pp. 1059–1076, https://doi.org/10.1080/03610918908812806

    work page doi:10.1080/03610918908812806 1989

  14. [14]

    Kannan and S

    R. Kannan and S. Vempala , Randomized algorithms in numerical linear algebra , Acta Nu- merica, 26 (2017), p. 95–135, https://doi.org/10.1017/S0962492917000058. 28 S. KAR, HARIPRASAD M., SAI GOWRI J. N., AND M. VENKATAPATHI

    work page doi:10.1017/s0962492917000058 2017

  15. [15]

    Kar, Example codes for first order multiplication of truncated decompositions , 2025, https: //github.com/SuvenduKar/Efficient-approximations-of-matrix-multiplication

    S. Kar, Example codes for first order multiplication of truncated decompositions , 2025, https: //github.com/SuvenduKar/Efficient-approximations-of-matrix-multiplication

    work page 2025

  16. [16]

    F. Le Gall, Algebraic complexity theory and matrix multiplication , in Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC ’14, ACM, July 2014, https://doi.org/10.1145/2608628.2627493

    work page doi:10.1145/2608628.2627493 2014

  17. [17]

    E. S. Meckes, The random matrix theory of the classical compact groups , vol. 218, Cambridge University Press, 2019

    work page 2019

  18. [18]

    Strassen , Gaussian elimination is not optimal , Numerische Mathematik, 13 (1969), pp

    V. Strassen , Gaussian elimination is not optimal , Numerische Mathematik, 13 (1969), pp. 354–356, https://doi.org/10.1007/BF02165411

    work page doi:10.1007/bf02165411 1969

  19. [19]

    Vaswani, N

    A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, Attention is all you need , Advances in neural information processing systems, 30 (2017)

    work page 2017

  20. [20]

    V. V. Williams, Multiplying matrices faster than coppersmith-winograd, STOC ’12, New York, NY, USA, 2012, Association for Computing Machinery, p. 887–898, https://doi.org/10. 1145/2213977.2214056. EFFICIENT APPROXIMATIONS OF MATRIX MULTIPLICATION 29 Toeplitz Block Toeplitz Bus494 Bus662 Hankel Kappa matrix Dog image Symmetric Random General Random Type-1 ...

    work page arXiv 2012