algorithm - 用于矩阵乘法的施特拉森算法

Question

谁能直观地解释一下 strassen 的矩阵乘法算法？我已经通过(好吧，试图通过)书和维基中的解释，但它没有点击楼上。 Web 上任何使用大量英语而不是正式符号等的链接也会有所帮助。是否有任何类比可以帮助我从头开始构建此算法而无需记住它？

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 起作用。与要求的其他 3 个结果相同。

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