Strassen矩阵乘法算法

Question

有人能用直观的方式解释一下strassen的矩阵乘法算法吗？我已经看过(好吧，试着看过)书和wiki中的解释，但它不能上楼。任何在网络上使用大量英语而不是正式符号的链接也会很有帮助。有没有什么类比可以帮助我从头开始构建这个算法，而不需要记住它？

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项)，然后加/减一些其他的Ms，直到我们只剩下AE+BG。神奇的是，M的选择使得M1+M7-M2+M5工作。与所需的其他3个结果相同。

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

Answer 2

在我看来，你需要有3个想法：

，

1. ，你可以把一个矩阵分成多个块，然后像对一个数字矩阵一样，对得到的块矩阵进行运算。特别是，您可以将两个这样的块矩阵相乘(当然，只要一个矩阵中的块行数与另一个矩阵中的块列数匹配)，就可以得到与将原始矩阵相乘时的结果相同的结果。
2. 表示2x2分块矩阵乘法的结果所需的块具有足够的公因子，使得计算它们的乘法次数少于原始公式所暗示的次数。这是Tony's answer.
3. Recursion.

中描述的技巧

Strassen算法就是上述算法的一个应用。要理解对其复杂性的分析，您需要阅读Ronald Graham，Donald Knuth和Oren Patashnik的"Concrete Mathematics“或类似的书籍。

Answer 3

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

这是一个类比。x*x + 5*x + 6中有多少乘法？两个，对吧？(x+2)(x+3)中有多少乘法？一个，对吧？但它们是相同的表情！

请注意，我并不期望这能提供对算法的深入理解，只是一种直观的方式，让您能够理解算法如何可能导致计算复杂性的提高。