斯特拉森矩阵乘法算法

Question

有人能以直观的方式解释Strassen矩阵乘法算法吗？我已经尝试过书本和维基百科上的解释，但还是不太理解。如果有一些使用大量英语而不是正式符号等的网络链接将会很有帮助。是否有任何比喻可以帮助我从头开始构建这个算法，而无需记忆它？

- confused_by_strassen

---

你是否在理解第一部分（填充零后分区）或下一步（减少操作次数）方面遇到了困难？ - Alok Singhal

看看这篇试图进行教学解释的论文。 - Axel Kemper

Answer 1

考虑两个2x2矩阵的乘法，如下所示：

A B * E F = AE+BG AF+BH
C D   G H   CE+DG CF+DH

计算右边的显而易见的方法就是进行8次乘法和4次加法。但是，假设乘法比加法要昂贵得多，因此如果可能的话，我们希望减少乘法的数量。Strassen使用了一个技巧来通过减少一次乘法、增加大量加法（和一些减法）来计算右侧。

这里是7个乘法：

M1 = (A + D) * (E + H) = AE + AH + DE + DH
M2 = (A + B) * H = AH + BH
M3 = (C + D) * E = CE + DE
M4 = A * (F - H) = AF - AH
M5 = D * (G - E) = DG - DE
M6 = (C - A) * (E + F) = CE + CF - AE - AF
M7 = (B - D) * (G + H) = BG + BH - DG - DH

要计算AE+BG，首先从M1+M7开始（这得到了AE和BG项），然后加上/减去一些其他的M，直到我们只剩下AE+BG为止。神奇的是，M被选择成M1+M7-M2+M5可以得出我们想要的结果。对于另外三个所需的结果也是一样。

现在只需要意识到这不仅适用于2x2矩阵，而且适用于任何（偶数）大小的矩阵，其中A..H是子矩阵。

- Keith Randall

---

仅为完成而言 AE+BG=M1+M7-M2+M5， AF+BH=M2+M4， CE+DG=M3+M5， CF+DH=M1+M6-M3+M4 - isuru chathuranga

Answer 2

在我看来，你需要掌握以下三个概念：

1. 你可以将矩阵分成块，并像处理数字矩阵一样操作得到的块矩阵。特别地，你可以相乘两个这样的块矩阵（当然只要一个的块行数等于另一个的块列数），并得到与原始数字矩阵相乘时相同的结果。

2. 为了表达2x2块矩阵乘法的结果所需的块具有足够的公共因子，可以使用比原始公式更少的乘法计算它们。这就是Tony's answer中描述的技巧。

3. 递归。

斯特拉森算法只是上述内容的应用。要理解其复杂性的分析，需要阅读Ronald Graham，Donald Knuth和Oren Patashnik的《Concrete Mathematics》或类似的书籍。

- Rafał Dowgird

Answer 3

我浏览了一下维基百科，这个算法似乎通过重新排列方程式来略微减少所需的乘法次数。

这里有一个类比。在 x*x + 5*x + 6 中有两个乘法，对吗？在 (x+2)(x+3) 中有一个乘法，对吗？但它们是相同的表达式！

请注意，我并不指望这能提供算法的深入理解，只是以一种直观的方式让您了解该算法如何可能导致计算复杂度的改进。

- Tony van der Peet