Strassen 矩阵乘法算法
有人能以直观的方式解释斯特拉森的矩阵乘法算法吗？我已经阅读了（好吧，试图阅读）书中和维基中的解释，但它没有点击楼上。网络上任何使用大量英语而不是正式符号等的链接也会有所帮助。是否有任何类比可以帮助我从头开始构建这个算法而无需记住它？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
考虑将两个 2x2 矩阵相乘，如下所示：
计算右侧的明显方法就是进行 8 次乘法和 4 次加法。但想象乘法比加法昂贵得多，因此我们希望尽可能减少乘法的次数。施特拉森使用一种技巧来计算右侧，减少一次乘法，增加大量加法（以及一些减法）。
以下是 7 次乘法：
因此，要计算 AE+BG，请从 M1+M7（这为我们提供 AE 和 BG 项）开始，然后添加/减去其他一些 Ms，直到剩下 AE+BG。奇迹般的是，M 的选择使得 M1+M7-M2+M5 起作用。与所需的其他 3 个结果相同。
现在要意识到这不仅适用于 2x2 矩阵，而且适用于 A..H 是子矩阵的任何（偶数）大小的矩阵。
Consider multiplying two 2x2 matrices, as follows:
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).
Here are the 7 multiplies:
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.
Now just realize this works not just for 2x2 matrices, but for any (even) sized matrices where the A..H are submatrices.
在我看来，您需要了解 3 个想法：
您可以将矩阵拆分为多个块，然后像对数字矩阵一样对生成的块矩阵进行操作。特别是，您可以将两个这样的块矩阵相乘（当然，只要一个矩阵中的块行数与另一个中的块列数相匹配），并得到与原始数字矩阵相乘时相同的结果。
表达 2x2 块矩阵乘法结果所需的块具有足够的公因数，可以用比原始公式所暗示的更少的乘法来计算它们。这是托尼的回答中描述的技巧。
递归。
Strassen算法只是上述算法的一个应用。要理解其复杂性的分析，你需要阅读 Ronald Graham 的《具体数学》， Donald Knuth 和 Oren Patashnik 或类似的书。
In my opinion there are 3 ideas that you need to get:
You can split a matrix into blocks and operate on the resulting matrix of blocks like you would on a matrix of numbers. In particular you can multiply two such block matrices (of course as long as the number of block rows in one matches the number of block columns in the other) and get the same result as you would when multiplying original matrices of numbers.
The blocks necessary to express the result of 2x2 block matrix multiplication have enough common factors to allow computing them in fewer multiplications than the original formula implies. This is the trick described in Tony's answer.
Recursion.
Strassen algorithm is just an application of the above. To understand the analysis of its complexity, you need to read "Concrete Mathematics" by Ronald Graham, Donald Knuth, and Oren Patashnik or a similar book.
快速浏览了一下维基百科，在我看来，该算法稍微减少了重新排列方程所需的乘法次数。
这是一个类比。
x*x + 5*x + 6有多少次乘法？两个，对吧？(x+2)(x+3)中有多少次乘法？一，对吗？但他们的表情是一样的！请注意，我并不期望这能提供对算法的深入理解，只是一种直观的方式，让您可以了解算法如何可能导致计算复杂性的提高。
Took a quick look at the Wikipedia and it appears to me that this algorithm is a slight reduction in the number of multiplications required by rearranging the equations.
Here's an analogy. How many multiplications in
x*x + 5*x + 6? Two, right? How many multiplications in(x+2)(x+3)? One, right? But they're the same expression!Note, I do not expect this to provide a deep understanding of the algorithm, just an intuitive way in which you can understand how the algorithm can possibly lead to an improvement in calculation complexity.