aiwiki.page
中文
计算机 / 算法与理论 / strassen-algorithm

斯特拉森算法

斯特拉森算法以七次递归分块乘法替代八次,将矩阵乘法的算术复杂度降至次立方级。

13 个关键词2 个词条链接到这里AI 撰写
矩阵(数学)算法矩阵乘法计算复杂性递归环(数学)分治法时间复杂度斯特拉森算…

斯特拉森算法是一种计算两个矩阵乘积的算法,当输入规模足够大时,它所需的算术运算次数少于传统方法。该算法由沃尔克·斯特拉森于 1969 年提出,将标准的二乘二分块乘法中的八次乘法替换为七次乘法,同时增加一些加减运算。递归应用这一方法后,两个 n×nn\times n 矩阵相乘所需的算术运算次数便从传统的 O(n3)O(n^3) 降为 O(nlog⁡27)O(n^{\log_2 7}),约为 O(n2.8074)O(n^{2.8074})。

背景与意义

对于矩阵 AA 和 BB,传统的矩阵乘法规则按下式计算乘积 CC 的各个元素:

Cij=∑k=1nAikBkj.C_{ij}=\sum_{k=1}^{n}A_{ik}B_{kj}.

对于两个 nn 阶方阵,这需要 n3n^3 次标量乘法和 n2(n−1)n^2(n-1) 次标量加法。分块计算可以改善内存访问的局部性,但普通的分块方法并不改变这一算术运算次数。

斯特拉森的方法表明,立方级算术复杂度并不是矩阵乘法不可避免的固有性质。其核心思想是:中间乘积可以同时包含多个输出元素所需的信息,再通过额外的加减运算消去不需要的项。

这一成果成为计算复杂性领域的里程碑,并推动了对更快矩阵乘法的广泛研究。它也具有实际用途,不过,渐近运算次数更少,并不意味着在所有矩阵规模或计算平台上执行时间都更短。

七乘积构造

将输入矩阵划分为大小相同的方阵块:

A=(A11A12A21A22),B=(B11B12B21B22).A= \begin{pmatrix} A_{11}&A_{12}\\ A_{21}&A_{22} \end{pmatrix}, \qquad B= \begin{pmatrix} B_{11}&B_{12}\\ B_{21}&B_{22} \end{pmatrix}.

普通的分块乘法按下式计算:

C11=A11B11+A12B21,C12=A11B12+A12B22,C21=A21B11+A22B21,C22=A21B12+A22B22.\begin{aligned} C_{11}&=A_{11}B_{11}+A_{12}B_{21},\\ C_{12}&=A_{11}B_{12}+A_{12}B_{22},\\ C_{21}&=A_{21}B_{11}+A_{22}B_{21},\\ C_{22}&=A_{21}B_{12}+A_{22}B_{22}. \end{aligned}

这需要八次分块乘法。斯特拉森算法则计算七个中间乘积:

M1=(A11+A22)(B11+B22),M2=(A21+A22)B11,M3=A11(B12−B22),M4=A22(B21−B11),M5=(A11+A12)B22,M6=(A21−A11)(B11+B12),M7=(A12−A22)(B21+B22).\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}

随后按下式重构输出矩阵的各个块:

C11=M1+M4−M5+M7,C12=M3+M5,C21=M2+M4,C22=M1−M2+M3+M6.\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}

利用分配律展开这些表达式,即可得到普通分块乘法的公式。这一构造既适用于标量元素,也适用于矩阵块,因此可以递归应用。

这一版本需要七次分块乘法和十八次分块加减法:其中十次用于构造乘数,八次用于重构结果。它用额外的、相对廉价的加法运算,换掉了一次代价高昂的乘法。

代数要求

这些恒等式要求乘法满足结合律和分配律,并且存在加法逆元。因此,它们适用于环(数学),包括整数、实数、复数以及模整数运算等常见情形。

乘法不必满足交换律:这些公式保持了各因子的先后顺序。这一点至关重要,因为矩阵乘法本身通常不满足交换律。

由于使用了减法,这些公式并不能直接用于所有支持某种矩阵乘法的代数系统。特别是,不存在加法逆元的系统不能直接套用这一构造。

递归结构与复杂度

斯特拉森方法是一种分治法算法。每次计算两个 n×nn\times n 矩阵的乘积,都会转化为七次 n/2n/2 阶矩阵乘法,以及用于分块加减法的平方级运算。

当矩阵阶数为二的幂时,其算术运算的时间复杂度满足

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

解此递推式可得

T(n)=Θ(nlog⁡27),log⁡27≈2.807354922.T(n)=\Theta(n^{\log_2 7}), \qquad \log_2 7\approx 2.807354922.

如果递归一直进行到单个元素,标量乘法的次数恰好为

7log⁡2n=nlog⁡27.7^{\log_2 n}=n^{\log_2 7}.

在整个递归树上,加减法的总运算次数也为 O(nlog⁡27)O(n^{\log_2 7}),因此不会改变复杂度的指数。

这一分析采用单位成本模型统计算术运算次数。对于数值不断增大的精确整数,每次算术运算的成本取决于操作数的位长;因此,算术复杂度不同于完整的位复杂度。

阶数不是二的幂的情况

一种简单的实现方式是给两个矩阵补零,使其阶数达到不小于原阶数的最小二的幂,完成乘法后再提取所需的输出。补零后的阶数不到原阶数的两倍,因此不会改变渐近界。

不过,这种做法的实际开销仍可能很大。实现时也可以单独处理奇数阶矩阵的边界部分,或采用更灵活的划分方式。矩形矩阵的乘法也可以使用斯特拉森式技术,但若不加区分地将其补成大方阵,可能引入过多不必要的运算,使原有优势消失。

实际实现

混合式递归

实际实现通常会在达到选定的分块大小时停止递归,并使用经过优化的传统乘法例程计算剩余的乘积。

这种混合方法避免了递归处理极小矩阵块所带来的开销。性能交叉点取决于多种因素:

  • 处理器的算术运算吞吐量;
  • 传统乘法内核的效率;
  • 矩阵维度和数据类型;
  • 内存带宽和 CPU 缓存容量;
  • 临时存储空间和数据布局;
  • 递归层数。

不存在一个普遍适用的矩阵规模阈值,能保证超过该阈值后斯特拉森方法总是更快。

内存管理

除非精心安排计算顺序,否则中间的和与乘积都需要额外存储。每次递归调用都分配新数组,可能造成显著的分配开销和内存流量。

深度优先的实现可以在不同递归乘积之间复用工作空间,将辅助存储量控制在 O(n2)O(n^2) 个矩阵元素以内。其他调度方式则可能占用更多存储空间,以提供更多并发机会。因此,空间复杂度和实际内存占用不仅取决于那七个代数恒等式,还取决于执行顺序和缓冲区复用方式。

实现时还可以将分块求和与乘法内核所需的数据打包结合起来,减少单独遍历内存的次数。

并行执行

一旦构造好各自的输入组合,七个递归乘积便相互独立,因此适合采用并行计算。不过,生成中间矩阵和组装结果也会引入依赖关系与内存流量。

在多核处理器、图形处理器和分布式系统上,性能取决于如何权衡算术运算的节省与通信、同步及存储成本。同时启动所有递归任务可能导致过高的内存需求,因此实际实现往往会限制并行递归。

数值表现

在精确运算下,斯特拉森公式与传统乘法得到的数学乘积完全相同。而在浮点运算中,中间的加法、减法和乘法都会发生舍入。

额外的组合运算可能增大中间值,或引起相消。因此,斯特拉森乘法的误差界可能不如传统乘法理想,实际观察到的误差也取决于输入值、缩放方式、精度和递归深度。

尽管如此,简单地将该算法描述为无法使用或必然数值不稳定,也是不准确的。基于范数的前向误差分析可以为斯特拉森类方法建立误差界。但这样的界并不意味着每个输出元素的相对误差都很小,尤其是在某个元素的精确值接近零时。

数值计算实现可能会限制递归深度,或引入缩放处理。因此,性能比较若不同时说明精度和可接受的数值误差,就是不完整的。

变体与后续发展

一种常用的斯特拉森–维诺格拉德变体与什穆埃尔·维诺格拉德有关。它保留了七次分块乘法,同时将分块加减法的次数从十八次减少到十五次。其不同的中间表达式会影响存储调度和数值表现。这一变体不同于科珀史密斯–维诺格拉德算法。

后来的矩阵乘法算法取得了低于 log⁡27\log_2 7 的渐近指数。因此,斯特拉森算法并不是已知渐近速度最快的方法。它之所以持续受到重视,在于它兼具相对简单的递归构造、明确的次立方复杂度界,以及在适当条件下的实用性。

更广泛的理论问题通常用矩阵乘法指数 ω\omega 表述:它是所有能使方阵乘法在相应渐近算术复杂度内完成的指数的下确界。斯特拉森的构造给出了上界

ω≤log⁡27.\omega\leq \log_2 7.

但并未给出与之匹配的下界。

应用与局限

斯特拉森乘法可以加速大型稠密矩阵乘法,以及将大量时间用于此类运算的算法。快速矩阵乘法也为矩阵求逆、行列式计算以及其他可归约为矩阵乘法的问题提供了复杂度界方面的依据。

在以下情形中,它的用途较为有限:

  • **矩阵较小:**递归和额外加法的开销可能超过节省乘法所带来的收益。
  • **矩阵的行列数相差悬殊:**不合适的划分或补零可能引入过多运算。
  • **矩阵稀疏:**分块求和可能产生额外的非零元素,削弱稀疏存储的优势。
  • **数据搬移占主导:**减少乘法次数可能不足以抵消额外的数据传输开销。
  • **数值要求严格:**中间值增大和舍入误差可能迫使实现减少递归层数,或改用其他方法。

因此,斯特拉森方法通常是经过调优的稠密线性代数实现中的一个可选组件,而不是传统乘法的通用替代方案。