Strassen的矩阵乘法算法

Question

有人可以用直观的方式解释strassen的矩阵乘法算法吗？我已经完成了(好了,试图通过)书中的解释和维基,但它没有点击楼上.网络上使用大量英语而非正式表示法等的任何链接也会有所帮助.是否有任何类比可以帮助我从头开始构建这个算法而不必记住它？

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)？一个吧？但他们是同一个表达!

注意,我不希望这提供对算法的深入理解,只是一种直观的方式,您可以在其中理解算法如何可能导致计算复杂性的提高.