Efficient approximations of matrix multiplication using truncated decompositions
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910161089593344 |
|---|---|
| author | Kar, Suvendu M., Hariprasad N., Sai Gowri J. Venkatapathi, Murugesan |
| author_facet | Kar, Suvendu M., Hariprasad N., Sai Gowri J. Venkatapathi, Murugesan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_19308 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Efficient approximations of matrix multiplication using truncated decompositions Kar, Suvendu M., Hariprasad N., Sai Gowri J. Venkatapathi, Murugesan Numerical Analysis 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. |
| title | Efficient approximations of matrix multiplication using truncated decompositions |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2504.19308 |