问题描述
有人可以解释以直观的方式施特拉森的算法，矩阵乘法？我已经通过了（当然，试图去通过）在书中和维基解释，但它不是一下楼上。使用了很多英语，而不是正式符号等在网络上的任何链接将是有益的，太。是否有任何类比可能有助于我从头开始构建这个算法，而无需记住它？
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?
推荐答案
考虑乘以2×2矩阵，如下：
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而言），那么加/减其他一些女士，直到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.
现在才意识到这部作品不仅是2×2矩阵，但对于任何（甚至）大小的矩阵，其中A..H的子矩阵。
Now just realize this works not just for 2x2 matrices, but for any (even) sized matrices where the A..H are submatrices.
这篇关于施特拉森的矩阵乘算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！