改进的激光方法与更快的矩阵乘法

Josh Alman and Virginia Vassilevska Williams. 2021. A refined laser method and faster matrix multiplication. In Proceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '21). Society for Industrial and Applied Mathematics, USA, 522–539.

Josh Alman 和 Virginia Vassilevska Williams 在这篇发表于2021年SIAM的论文中，通过对激光方法的精妙改进，成功将矩阵乘法指数$\omega$的上界从2.37287降低到2.37286。虽然改进幅度看似微小，但这代表了自1986年以来该领域采用的核心技术方法的一次重要突破。

第一章：引言与背景

1.1 矩阵乘法复杂度问题

矩阵乘法的算法复杂度是理论计算机科学中最引人入胜的开放问题之一。问题的核心在于确定指数$\omega$，它定义为：

$$\omega := \inf\{r \in \mathbb{R} : n \times n \text{矩阵可以用} O(n^r) \text{次域运算相乘}\}$$

从定义可以看出，$\omega \geq 2$（因为必须输出$n^2$个元素），而朴素算法给出$\omega \leq 3$。自1969年Strassen证明$\omega < 2.81$以来，一长串研究工作发展出了强大的技术工具箱，最终在本文之前达到了$\omega < 2.37287$的最佳界限。

矩阵乘法算法的发展历程可以概括为几个关键阶段。早期工作（1969-1986）主要关注于发现新的递归算法结构。从1986年开始，Strassen引入的激光方法成为主导技术，所有后续改进都基于这一框架。Coppersmith和Winograd在1990年引入的CW张量族成为分析的核心对象。

1.2 激光方法的原理

激光方法的核心思想可以通过以下步骤理解。考虑一个张量$T$，其变量集被划分为$X = X_1 \cup \cdots \cup X_{k_X}$，$Y = Y_1 \cup \cdots \cup Y_{k_Y}$，$Z = Z_1 \cup \cdots \cup Z_{k_Z}$。对于每个三元组$(i,j,k)$，定义子张量：

$$T_{ijk} = \sum_{x \in X_i} \sum_{y \in Y_j} \sum_{z \in Z_k} a_{xyz} \cdot xyz$$

假设每个$T_{ijk}$要么为0，要么是矩阵乘法张量。虽然$T$是这些矩阵乘法张量的和，但通常不是直和。激光方法通过以下巧妙方式解决这个问题：

首先，在非零子张量上选择概率分布$\alpha$，对$T_{ijk}$赋予概率$\alpha_{ijk}$。然后考虑大的Kronecker幂：

$$T^{\otimes n} = \sum_{(T_1,\ldots,T_n) \in \{T_{ijk}\}^n} T_1 \otimes \cdots \otimes T_n$$

目标是零化$T^{\otimes n}$中的变量，使得剩余的是$B$个不同子张量$T_1 \otimes T_2 \otimes \cdots \otimes T_n$的直和，这些子张量与$\alpha$一致，即对每个$(i,j,k)$，有$|\{\ell \in [n] : T_\ell = T_{ijk}\}| = \alpha_{ijk} \cdot n$。

第二章：张量理论基础

2.1 张量运算的形式化定义

设$\mathbb{F}$为任意域，定义张量$T$在变量集$X = \{x_1, \ldots, x_{|X|}\}$，$Y = \{y_1, \ldots, y_{|Y|}\}$，$Z = \{z_1, \ldots, z_{|Z|}\}$上为三线性形式：

$$T = \sum_{i=1}^{|X|} \sum_{j=1}^{|Y|} \sum_{k=1}^{|Z|} a_{ijk} \cdot x_i y_j z_k$$

两个张量的直和$T \oplus T'$定义在不相交并$X \sqcup X'$，$Y \sqcup Y'$，$Z \sqcup Z'$上。Kronecker积$T \otimes T'$定义在笛卡尔积$X \times X'$，$Y \times Y'$，$Z \times Z'$上：

$$T \otimes T' = \sum_{i,j,k,i',j',k'} a_{ijk}b_{i'j'k'} \cdot (x_i, x'_{i'})(y_j, y'_{j'})(z_k, z'_{k'})$$

2.2 矩阵乘法张量

$a \times b \times c$矩阵乘法张量$\langle a,b,c \rangle$定义为：

$$\langle a,b,c \rangle = \sum_{i \in [a]} \sum_{j \in [b]} \sum_{k \in [c]} x_{ij}y_{jk}z_{ki}$$

这个张量编码了$a \times b$矩阵与$b \times c$矩阵相乘的三线性形式。关键性质包括：

$$\langle a,b,c \rangle \otimes \langle d,e,f \rangle \equiv \langle ad,be,cf \rangle$$

这对应于分块矩阵乘法的事实。

2.3 Schönhage渐近和不等式

Schönhage在1981年证明的一个关键结果表明，不仅单个矩阵乘法张量的秩可以给出$\omega$的界限，多个矩阵乘法张量的直和也可以：

定理 2.1 (Schönhage, 1981) 假设存在正整数$r > m$和$a_i, b_i, c_i$（$i \in [m]$），使得张量

$$T = \bigoplus_{i=1}^m \langle a_i, b_i, c_i \rangle$$

满足$\tilde{R}(T) \leq r$。则$\omega \leq 3\tau$，其中$\tau \in [2/3, 1]$是方程

$$\sum_{i=1}^m (a_i \cdot b_i \cdot c_i)^\tau = r$$

的解。

第三章：Coppersmith-Winograd张量族

3.1 CW张量的定义与结构

对于非负整数$q$，Coppersmith-Winograd张量$CW_q$定义在变量集$\{x_0, \ldots, x_{q+1}\}$，$\{y_0, \ldots, y_{q+1}\}$，$\{z_0, \ldots, z_{q+1}\}$上：

$$CW_q = x_0y_0z_{q+1} + x_0z_{q+1}y_0 + x_{q+1}y_0z_0 + \sum_{i=1}^q (x_0y_iz_i + x_iy_0z_i + x_iy_iz_0)$$

这个张量可以分解为：

• 三个"角项"：$x_0y_0z_{q+1}$，$x_0z_{q+1}y_0$，$x_{q+1}y_0z_0$
• 三个矩阵乘法张量：$\sum_{i=1}^q x_0y_iz_i \equiv \langle 1,1,q \rangle$，$\sum_{i=1}^q x_iy_0z_i \equiv \langle q,1,1 \rangle$，$\sum_{i=1}^q x_iy_iz_0 \equiv \langle 1,q,1 \rangle$

3.2 CW张量的自然划分

$CW_q$具有自然的变量划分：

• $X^0 = \{x_0\}$，$X^1 = \{x_1, \ldots, x_q\}$，$X^2 = \{x_{q+1}\}$
• $Y^0 = \{y_0\}$，$Y^1 = \{y_1, \ldots, y_q\}$，$Y^2 = \{y_{q+1}\}$
• $Z^0 = \{z_0\}$，$Z^1 = \{z_1, \ldots, z_q\}$，$Z^2 = \{z_{q+1}\}$

非零子张量恰好是满足$i+j+k=2$的$T_{ijk}$，使得$CW_q$成为2-划分张量。

第四章：改进的激光方法

4.1 主要定理

本文的核心贡献是以下改进的激光方法定理：

定理 4.1（改进的激光方法） 对于任何$P$-划分张量$T$，任何$\alpha \in D$，以及任何$\tau \in [2/3, 1]$，有：

$$V_\tau(T) \geq \alpha_{V_\tau} \cdot \alpha_B \cdot \sqrt{\frac{\alpha_N}{\max_{\beta \in D_\alpha} \beta_N}}$$

其中：

• $\alpha_B = \left(\prod_{i \in [k_X]} \alpha_{X_i}^{-\alpha_{X_i}}\right)^{1/3} \left(\prod_{j \in [k_Y]} \alpha_{Y_j}^{-\alpha_{Y_j}}\right)^{1/3} \left(\prod_{k \in [k_Z]} \alpha_{Z_k}^{-\alpha_{Z_k}}\right)^{1/3}$
• $\alpha_N = \prod_{(i,j,k) \in S} \alpha_{ijk}^{-\alpha_{ijk}}$
• $\alpha_{V_\tau} = \prod_{(i,j,k) \in S} V_\tau(T_{ijk})^{\alpha_{ijk}}$
• $D_\alpha$是与$\alpha$具有相同边缘分布的概率分布集合

与之前的界限$V_\tau(T) \geq \alpha_{V_\tau} \cdot \alpha_B \cdot \frac{\alpha_N}{\max_{\beta \in D_\alpha} \beta_N}$相比，新方法通过因子$\sqrt{\frac{\max_{\beta \in D_\alpha} \beta_N}{\alpha_N}}$实现了改进。

4.2 证明策略

证明分为四个主要步骤。考虑大的正整数$n$和张量$\mathcal{T} = T^{\otimes n} \otimes T^{r \otimes n} \otimes T^{rr \otimes n}$。目标是证明$\mathcal{T}$可以被零化为

$$\frac{\alpha_B^{3n-o(n)} \cdot \alpha_N^{1.5n-o(n)}}{\max_{\beta \in D_\alpha} \beta_N^{1.5n-o(n)}}$$

个不同张量的直和，每个具有值$\alpha_V^{3n}$。

步骤1：移除与$\alpha$不一致的块

定义$X_I$对$I \in [k_X]^n$与$\alpha$一致，如果对所有$i \in [k_X]$：

$$\alpha_{X_i} = \frac{1}{n} \cdot |\{\ell \in [n] : I_\ell = i\}|$$

零化所有至少有一个分量与$\alpha$不一致的$X$-块、$Y$-块或$Z$-块。剩余块的数量为：

$$N_B = \left(\prod_{i \in [k_X]} \alpha_{X_i}^{-\alpha_{X_i}}\right)^{n-o(n)} \cdot \left(\prod_{j \in [k_Y]} \alpha_{Y_j}^{-\alpha_{Y_j}}\right)^{n-o(n)} \cdot \left(\prod_{k \in [k_Z]} \alpha_{Z_k}^{-\alpha_{Z_k}}\right)^{n-o(n)} = \alpha_B^{3n-o(n)}$$

步骤2：计数非零块三元组

与$(\beta, \beta', \beta'')$一致的非零块三元组数量为：

$$(\beta_N \cdot \beta'_N \cdot \beta''_N)^{n-o(n)}$$

特别地，与$(\alpha, \alpha, \alpha)$一致的块三元组数量为$N_\alpha = \alpha_N^{3n-o(n)}$。

步骤3：使用Salem-Spencer集合稀疏化

定义哈希函数$h_X, h_Y, h_Z$到$\mathbb{Z}_M$，其中$M \in [100R, 200R]$是素数，$R = N_\alpha/N_B$。使用Salem-Spencer集合$A \subseteq \mathbb{Z}_M$，满足$|A| \geq M^{1-o(1)}$，零化所有不哈希到$A$中值的块。

步骤4：应用对角化定理

应用定理3.1将剩余张量转化为至少

$$L \geq \frac{2}{3\sqrt{3}} \cdot \frac{C_1'^{3/2}}{C_3^{1/2}} \geq \frac{\alpha_B^{3n-o(n)} \cdot \alpha_N^{1.5n-o(n)}}{\max_{\beta \in D_\alpha} \beta_N^{1.5n-o(n)}}$$

个与$(\alpha, \alpha, \alpha)$一致的块三元组的直和。

第五章：优化算法与启发式方法

5.1 固定$\gamma$时的优化

对于固定的$\gamma \in D$，优化所有$\alpha \in D_\gamma$上的界限可以通过求解两个凸规划问题完成：

问题1： 最大化 $\alpha_{V_\tau} \cdot \alpha_B \cdot \sqrt{\alpha_N}$，约束条件：$\alpha \in D_\gamma$

问题2： 最大化 $\beta_N$，约束条件：$\beta \in D_\gamma$

这两个问题都是在线性约束下最大化凹函数，可以高效求解。

5.2 选择$\gamma$的启发式方法

论文提出了四种启发式方法：

启发式1： 选择$\gamma$最大化$\gamma_{V_\tau} \cdot \gamma_B$，满足$\gamma = \arg\max_{\gamma' \in D_\gamma} \gamma_N$

启发式2： 选择$\gamma$最大化$\gamma_{V_\tau} \cdot \gamma_B$

启发式3： 选择$\gamma$最大化$\gamma_{V_\tau} \cdot \gamma_B + \lambda/\gamma_N$，其中$\lambda$是可调参数

启发式4： 选择$\gamma$最大化$\gamma_{V_\tau} \cdot \gamma_B \cdot \sqrt{\gamma_N}$

实验表明，启发式3在$\lambda$取0到$10^7$之间的正值时通常给出最好的结果。

第六章：数值结果

6.1 对$CW_q^{\otimes t}$的分析

对于$t$次幂的CW张量，定义映射$\kappa: \{0,1,\ldots,q+1\} \to \{0,1,2\}$：

• $\kappa(0) = 0$
• $\kappa(i) = 1$ 对于 $i \in \{1,\ldots,q\}$
• $\kappa(q+1) = 2$

对于$I \in \{0,1,\ldots,2t\}$，定义：

$$L_{t,I} = \{A \in \{0,1,\ldots,q+1\}^t : \sum_{\ell=1}^t \kappa(A_\ell) = I\}$$

6.2 子张量的合并现象

某些子张量可以通过"合并"获得更大的值。例如，$T^2_{220}$可以合并为：

$$T^2_{220} \equiv \sum_{i=0}^{q+1} x_{i,i}y_{i,i}z_{0,0} \equiv \langle q+2, 1, 1 \rangle$$

因此$V_\tau(T^2_{220}) = (q+2)^\tau$，这比单独处理各部分得到的值更大。

6.3 最终界限

应用改进的激光方法到$CW_5^{\otimes 32}$，对于$\tau = 2.3728596/3$，得到：

$$V_\tau(CW_5^{\otimes 32}) > 7^{32 + 9.19 \times 10^{22}}$$

结合Schönhage不等式和$\tilde{R}(CW_5) = 7$的事实，这给出：

$$\omega < 2.3728596$$

附录A：概率分析的技术细节

A.1 边缘分布的保持

引理 A.1 对于任何$\alpha \in D$和足够大的正整数$n$，存在$\alpha' \in D$使得：

• $\alpha'_{ijk}$是$1/n$的整数倍
• $|\alpha_{ijk} - \alpha'_{ijk}| < 1/n$

证明： 设$S' \subseteq S$为$\alpha_{ijk}$不是$1/n$整数倍的$(i,j,k)$集合。对每个$(i,j,k) \in S \setminus S'$，令$\alpha'_{ijk} = \alpha_{ijk}$。初始时，对每个$(i,j,k) \in S'$，令$\alpha'_{ijk} = \lfloor n \cdot \alpha_{ijk} \rfloor/n$。

因为$\sum_{(i,j,k) \in S} \alpha_{ijk} = 1$，设$t = \sum_{(i,j,k) \in S} \alpha'_{ijk}$。则：

$$1 - t = \sum_{(i,j,k) \in S'} (\alpha_{ijk} - \alpha'_{ijk}) \leq \frac{|S'|}{n}$$

存在非负整数$K \leq |S'|$使得$t = 1 - K/n$。选择$S'$中任意$K$个元素$(i,j,k)$，对其$\alpha'_{ijk}$加上$1/n$。现在$\sum \alpha'_{ijk} = 1$，因此$\alpha' \in D$。

A.2 舍入误差的影响

引理 A.2 设$\alpha, \alpha'$如上。则：

$$\frac{1}{2^{o(n)}} \leq \frac{\alpha_N}{\alpha'_N} \leq 2^{o(n)}$$

证明： 因为$\alpha_N = \prod_{(i,j,k) \in S} \alpha_{ijk}^{-\alpha_{ijk}}$，我们有：

$$\frac{\alpha_N}{\alpha'_N} = \prod_{(i,j,k) \in S} \left(\frac{\alpha_{ijk}}{\alpha'_{ijk}}\right)^{-\alpha_{ijk}} \cdot \left(\alpha'_{ijk}\right)^{\alpha'_{ijk} - \alpha_{ijk}}$$

对于固定的$(i,j,k) \in S$，如果$\alpha_{ijk}$是$1/n$的整数倍，则$\alpha'_{ijk} = \alpha_{ijk}$，比值为1。

否则，设$\delta = \alpha'_{ijk} - \alpha_{ijk}$，其中$0 < |\delta| < 1/n$。当$\delta > 0$时：

$$\log\left(\frac{\alpha_{ijk}^{-\alpha_{ijk}}}{\alpha_{ijk}'^{-\alpha'_{ijk}}}\right) = (\alpha_{ijk} + \delta)\log(\alpha_{ijk} + \delta) - \alpha_{ijk}\log\alpha_{ijk}$$

使用$\log(1+x) = x - O(x^2)$当$x \to 0^+$：

$$= \alpha_{ijk}\log\left(1 + \frac{\delta}{\alpha_{ijk}}\right) + \delta\log(\alpha_{ijk} + \delta) \leq O\left(\frac{1}{n}\right)$$

因此比值在$2^{-o(n)}$和$2^{o(n)}$之间。

附录B：对角化定理的最优性

B.1 下界构造

定理 B.1 对于正整数$n \geq m$且$n$足够大，存在集合$S \subseteq \{(i,j,k) \in [n]^3 : i,j,k \text{互不相同}\}$，$|S| = mn$，使得对任何大小$|I| = n\sqrt{\log n}/m$的子集$I \subseteq [n]$，存在$(i,j,k) \in S$满足$i,j,k \in I$。

证明： 令$\mathcal{C}$为所有大小为$n\sqrt{\log n}/m$的$[n]$子集的集合。因此：

$$|\mathcal{C}| = \binom{n}{n\sqrt{\log n}/m} \leq n^{n\sqrt{\log n}/m}$$

初始令$S = \emptyset$。重复添加元素$(i,j,k)$到$S$，并移除所有包含$i,j,k$的剩余$I \in \mathcal{C}$，直到$\mathcal{C}$变空。

在每步，贪心选择最大化$|\{I \in \mathcal{C} : i,j,k \in I\}|$的互不相同的$(i,j,k) \in [n]^3$。对于随机选择的三个互不相同的$i,j,k \in [n]$，给定$I \in \mathcal{C}$，$i,j,k \in I$的概率为：

$$\frac{|I|}{n} \cdot \frac{|I|-1}{n-1} \cdot \frac{|I|-2}{n-2} > \left(\frac{|I|-2}{n-2}\right)^3 > \frac{1}{2}\left(\frac{\log n}{\sqrt{m}}\right)^3$$

重复$mn$次后，$|\mathcal{C}|$的大小将小于：

$$n^{n/\sqrt{m}} \cdot \left(1 - \frac{1}{2}\left(\frac{\log n}{\sqrt{m}}\right)^3\right)^{mn} < n^{n/\sqrt{m}} \cdot e^{-\frac{1}{2}n\log^3 n/\sqrt{m}} < 1$$

对于足够大的$n$。因此$|\mathcal{C}| = 0$。

B.2 自由张量的构造

定理 B.2 对于正整数$n$和$m$，其中$n$足够大且$\log^2 n \leq m \leq \sqrt{n/6}$，存在集合$S \subseteq \binom{[n]}{3}$，$|S| \leq O(mn)$，使得：

1. 任意不同的$\{i,j,k\}, \{i',j',k'\} \in S$满足$|\{i,j,k\} \cap \{i',j',k'\}| \leq 1$
2. 对任何大小$|I| = n\log(n)/\sqrt{m}$的子集$I \subseteq [n]$，存在$\{i,j,k\} \in S$满足$i,j,k \in I$

这个构造证明了即使对于具有额外结构（自由性）的张量，$\sqrt{m}$因子仍然是最优的。

附录C：Salem-Spencer集合的张量解释

C.1 构造与性质

对于奇素数$M$，定义张量$C_M$：

$$C_M = \sum_{i=0}^{M-1} \sum_{j=0}^{M-1} x_i \cdot y_j \cdot z_{(i+j)/2 \bmod M}$$

使用Salem-Spencer集合$A$，零化所有$i \notin A$的$x_i, y_i, z_i$，得到：

$$\sum_{i \in A} x_i \cdot y_i \cdot z_i$$

这是$|A| \geq M \cdot e^{-O(\sqrt{\log M})}$项的直和。

C.2 在激光方法中的应用

在步骤3中，定义的哈希函数满足关键性质：

• $h_X(I, J', K'') + h_Y(J, K', I'') = 2h_Z(K, I', J'') \pmod{M}$
• 三个哈希值在条件于其他两个之一时仍是均匀随机的
• 哈希函数是成对独立的

这些性质确保了Salem-Spencer集合可以有效地用于稀疏化，同时保持足够多的与$(\alpha, \alpha, \alpha)$一致的块三元组。

结论

本文通过引入$\sqrt{m}$改进因子，成功地改进了激光方法并获得了矩阵乘法指数的新界限$\omega < 2.3728596$。虽然改进幅度看似微小，但这代表了该领域核心技术的一次重要突破。更重要的是，这种改进的激光方法是通用的，可能在算术复杂性的其他问题中有进一步应用。

已知的局限性结果表明，仅使用激光方法和Coppersmith-Winograd张量族无法证明$\omega = 2$。要实现矩阵乘法复杂度的重大突破，可能需要全新的方法或张量族。尽管如此，本文的工作为未来研究提供了新的技术工具，并展示了即使在高度优化的算法中仍有改进空间。