🔢 mathematics

Efficient approximations of matrix multiplication using truncated decompositions

本文提出了一种利用截断奇异值分解（TSVD）和循环分解（circulant decomposition）来高效近似大规模稠密矩阵乘法的方法，在保持约1%相对误差的前提下，将计算复杂度降低至 $\mathcal{O}(n^2 \log n)$ ，并展示了其在提升大语言模型（LLM）端到端运行效率方面的巨大潜力。

原作者： Suvendu Kar, Hariprasad M., Sai Gowri J. N., Murugesan Venkatapathi

发布于 2026-04-27

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Suvendu Kar, Hariprasad M., Sai Gowri J. N., Murugesan Venkatapathi

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇文章介绍了一种让计算机进行“矩阵乘法”更快速、更聪明的方法。为了让你理解，我们先跳出数学，用一个生活中的例子来做类比。

1. 核心矛盾：大厨与“超级订单”

想象你是一位世界顶级的厨师，你的任务是处理每天成千上万份的“超级订单”（这就是矩阵乘法）。

传统的做法（精确计算）： 每一份订单，你都必须严格按照菜谱，把每一个调料、每一克盐都精准地称量并放入锅中。这非常准确，但当订单量达到几百万份时，你会被累死，厨房也会瘫痪。
目前的改进方案（随机近似）： 有些人建议：“既然太累，我们干脆随便抓一把盐就行了！”这虽然快了，但味道变得一塌糊g，完全没法吃。

这篇论文的目标是： 找到一种“既能让你飞速出餐，又能保证味道几乎没差别”的神奇方法。

2. 论文的“秘密武器”：拆解与“第一阶近似”

这篇论文的核心思想不是直接去硬啃那个巨大的订单，而是把订单**“拆解”**成几个部分。它提出了三种不同的“拆解工具”：

工具 A：奇异值分解 (SVD) —— “抓大放小法”

类比： 想象你在看一部好莱坞大片。你不需要记住每一个像素点的颜色，你只需要记住主角是谁、主要剧情是什么。

做法： 把矩阵拆成“最重要的核心部分”和“微不足道的杂质部分”。
论文的创新： 以前的方法只算“核心部分”，味道会变。这篇论文说：“我们不仅算核心部分，还要把核心部分和那些‘杂质’进行一次简单的互动（称为第一阶近似）。”这样，味道就非常接近原味了。

工具 B：循环分解 (Circulant Decomposition) —— “节奏律动法”

类比： 想象你在听一段复杂的交响乐。虽然乐器很多，但其实是有节奏（周期性）的。

做法： 如果矩阵里有一些重复的、有规律的模式，我们就把这些“节奏”提取出来。
优势： 对于那些有规律的矩阵（比如处理图像或某些物理数据），这种方法快得惊人，因为它利用了数学里的“快速傅里叶变换”（FFT），就像是学会了用节奏感来快速切菜。

工具 C：傅里叶稀疏化 —— “滤镜精简法”

类比： 就像给照片加了一个“智能滤镜”。

做法： 很多数据其实是“冗余”的。我们通过数学变换，把那些对结果影响不大的“背景噪音”直接滤掉，只留下最亮眼的“高频特征”。

3. 为什么这很重要？（以 ChatGPT 为例）

你可能在想：“这跟我有什么关系？”

现在的大语言模型（LLM），比如 ChatGPT，其大脑运作的核心就是海量的矩阵乘法。当你问它问题时，它在后台进行着天文数字级别的计算。

痛点： 随着模型越来越大（比如从 1.25 亿参数变成 13 亿甚至万亿参数），计算量会呈爆炸式增长，导致回答变慢，甚至耗电惊人。
论文的贡献： 作者在论文末尾做了一个实验，直接把这种方法应用到了大模型上。结果发现：在保证模型说话逻辑（困惑度/准确性）几乎不变的情况下，计算速度得到了巨大的提升！

4. 总结：这篇论文说了什么？

如果用一句话总结：

“我们发明了一种聪明的‘偷懒’艺术：通过把复杂的数学任务拆解成‘精华’与‘残余’，并巧妙地让它们进行一次轻量级的互动，我们让计算机在处理海量数据时，能以极快的速度完成任务，且几乎不损失精度。”

这就像是给计算机装上了一个“智能大脑”，让它不再做无意义的体力活，而是学会了“抓重点”。

这是一篇关于利用截断分解（Truncated Decompositions）实现高效矩阵乘法近似的研究论文。以下是对该论文的详细技术总结：

1. 研究问题 (Problem)

在深度学习（如 Transformer 架构）、数值模拟和大数据处理中，大规模稠密矩阵的乘法是计算的核心瓶颈。

现有挑战： 虽然存在渐进复杂度较低的算法（如 Strassen 算法），但它们在实际工程中难以实现。现有的随机近似算法虽然降低了计算量，但在精度和效率之间难以达到理想的平衡，无法对实际计算产生广泛影响。
核心目标： 寻找一种既能显著降低算术运算复杂度（从 $O(n^3)$ 降低到 $O(n^2 \log n)$ 级别），又能保持高精度（相对误差 $\le 1\%$ ）的矩阵乘法近似方法。

2. 研究方法 (Methodology)

论文的核心思想是一阶近似（First-order Approximation）。作者不只是简单地对两个矩阵进行截断后相乘（零阶近似），而是通过结合“主成分”与“残差项”来提高精度。

对于两个矩阵 $A$ 和 $B$ ，将其分别分解为：
$A = A_i + \Delta A$ （ $A_i$ 为主成分， $\Delta A$ 为残差）
$B = B_k + \Delta B$ （ $B_k$ 为主成分， $\Delta B$ 为残差）

一阶近似公式为：
$M \approx A_i B + \Delta A B_k$
（即：主成分与全矩阵相乘 + 残差与另一矩阵的主成分相乘，忽略高阶项 $\Delta A \Delta B$ ）。

论文提出了三种基于不同分解方式的近似路径：

基于奇异值分解 (SVD) 的近似：
- 利用随机化算法（Randomized SVD）快速提取前 $k$ 个最大的奇异值分量。
- 适用于具有低有效秩（Low effective rank）的矩阵。
基于循环分解 (Circulant Decomposition, CD) 的近似：
- 利用快速傅里叶变换 (FFT) 将矩阵分解为 $n$ 个循环矩阵。
- 通过保留能量最大的若干个循环分量来构建近似。
- 优势： 对具有周期性结构的矩阵（如 Toeplitz 矩阵）非常有效，且对矩阵的秩不敏感。
基于傅里叶域稀疏化 (Fourier-domain Sparsification) 的近似：
- 将矩阵变换到频域，仅保留每个行/列中能量最大的 $k$ 个频率分量，实现矩阵的稀疏化。

3. 核心贡献 (Key Contributions)

理论分析： 论文详细推导了近似误差的界限。证明了在特定条件下（如残差项具有独立分布或平坦谱），一阶近似的相对误差可以被有效控制，且误差估计可以通过 $O(n^2)$ 的复杂度预先计算。
算法复杂度优化： 提出的方法将计算复杂度从传统的 $O(n^3)$ 降低到了 $O(n^2 \log n)$ 或 $O(kn^2)$ ，这在处理大规模矩阵时具有显著的规模优势。
误差估计模型： 提出了基于 Frobenius 范数的误差估计方法，允许用户在实际计算前评估分解的适用性，或在计算后评估精度。

4. 实验结果 (Results)

论文通过多种类型的矩阵进行了广泛的数值实验：

矩阵类型： 包括对称矩阵、Toeplitz 矩阵、Hankel 矩阵、图像数据以及具有特定奇异值分布的合成矩阵。
SVD 表现： 在处理低秩矩阵（如 Type-1 矩阵）时，SVD 方法表现极佳。
CD 表现： 在处理具有周期性结构的矩阵（如 Toeplitz 矩阵）时，循环分解法在保持低误差的同时，所需的计算分量远少于 SVD。
LLM 应用测试（关键结果）：
- 在 OPT-125M 和 OPT-1.3B 大语言模型的推理阶段（Prefilling 阶段）进行了端到端测试。
- 结论： 采用一阶 SVD 近似可以在保持模型困惑度（Perplexity）几乎不变（即精度几乎无损）的情况下，实现显著的加速。对于 1.3B 参数模型，端到端加速比达到了约 3.07倍。

5. 研究意义 (Significance)

工程实践价值： 该研究为大规模深度学习模型的推理加速提供了一种数学上严谨且工程上可行的方案。
计算效率突破： 通过将矩阵乘法从“计算密集型”转向“分解+高效分量乘法”，为处理超大规模稠密矩阵开辟了新路径。
通用性： 论文提出的框架不仅适用于 SVD，还可以扩展到其他分解方式，为数值线性代数领域提供了一个通用的近似计算范式。