🔢 mathematics

Efficient approximations of matrix multiplication using truncated decompositions

This paper proposes an efficient method for approximating large dense matrix multiplication in $\mathcal{O}(n^2 \log n)$ time by utilizing truncated singular value, circulant, and cycle-based decompositions to reduce computational complexity while maintaining usable error tolerances, specifically targeting performance gains in Large Language Model (LLM) operations.

Original authors: Suvendu Kar, Hariprasad M., Sai Gowri J. N., Murugesan Venkatapathi

Published 2026-04-27

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Suvendu Kar, Hariprasad M., Sai Gowri J. N., Murugesan Venkatapathi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a professional chef tasked with preparing a massive banquet for 1,000 guests. You have two huge crates of ingredients (Matrix A and Matrix B) that need to be combined (multiplied) to create the final feast (Matrix AB).

If you try to follow every single recipe to the letter, chopping every tiny herb and measuring every grain of salt perfectly, you will be in the kitchen for weeks. The guests will leave hungry, and you will collapse from exhaustion. This is the problem with exact matrix multiplication: it is incredibly "expensive" in terms of time and computer power.

This paper proposes a way to cook that feast much faster by using "Smart Shortcuts"—approximations that give you a meal that tastes 99% as good as the original, but in a fraction of the time.

Here is how they do it, using three different "cooking styles":

1. The "Main Ingredients" Method (SVD Decomposition)

Imagine you realize that most of the flavor in your banquet comes from just a few key ingredients: salt, pepper, garlic, and onions. The rest—the tiny sprigs of parsley or the microscopic bits of spice—don't actually change the overall taste that much.

In math, this is called Singular Value Decomposition (SVD). The researchers say: "Let's identify the 'heavy hitters' (the most important parts of the matrix) and multiply those perfectly. Then, we’ll take a quick, rough look at the 'tiny spices' (the residue) and add them in just enough to keep the flavor right."

The Result: You get a massive speed boost because you aren't spending hours obsessing over the parsley.

2. The "Pattern Recognition" Method (Circulant Decomposition)

Imagine you are making a giant sheet of puff pastry. Instead of treating every single flake of dough as a unique object, you realize the pastry follows a repeating pattern: fold, roll, repeat. Because you recognize the pattern, you don't have to think about every flake; you just apply the "pattern rule" over and over.

This is Circulant Decomposition. Many real-world data sets (like images or signals) have repeating patterns or "cycles." The researchers found that if you break a matrix down into these repeating cycles, you can use a mathematical "cheat code" called the Fast Fourier Transform (FFT) to multiply them incredibly quickly.

The Result: It’s like using a cookie cutter instead of hand-shaping 1,000 individual cookies.

3. The "Essential Sketch" Method (Fourier Sparsification)

Imagine you are looking at a beautiful, highly detailed landscape painting. If you want to describe it to a friend quickly, you don't describe every single blade of grass. Instead, you describe the big shapes: "There is a blue sky, a green hill, and a brown tree." You've "sparsified" the image—keeping the important shapes and ignoring the tiny details.

This is Fourier Sparsification. The researchers transform the matrix into a "frequency" version (like turning a complex song into just its main melody and bassline). They keep the loud, dominant notes and throw away the quiet, background static.

The Result: You get a "sketch" of the multiplication that is much lighter and faster to process.

Why does this matter in the real world? (The LLM Connection)

The paper specifically mentions Large Language Models (LLMs)—the brains behind things like ChatGPT.

When you type a prompt into an AI, the computer has to perform billions of these "ingredient combinations" (matrix multiplications) to figure out what word to say next. This takes a massive amount of electricity and time.

The researchers proved that by using these "Smart Shortcuts," they could make the AI respond much faster (up to 3 times faster in some tests) without making the AI "stupid." The AI still gives smart, coherent answers because, even though we skipped the "tiny sprigs of parsley," we kept all the "garlic and onions" that actually drive the intelligence.

Summary

The Problem: Exact math is too slow for the massive data used by modern AI.
The Solution: Don't be a perfectionist. Identify the most important parts (SVD), recognize the patterns (Circulant), or focus on the big shapes (Sparsification).
The Win: Faster AI, less computing power, and almost no loss in quality.

Technical Summary: Efficient Approximations of Matrix Multiplication Using Truncated Decompositions

1. Problem Statement

The fundamental bottleneck in many modern computational tasks—ranging from scientific simulations to Deep Learning—is the multiplication of large, dense matrices. While exact multiplication of two $n \times n$ matrices requires $O(n^3)$ arithmetic operations, and advanced algorithms like Strassen or Coppersmith-Winograd offer better asymptotic scaling (e.g., $O(n^{2.37})$ ), these are notoriously difficult to implement efficiently in practice.

The authors address the need for approximate matrix multiplication, where the goal is to trade a controlled amount of precision (relative error) for a significant reduction in computational complexity. Existing randomized approximation methods often lack the precision or efficiency required for widespread practical impact.

2. Methodology

The core innovation of the paper is the proposal of a "first-order approximation" approach. Instead of simply multiplying truncated versions of two matrices (a zeroth-order approximation), the authors include "residue" terms to capture more information without significantly increasing complexity.

Given two matrices $A$ and $B$ , they are decomposed into a sum of dominant components ( $A_i, B_k$ ) and a dense residue ( $\Delta A, \Delta B$ ):
$A \approx \sum A_i + \Delta A, \quad B \approx \sum B_k + \Delta B$
The proposed first-order approximation $M$ is:
$M \approx \sum (A_i B) + \sum (\Delta A B_k)$
This approach allows the multiplication to scale as $O(n^2 \log n)$ or $O(kn^2)$ depending on the decomposition used, rather than $O(n^3)$ .

The paper explores three distinct decomposition strategies:

Singular Value Decomposition (SVD): Uses randomized algorithms to extract the $k$ largest singular value components. This is highly effective for low-rank matrices.
Circulant Decomposition (CD): Decomposes a matrix into $n$ circulant matrices using the Fast Fourier Transform (FFT). This is particularly efficient for matrices with periodic structures (e.g., Toeplitz or Hankel matrices).
Fourier-domain Sparsification: Expands rows and columns using Fourier series and retains only the most dominant frequencies, effectively sparsifying the matrix in the frequency domain.

3. Key Contributions

First-Order Approximation Framework: A mathematical framework that significantly reduces relative error compared to standard truncated (zeroth-order) multiplications by incorporating residue-component products.
Error Estimation Theory: The authors provide rigorous theoretical bounds for the expected relative error. They demonstrate that the error in the product can be smaller than the product of the individual truncation errors, and they provide methods to estimate these errors a priori (before multiplication) and a posteriori (after multiplication).
Complexity Reduction: They prove that for a usable tolerance (e.g., 1% error), the arithmetic operations scale as $O(n^2 \log n)$ , providing a massive speedup over $O(n^3)$ .
Complementarity Analysis: The paper identifies which decomposition is best suited for specific matrix types (e.g., SVD for low-rank, CD for periodic/structured matrices).

4. Results

The authors validated their methods through extensive numerical experiments:

Matrix Types: They tested various matrices, including Symmetric, Toeplitz, Hankel, DFT models, and unstructured random matrices.
SVD Performance: For low-rank and structured matrices, the first-order SVD approach achieved 1% relative error with significantly fewer components than traditional randomized low-rank methods.
CD Performance: For matrices with periodicity (like Toeplitz), the Circulant Decomposition was highly efficient and agnostic to the matrix rank.
Large Language Models (LLMs): In a real-world application involving the OPT-125M and OPT-1.3B models, the authors demonstrated that the first-order approximation creates a "Pareto front" between speed and accuracy.
- For the OPT-1.3B model, they achieved up to a 3.07x end-to-end speedup in the prefilling phase while maintaining near-lossless perplexity (accuracy).
Run-time Gains: Experiments on Apple M4 Pro hardware showed that the proposed methods outperform naive exact multiplication and existing randomized methods as matrix dimensions increase.

5. Significance

This work is highly significant for the field of High-Performance Computing (HPC) and Artificial Intelligence. By providing a mathematically sound way to approximate matrix multiplication with predictable error bounds, it offers a path to:

Accelerating LLM Inference: Reducing the latency of the "prefilling" stage in large-scale transformer models.
Energy Efficiency: Reducing the total FLOPs required for massive linear algebra workloads, which directly translates to lower power consumption in data centers.
Scalability: Providing algorithms that scale much more gracefully with increasing matrix dimensions, enabling the processing of larger datasets and more complex models.