2.5 Strassen 矩阵乘法

这一篇，分治进入代数世界。问题是矩阵乘法：两个 $n\times n$ 矩阵相乘。朴素做法 $O(n^3)$ ，1969 年 Strassen 用一个天才的分治构造，把它降到 $O(n^{2.807})$ 。这是第一个打破 $O(n^3)$ 屏障的算法，震撼了整个领域，也开启了对"矩阵乘法到底能多快"的持续探索（至今仍是开放问题）。它也是分治最反直觉的应用——你很难想到"矩阵相乘"这种代数运算能用分治加速。

1.朴素矩阵乘法为什么是 $O(n^3)$

$C=AB$ ， $C_{ij}=\sum_{k=1}^{n}A_{ik}B_{kj}$ 。每个元素是两个长度 $n$ 向量的点积， $O(n)$ ； $C$ 有 $n^2$ 个元素，所以总共 $O(n^3)$ 。三个嵌套循环，没有捷径——至少朴素实现里没有。

2.朴素的分治：还是 $O(n^3)$

分治的第一反应：把矩阵四等分。

A=\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix},\quad B=\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{pmatrix}

C_{11}=A_{11}B_{11}+A_{12}B_{21},\quad C_{12}=A_{11}B_{12}+A_{12}B_{22},\quad \dots

每个 $C_{ij}$ 是两个"半大小"子矩阵乘积的和。算 8 个 $\frac{n}{2}\times\frac{n}{2}$ 的子乘积，加上常数次 $\frac{n}{2}\times\frac{n}{2}$ 的加法（ $O(n^2)$ ）：

T(n)=8T(n/2)+\Theta(n^2)=\Theta(n^3)

（用主定理： $n^{\log_2 8}=n^3$ ，和 $n^2$ 比， $n^3$ 主导，所以 $\Theta(n^3)$ 。）

朴素的分治没省到任何东西——8 个子问题和朴素法的三个嵌套循环本质上一样。问题出在：子问题太多了。Strassen 的天才之处就在于——减少子乘积的个数。

3.Strassen 的魔法：7 个子乘积就够

Strassen 找到了一组巧妙的组合，只用 7 个（而不是 8 个）半大小矩阵乘法，就能算出 $C$ 。多出来的代价是更多次矩阵加减法，但加减法是 $O(n^2)$ ，比乘法 $O(n^{\log 7})$ 便宜，所以值得。

定义 7 个中间量（每个是若干个半大小子矩阵的加减组合）：

\begin{aligned} M_1&=(A_{11}+A_{22})(B_{11}+B_{22})\\ M_2&=(A_{21}+A_{22})B_{11}\\ M_3&=A_{11}(B_{12}-B_{22})\\ M_4&=A_{22}(B_{21}-B_{11})\\ M_5&=(A_{11}+A_{12})B_{22}\\ M_6&=(A_{21}-A_{11})(B_{11}+B_{12})\\ M_7&=(A_{12}-A_{22})(B_{21}+B_{22}) \end{aligned}

然后用这 7 个 $M$ 拼出 $C$ ：

\begin{aligned} C_{11}&=M_1+M_4-M_5+M_7\\ C_{12}&=M_3+M_5\\ C_{21}&=M_2+M_4\\ C_{22}&=M_1-M_2+M_3+M_6 \end{aligned}

你可以代入验证（展开 $M_i$ 把 $A_{ij}B_{kl}$ 项归并），结果和朴素乘法一模一样。这 7 个组合是 Strassen 凑出来的"代数恒等式"，没有几何直觉，纯粹是聪明的代数安排。

4.复杂度： $T(n)=7T(n/2)+O(n^2)=O(n^{\log_2 7})\approx O(n^{2.807})$

现在子乘积只剩 7 个：

T(n)=7T(n/2)+\Theta(n^2)

用主定理（4.2 节）： $a=7, b=2$ ， $n^{\log_b a}=n^{\log_2 7}\approx n^{2.807}$ 。它和 $f(n)=n^2$ 比， $n^{2.807}$ 更大（ $2.807>2$ ），所以属于主定理的第一种情形， $T(n)=\Theta(n^{\log_2 7})\approx\Theta(n^{2.807})$ 。

从 $n^3$ 到 $n^{2.807}$ ，省了多少？ $n=1000$ 时， $n^3=10^9$ ， $n^{2.807}\approx 2.7\times 10^8$ ，省了约 4 倍。 $n$ 越大省得越多。对超大矩阵（比如某些科学计算），这是实打实的加速。

5.这为什么重要：算法复杂度的天花板之争

Strassen 的贡献远不止一个具体的加速。它打破了"矩阵乘法天然是 $O(n^3)$ "的成见，催生了一个根本问题：

矩阵乘法到底能多快？ 它的复杂度下界是什么？

Strassen 之后，人们一路改进：Pan、Bini、Coppersmith-Winograd、直到 2023 年前后最优结果约 $O(n^{2.37})$ 。而且我们至今不知道这个问题的真正下界——它可能在 $O(n^{2+\epsilon})$ 甚至接近 $O(n^2)$ （理论上 $n^2$ 是下界，因为光读入矩阵就要 $n^2$ ）。这个" $\omega$ （矩阵乘法指数）到底是多少"的问题，是理论计算机科学最著名的开放问题之一。

这是分治思想能达到的深度——不是优化常数，而是改变渐进指数。第二卷的 FFT（2.6）会再给你一次这种震撼（多项式乘法 $O(n^2)\to O(n\log n)$ ）。

6.实践中的取舍

值得说一句：Strassen 虽然渐进更快，但常数大（那一堆矩阵加减法不是白干的），而且数值稳定性不如朴素法（浮点误差累积）。所以实践中：

小矩阵（ $n$ 小于几十到几百）：朴素 $O(n^3)$ 反而更快（常数小、缓存好）。
大矩阵：Strassen 才划算，通常的做法是"分治到一定规模就切回朴素法"（混合策略，和 1.1 插入排序在小段切回一个道理）。
高精度要求：可能放弃 Strassen，因为稳定性问题。

渐进复杂度和实际性能不是一回事——这是 1.8 节反复强调的，Strassen 是绝佳的例子：它理论上更快，但只有在 $n$ 够大时才真的更快。

7.练习

Q1. 朴素分治矩阵乘法用 8 个子乘积， $T(n)=8T(n/2)+O(n^2)=\Theta(n^3)$ 。Strassen 减到 7 个，为什么就能打破 $O(n^3)$ ？

因为 $\log_2 8=3$ 而 $\log_2 7\approx 2.807$ 。主定理下 $T(n)=aT(n/2)+O(n^2)$ 的解是 $\Theta(n^{\log_2 a})$ （当 $\log_2 a>2$ ）。8 个子问题给 $n^3$ ，7 个给 $n^{2.807}$ 。少一个子乘积，指数就从 3 降到 2.807——这就是 Strassen 的全部魔法：靠减少递归分支数改变指数。

Q2. Strassen 多了很多矩阵加减法（ $O(n^2)$ ），为什么这些加减法不拖慢算法？

因为加减法是 $O(n^2)$ ，而子乘积是 $O(n^{2.807})$ 。 $n^{2.807}$ 严格大于 $n^2$ ，所以乘法主导，加减法被"吸收"进了更低阶。这正是主定理第一种情形（ $f(n)$ 比子问题总和便宜）。用便宜的加减换昂贵的乘，是 Strassen 的权衡，也是一切"减少乘法个数"代数优化的思路。

Q3.（思考题） Strassen 渐进更快，为什么实际工程在中等规模矩阵上仍用朴素 $O(n^3)$ ？

因为 Strassen 常数大（一堆加减法、递归开销）、缓存不友好（子矩阵访问跳跃）、数值稳定性差（浮点误差累积）。只有 $n$ 足够大时， $n^{2.807}$ 的优势才压过这些常数代价。工程上常用混合策略：大矩阵用 Strassen 分治，到一定规模切回朴素法。这再次说明"渐进复杂度"和"实际性能"要分开看——1.8 节的核心教训。

8.小结

Strassen 用一组天才的代数组合，把矩阵乘法从 8 个子乘积压到 7 个，复杂度从 $O(n^3)$ 降到 $O(n^{2.807})$ 。它打破了" $O(n^3)$ 不可破"的成见，开启了"矩阵乘法指数 $\omega$ 到底多少"这个至今未决的开放问题。下一篇的分治收官之作——快速傅里叶变换，会给你最后一次"改变指数"的震撼。