从8次乘法到7次:Strassen 算法为何把矩阵乘法降到 O(n^2.81)
Franc0Fernand0 · x · 2026-10-14
作者澄清一个常见误解:矩阵乘法的加速不是靠把大矩阵切成小块(分块本身不会更快),而是靠减少乘法次数。朴素算法是 O(n³);分治法把每个矩阵分成 4 个 n/2×n/2 子矩阵,但每层递归仍需 8 次子矩阵乘法和 4 次加法,复杂度依然是 O(n³)。Strassen 算法用相同的分块方式,但以不同的组合方式合并结果,每步只需 7 次乘法,复杂度降到 O(n^2.81)。看似微小的改进,在大规模输入下意义显著。配图为 Strassen 1969 年论文中七个乘积公式的一页。
「研究」频道最新
- arXiv 论文为 StopGrad 正名：无损失函数也能收敛到正确解 — srush_nlp · 2026-10-23
- PEARL 演示：LLM 机器人自主核对实验结果、修正方案并复测 — KevinKaichuang · 2026-10-23
- 伯克利 StyleStream 2.0：流式语音转换延迟降至 520ms 提速一倍 — Berkeley · 2026-10-23
- 数学博士生宣布离开学术界：AI 正让数学变得面目全非 — pickover · 2026-10-23
- ICLR 投稿现 LLM 残留自评：作者模型自曝结果不显著 — _onionesque · 2026-10-23
- AKV 推理系统让 Agent 自管 KV 缓存,成本降 27.7% 准确率反升 — _akhaliq · 2026-10-23