矩阵乘法的施特拉森算法 [英] Strassen's algorithm for matrix multiplication

问题描述

有人可以以一种直观的方式解释矩阵乘法的斯特拉森算法吗?我已经阅读了(好吧，试图阅读)书中和维基中的解释，但它并没有在楼上点击.网络上任何使用大量英语而不是正式符号等的链接也会有所帮助.有没有类比可以帮助我从头开始构建这个算法而不必记住它?

Can someone please explain strassen's algorithm for matrix multiplication in an intuitive way? I've gone through (well, tried to go through) the explanation in the book and wiki but it's not clicking upstairs. Any links on the web that use a lot of English rather than formal notation etc. would be helpful, too. Are there any analogies which might help me build this algorithm from scratch without having to memorize it?

推荐答案

考虑将两个 2x2 矩阵相乘，如下:

Consider multiplying two 2x2 matrices, as follows:

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

计算右侧的显而易见的方法就是进行 8 次乘法和 4 次加法.但是想象一下，乘法比加法要昂贵得多，所以我们希望尽可能减少乘法的次数.Strassen 使用一种技巧来计算右手边少一个乘法和更多的加法(和一些减法).

The obvious way to compute the right side is just to do the 8 multiplies and 4 additions. But imagine multiplies are a lot more expensive than additions, so we want to reduce the number of multiplications if at all possible. Strassen uses a trick to compute the right hand side with one less multiply and a lot more additions (and some subtractions).

这里是 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 个结果相同.

So to compute AE+BG, start with M1+M7 (which gets us the AE and BG terms), then add/subtract some of the other Ms until AE+BG is all we are left with. Miraculously, the M's are chosen so that M1+M7-M2+M5 works. Same with the other 3 results required.

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

Now just realize this works not just for 2x2 matrices, but for any (even) sized matrices where the A..H are submatrices.

这篇关于矩阵乘法的施特拉森算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！