algorithm - Strassen 的矩阵乘法算法

Question

有人可以以直观的方式解释施特拉森的矩阵乘法算法吗？我已经通过（好吧，试图通过）书和维基中的解释，但它没有点击楼上。网络上使用大量英语而不是正式符号等的任何链接也会有所帮助。有没有什么类比可以帮助我从头开始构建这个算法而不必记住它？

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 块矩阵乘法结果所需的块具有足够的公因数，可以用比原始公式所暗示的更少的乘法来计算它们。这是托尼的回答中描述的技巧。

3. 递归。

Strassen算法只是上述的一个应用。要了解其复杂性的分析，您需要阅读 Ronald Graham、Donald Knuth 和 Oren Patashnik 的《具体数学》或类似的书。

Answer 3

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

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

请注意，我不希望这能提供对算法的深入理解，只是一种直观的方式，您可以通过这种方式了解算法如何可能导致计算复杂度的提高。