Strassen 算法

Strassen 算法(Strassen Algorithm)是一种矩阵乘法的分治算法,由德国数学家福尔克·施特拉森(Volker Strassen)于 1969 年提出。在此之前学界普遍认为矩阵乘法必须要 O(n³) 次运算,施特拉森的构造first次把指数压到 log2(7) 约等于 2.807,震动了整个算法界,并开创了快速矩阵乘法这一研究方向。

概述

按定义计算两个 n 阶方阵的乘积需要 n³ 次标量乘法。朴素分治把每个矩阵切成四个 n/2 阶子块,仍需 8 次子块乘法,复杂度不变。施特拉森发现,通过精心设计的加减组合,只用 7 次子块乘法就能凑出结果的四个子块,于是递归式变为 T(n)=7T(n/2)+O(n²),解得约 O(n^2.807)。乘法次数的减少以更多的加减法和中间矩阵为代价,因此只有矩阵足够大时才有实际收益。

核心特点

• 分治结构:矩阵四分块,递归计算 7 个中间积 M1 到 M7,再由它们的加减组合拼出结果。
• 复杂度:O(n^log2(7)),是第一个次立方矩阵乘法算法。
• 实用门槛:递归到小规模(实践中常为几十到几百阶)后应切换回朴素乘法,以避免常数开销反超。
• 数值稳定性:误差界比朴素算法弱,对精度敏感的场景需谨慎。

发展与应用

Strassen 算法引发了持续数十年的指数竞赛:1990 年科珀史密斯与维诺格拉德把理论指数降到约 2.376,近年经多轮改进已低于 2.372,但这些理论算法常数巨大,毫无实用价值,目前真正用于工程的次立方算法仍以 Strassen 及其变体为主。部分高性能线性代数库在大矩阵上采用 Strassen 分治层,深度学习编译器也曾探索用它减少卷积中的乘法量。矩阵乘法指数究竟能否达到 2,至今仍是理论计算机科学的著名开放问题。

常见问题

问:实际软件为什么很少默认启用 Strassen 算法？答:现代 BLAS 库靠缓存分块与向量化把朴素算法的硬件效率压榨到极致,Strassen 的额外加减与内存访问只有在相当大的矩阵上才划算,且数值误差略大。

问:非 2 的幂阶矩阵怎么办？答:补零填充到合适规模,或在奇数维度上做削皮处理,均不影响渐近复杂度。

问:7 次乘法还能再少吗？答:对 2×2 分块已证明 7 次是最少的;进一步降指数需要更大的分块与完全不同的技术,如激光方法。