矩阵Strassen 算法

ops/2025/1/16 0:08:46/

Strassen 算法
不要与多项式乘法的 Schönhage-Strassen 算法混淆。
在线性代数中，以 Volker Strassen 命名的 Strassen 算法是一种矩阵乘法算法。对于大型矩阵，它比标准矩阵乘法算法更快，具有更好的渐近复杂度，尽管朴素算法通常更适合较小的矩阵。对于极大矩阵，Strassen 算法比已知最快的算法慢，但这种银河算法在实践中没有用，因为它们对于实际大小的矩阵要慢得多。对于小矩阵，存在更快的算法。
Strassen 算法适用于任何环，例如加/乘，但不适用于所有半环，例如最小加或布尔代数，其中朴素算法仍然有效，以及所谓的组合矩阵乘法。
历史
Volker Strassen 在 1969 年首次发布了这个算法，从而证明了n3通用矩阵乘法算法不是最佳的。Strassen 算法的发布导致了对矩阵乘法的更多研究，这导致了渐近下界和改进的计算上限。

算法
在这里插入图片描述

让AB是环上的两个方形矩阵R，例如，其项为整数或实数的矩阵。矩阵乘法的目标是计算矩阵乘积C=AB。以下算法说明假定所有这些矩阵的大小都是 2 的幂
在这里插入图片描述

但这只是概念上必要的 — 如果矩阵A,B不是类型2nX2n，“缺失的”行和列可以用零填充以获得大小为 2 的幂的矩阵 — 尽管该算法的实际实现在实践中不会这样做。
Strassen 算法分区A,B和C转换为大小相等的块矩阵
在这里插入图片描述

跟在这里插入图片描述
。朴素的算法为：

这种构造不会减少乘法的次数：仍然需要 8 次矩阵块的乘法来计算Cij矩阵，则使用标准矩阵乘法时所需的乘法次数相同。
Strassen 算法定义了新值：
在这里插入图片描述

仅使用 7 次乘法（每次 1 次Mk）而不是 8。我们现在可以将Cij在Mk：
在这里插入图片描述

我们递归迭代这个除法过程，直到子矩阵退化为数字（环的元素R). 如上所述，如果原始矩阵的大小不是 2 的幂，则生成的乘积将具有零行和零列，就像A和B，然后这些将在此时被剥离以获得（更小的）矩阵C我们真的很想要。
Strassen 算法的实际实现对于足够小的子矩阵切换到标准的矩阵乘法方法，这些算法的效率更高。Strassen 算法更有效的特定交叉点取决于特定的实现和硬件。早期的作者估计，Strassen 算法对于宽度为 32 到 128 的矩阵，可以优化实现。然而，据观察，这个交叉点近年来一直在增加，2010 年的一项研究发现，与高度优化的传统乘法相比，即使是 Strassen 算法的单个步骤在当前架构上通常也没有好处，直到矩阵大小超过 1000 或更多，即使对于几千个矩阵大小，好处通常充其量也是微不足道的（大约 10% 或更少）。最近的一项研究（2016 年）观察到，小至 512 的矩阵有好处，好处约为 20%。