斯特拉森的矩阵乘法算法

有人可以用直观的方式解释斯特拉森的矩阵乘法算法吗？我经历了（好，试图通过）书和wiki中的解释，但它不是点击楼上的。任何使用大量英语而非正式表示法的网络链接也会有所帮助。是否有任何类比可以帮助我从头开始构建这个算法，而不必记住它？斯特拉森的矩阵乘法算法

来源

2009-12-17 confused_by_strassen

您在理解第一部分（零填充后跟分区）还是下一步（减少操作数）方面有困难？ – 2009-12-17 08:01:50

看看这篇文章试图[教学解释]（http://www.cs.utep.edu/vladik/2000/tr00-41.pdf）。 – 2012-12-21 22:41:40

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

下面是一个比喻。 x*x + 5*x + 6有多少乘法运算？两个，对吗？ (x+2)(x+3)有多少乘法运算？一个，对吗？但他们是一样的表达！

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

来源

2009-12-17 07:58:21

在我看来有三种想法，你需要得到：

您可以将矩阵分割成块，就像你会在数字矩阵上得到的这些砌块的矩阵操作。特别是，你可以乘两个这样的块矩阵（当然只要一个块的行数与另一个块的列数相匹配），并得到与乘以原始数字矩阵时相同的结果。
表达2×2块矩阵乘法结果所需的块有足够的公因子来允许以比原始公式暗示的更少的乘法计算它们。这是Tony's answer中描述的技巧。
递归。

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

来源

2009-12-17 09:30:06

多好的答案。 – 2009-12-18 06:03:26

考虑乘以2×2矩阵，如下：

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

计算右侧明显的方法就是做乘法8和4个补充。但是，想象乘法比加法要昂贵得多，所以我们希望尽可能减少乘法的次数。斯特拉森用一个小技巧来计算右边的乘法，减少乘法和更多的加法（以及一些减法）。

这里有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而言），那么加/减其他一些女士，直到我们只剩下AE + BG了。奇迹般地，M的选择是为了让M1 + M7-M2 + M5起作用。与其他3个结果相同。

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

来源

2009-12-17 18:01:54

只为完成 AE + BG = M1 + M7-M2 + M5, AF + BH = M2 + M4, CE + DG = M3 + M5, CF + DH = M1 + M6-M3 + M4 – 2013-11-17 16:47:18

斯特拉森的矩阵乘法算法

回答

相关问题