Efficient approximations of matrix multiplication using truncated decompositions
Suvendu Kar, Hariprasad M, Sai Gowri J. N, Murugesan Venkatapathi · 2025
Read Efficient approximations of matrix multiplication using truncated decompositions by Suvendu Kar, Hariprasad M, Sai Gowri J. N, Murugesan Venkatapathi (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-2504-19308.txt.
Introduction
Suvendu Kar and three co-authors speed up big matrix math with cut down forms in a 2025 paper. Matrix products sit at the heart of large AI models, and full products on huge dense grids eat time and power. Their plan trims each matrix to a small set of strong parts before the multiply step.
One path cuts a classic split at a set rank. A newer path splits by rings. They also split each matrix into a sparse strong part plus a dense rest, then use wave based or cycle based trims. The work scales near the square of the size times a log term for errors near one percent. Tests tied to large language models showed big speed gains.
Catalog record
| CREATOR | Suvendu Kar, Hariprasad M, Sai Gowri J. N, Murugesan Venkatapathi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 104 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-19308
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Efficient approximations of matrix multiplication using truncated decompositions Suvendu Kar, Hariprasad M, Sai Gowri J. N, Murugesan Venkatapathi 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 𝒪 ( n 2 log n ) \mathcal{O}(n^{2}\log n) in arithmetic operations for n × n 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 A and B B in the product A B AB are also possible in this approach, using efficient a priori evaluations for suitability, to improve further on the error tolerances demonstrated here. keywords matrix approximations, singular values, circulant matrix, sparsification, Fast Fourier Transform. † † runningheads: Efficient Approximations of Matrix Multiplication / S. Kar, Hariprasad M., Sai Gowri J. N., and M. Venkatapathi AMS 65F55, 65F35, 65F25. 1 Introduction Reducing the scaling of arithmetic operations required in multiplying two (dense) matrices can widely increase the efficiency of computing. Even though the asymptotic scaling of the Strassen-Coppersmith-Winograd type algorithms [ 18 , 20 , 9 , 16 , 3 , 1 ] as \mathcal{O}(n^{2.37}) is attractive compared to the naive approach using \mathcal{O}(n^{3}) arithmetic operations for an exact multiplication, they have been non-trivial in practical implementation [ 4 , 2 , 7 ] . As an alternative, randomized algorithms for approximation have been proposed to incur lower computing effort at the cost of lower precision in the evaluated matrix product [ 10 , 14 ] . Nevertheless, these methods are not sufficiently precise or efficient to have a wide impact on practical computing. We propose approximations based on relatively few components of a decomposition that each multiply a general matrix efficiently, thus allowing a first-order approximation of the product of two truncated decompositions. One may also note that in the more recent applications such as the domain of deep learning, multiplication of large matrices is unavoidable. For example, the forward pass of a convolutional neural network processes data in batches and it may perform evaluations of the form Z=WX+B , with W the weights of the connections. Back-propagation computes the gradient of the loss functions using the chain rule which may again involve the multiplication of large matrices [ 8 , 6 ] . Computation of self-attention in transformers uses the product of query, key, and value matrices [ 19 ] , and such multiplication of large matrices is not restricted to the above cases. We begin with the used notations in section 1.1 , and the relevant decompositions of matrices in section 1.2 . The subsequent sections 2 , 3 , and 4 detail the methods and algorithms, a theoretical analysis of errors, and the numerical experiments, respectively. 1.1 Notations used All vectors represent a column, where unit vectors have hats with the 2-norm \lVert\hat{v}\rVert_{2}=1 , and only the other vectors \bm{v} are in bold. Matrices V are in capitals. Its columns are indicated by superscripts with V^{(i)} for the i^{th} column and rows by subscripts with V_{(i)} for the i^{th} row. Plain subscripts in V_{i} represent a particular matrix component. Row vectors \bm{v}^{T} or \bm{v}^{*} have a transpose or a conjugate transpose of the columns indicated respectively. 1.2 Relevant decompositions 1.2.1 Singular Value Decomposition Any m\times n matrix A is given by a sum of weighted rank-one matrices, where its rank r\leq min(m,n) : \displaystyle A \displaystyle=\sigma_{1}\hat{u}_{1}\hat{v}_{1}^{*}+\sigma_{2}\hat{u}_{2}\hat{v}_{2}^{*}\dots+\sigma_{r}\hat{u}_{r}\hat{v}_{r}^{*}=\sum_{k=1}^{r}\sigma_{k}\hat{u}_{k}\hat{v}_{k}^{*} \displaystyle=U\Sigma V^{*}\quad\text{ where }\hat{u}_{k}\in\mathbb{C}^{m},\hat{v}_{k}\in\mathbb{C}^{n}\text{ , and }\Sigma_{kk}=\sigma_{k}\in\mathbb{R}_{\geq 0}, where \sigma_{1}>\sigma_{2}>\dots>\sigma_{r}>0 . Given \hat{u},\hat{v} are each sets of mutually orthogonal vectors, we have: A\hat{v}_{k}=\sigma_{k}\hat{u}_{k},\text{ and }A^{*}\hat{u}_{k}=\sigma_{k}\hat{v}_{k}. Though this decomposition requires \mathcal{O}(n^{3}) for n\times n matrices, we can use randomized algorithms to evaluate only the k largest components in \mathcal{O}(kn^{2}) arithmetic operations as shown in algorithm 1 . 1.2.2 Decomposition into cycles A matrix can also be decomposed into its n cycles each containing n entries, which in turn are combinations of the 2n-1 diagonals of a matrix. Let C be the permutation matrix corresponding to a full cycle. \displaystyle C=\begin{bmatrix}0&1\\ I_{n-1}&0\end{bmatrix}_{n\times n}. (1) The decomposition of any matrix into cycles is given by A=\sum_{j=0}^{n-1}\Lambda_{j}C^{j} , where \Lambda_{j} are diagonal matrices containing n entries of a cycle of the matrix, and C^{j} is the above permutation matrix C raised to the power j . While it is equally possible to have A=\sum_{j=0}^{n-1}C^{j}\Lambda_{j} , the ordering of the diagonal elements of \Lambda_{j} differ in both cases. This decomposition requires \mathcal{O}(n^{2}) arithmetic operations for its evaluation (see section A.5 for an example). Left multiplication of a cycle to a matrix involves a cyclic permutation of the columns of the matrix followed by a scaling of the rows using the diagonal entries in the cycle, costing \sim 2n^{2} operations. The converse applies to the right multiplication of a cycle. This decomposition may be useful in approximating matrices with dominant cycles numbering k\ll n . 1.2.3 Circulant Decomposition Theorem 1 . Any n\times n matrix A is given by a sum of n circulant matrices R_{k} with phase factors given by roots of unity. \displaystyle A \displaystyle=R_{0}+R_{1}D^{1}\dots+R_{n-1}D^{n-1} \displaystyle=\sum_{k=0}^{n-1}R_{k}D^{k}\quad\text{where }D(q,q)=\omega^{q}=e^{i\frac{2\pi}{n}q}\text{, and }D(p,q)=0\text{ for }p\neq q. Proof. Using the cycle decomposition described in section 1.2.2 , \displaystyle A=\sum\limits_{j=0}^{n-1}C^{j}\Lambda_{j}. (2) Then using a Fourier series expansion of a cycle j , \displaystyle C^{j}\Lambda_{j}=C^{j}\sum_{k}r_{j,k}D^{k}. (3) where r_{j,k}=\frac{1}{n}\sum_{l}\omega^{-kl}\Lambda_{j}(l,l) . Thus we get: \displaystyle A \displaystyle=\sum_{j,k}C^{j}r_{j,k}D^{k}, \displaystyle=\sum_{k}\left(\sum_{j}r_{j,k}C^{j}\right)D^{k}=\sum_{k}R_{k}D^{k} where the circulant matrix R_{k} for a given k , has the constants r_{j,k} in all the n entries of a cycle j . This decomposition requires only \mathcal{O}(n^{2}\log n) arithmetic operations for its evaluation using a Fast Fourier Transform. 00.5ex0.5ex Remark 2 . We can show that R_{k}D^{k} are mutually orthogonal w.r.t. a Frobenius inner product \odot , where A\odot A=\sum_{i,j}\overline{A(i,j)}A(i,j)=\lVert A\rVert_{F}^{2} . We know the property of invariance of the Frobenius inner product with unitary transformations [ 12 ] . Thus, (WAW^{*})\odot(WBW^{*})=A\odot B , where the unitary matrix W(p,q)=\frac{1}{\sqrt{n}}e^{-i\frac{2\pi pq}{n}} , with p,q=0,1,2\cdots n-1 . Further, \displaystyle R_{i}D^{i}\odot R_{j}D^{j} \displaystyle=(WR_{i}D^{i}W^{*})\odot(WR_{j}D^{j}W^{*})=(WR_{i}W^{*}WD^{i}W^{*})\odot(WR_{j}W^{*}WD^{j}W^{*}) \displaystyle=(\Lambda_{i}^{\prime}C^{i})\odot(\Lambda_{j}^{\prime}C^{j})=0\text{ for }i\neq j \displaystyle=\left\|R_{i}\right\|_{F}^{2}\text{ for }i=j. where we have used known relations WD^{j}W^{*}=C^{j} , and the diagonalization of a circulant matrix in the Fourier domain as WR_{j}W^{*}=\Lambda_{j}^{\prime} . This property of orthogonality along with the decomposition in theorem 1 gives us A\odot R_{k}D^{k}=\lVert R_{k}\rVert_{F}^{2} . 1.2.4 Fourier series based decompositions We can also expand every row of the matrix A using Fourier series, giving us the following decomposition. Theorem 3 . Every matrix A \in\mathcal{C}^{m\times n} is a weighted sum of rank-one Fourier components. \displaystyle A=\sum_{k=0}^{n-1}a_{k}\hat{f}_{k}\hat{\omega}_{k}^{T}\text{, and }A\odot A=\lVert A\rVert_{F}^{2}=\sum_{k=0}^{n-1}a_{k}^{2}. where \lVert\hat{f}_{k}\rVert_{2}=\lVert\hat{\omega}_{k}\rVert_{2}=1 , and a_{k} \in \mathbb{R}_{\geq 0} . Proof. Consider the Fourier series representation of a row of A written as : \displaystyle A_{(i)} \displaystyle=\sum_{k}f_{i,k}\mathbf{1}^{T}D^{k}. Then, using the canonical basis vectors \hat{e}_{i} we have, \displaystyle A \displaystyle=\sum_{i}\hat{e}_{i}A_{(i)}=\sum_{i}\hat{e}_{i}\sum_{k}f_{i,k}\mathbf{1}^{T}D^{k} \displaystyle=\sum_{k}\sum_{i}\hat{e}_{i}f_{i,k}\mathbf{1}^{T}D^{k}=\sum_{k=0}^{n-1}\bm{f}_{k}\mathbf{1}^{T}D^{k}. Let a_{k}=\sqrt{n}\lVert\bm{f}_{k}\rVert_{2} , \hat{f}_{k}=\frac{\bm{f}_{k}}{\lVert\bm{f}_{k}\rVert_{2}} , and \hat{\omega}_{k}^{T}=\frac{1}{\sqrt{n}}\mathbf{1}^{T}D^{k} . Thus, A=\sum_{k=0}^{n-1}a_{k}\hat{f}_{k}\hat{\omega}_{k}^{T}.