在 SegmentFault，学习技能、解决问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。
问题对人有帮助，内容完整，我也想知道答案
问题没有实际价值，缺少关键内容，没有改进余地
矩阵乘法的strassen算法的7个矩阵积是怎么想到的
答案对人有帮助，有参考价值
答案没帮助，是错误的答案，答非所问
根据数学公式推导出来的
分享到微博？
关闭理由：
删除理由：
忽略理由：
推广（招聘、广告、SEO 等）方面的内容
与已有问题重复（请编辑该提问指向已有相同问题）
答非所问，不符合答题要求
宜作评论而非答案
带有人身攻击、辱骂、仇恨等违反条款的内容
无法获得确切结果的问题
非开发直接相关的问题
非技术提问的讨论型问题
其他原因（请补充说明）
我要该，理由是：
在 SegmentFault，学习技能、解决问题
每个月，我们帮助 1000 万的开发者解决各种各样的技术问题。并助力他们在技术能力、职业生涯、影响力上获得提升。&&32025 阅读
发布于，作者Stoimen
Strassen的矩阵相乘方法是一种典型的分治算法。目前为止，我们已经见过一些分治策略的算法了，例如和。现在，让我再来看看分治策略的背后是什么。
同动态规划不同，在动态规划中，为了得到最终的解决方案，我们经常需要把一个大的问题“展开”为几个子问题，但是这里，我们会更多的谈到如何把一些子解决方案组合到一起。这些子问题的解决方案是对等的，他们的归并方式也是通过某种方式定义好的。
一个典型的例子就是归并排序算法。在归并排序中，我们有两个有序数组，我们想要这两个数组在合并之后仍然保持有序。当然了，在归并排序中，最复杂的部分当属自我合并，而原因在于，我们不得不传递两个数组，A和B，然后去比较每一“对”分别来自数组A和数组B的元素。有一点离题，但是，这是归并排序的一个弱点，虽然，它的最坏情况的时间复杂度是 O(n.log(n))，但是，快速排序却往往是实践中更为有效的排序方法，因为，它没有“合并”的过程。仅仅把两个子数组连接到一起，请注意，在快速排序中，子数组一般并不具有相同的长度，虽然他的最坏时间复杂度是O(n^2)，但它的性能却经常好于归并排序。
在上文中，那个简单的例子告诉我们：有时候如何合并两个子问题并不是一个简单的事情。因此，当我们使用分治策略的时候，我们必须非常谨慎。
是一位出生于1936年的德国数学家。他因为在概率论上的工作而广为人知，但是在计算机科学和算法领域，他却因为矩阵相乘算法而被大部分人认识，这个算法目前仍然是比通用矩阵相乘算法性能好的主要算法之一。
Strassen在1969年第一次发表关于这个算法的文章，并证明了复杂度为n^3的算法并不是最优算法。实际上，Strassen给出的解决方案只是更好一点点，但是，他的贡献却是巨大的，因为他的工作触发了矩阵相乘领域更多的研究，比如复杂度为O(n^2,3737)的。
两个矩阵 A[NxN] 和 B[NxN] 相乘的通用算法是非常简单的。虽然矩阵相乘比两个数字相乘要复杂得多，而且也不满足交换律，但它仍然非常简单——同时也很慢。
让我们先来定义一下什么是A[NxN]矩阵。因为我们要说下NxN矩阵，让我们先想象一个有N行N列的方格网。在每一行和每一列的A[i][j]，我们都有一个值。
当然，作为一个开发者，我们可以把一个矩阵看成一个二维数组。
// PHP two-dimensional array
$a = array(
0 =& array($v1, $v2, $v3, $v4),
1 =& array($v5, $v6, $v7, $v8),
2 =& array($v9, $v10, $v11, $v12),
不要忘记，一个NxN的矩阵仅仅是矩阵中的一种情况，同样的，我们可以有其他任何大小的NxM阶矩阵(N && M)。
然而，为了和另外的矩阵相乘，矩阵的大小是非常重要的，为什么？
正如我上面提到的一样，矩阵相乘和数字相乘并不一样。首先，这个操作并不满足交换律。
第二个问题是，你用来相乘A和B的方法。
仅仅因为这种方法只对NxN阶矩阵有效，因此我们能看到把矩形矩阵相乘产生的问题。确实，这是不可能的，除非A矩阵的第二维和B矩阵的第一维相等。
不过好在我们现在正在讨论的是具有相同维数的方形矩阵。
好的，现在我们知道如何把两个方形矩阵相乘了（具有相同维数NxN），现在，让我们一起去估算一下通用矩阵相乘算法的时间复杂度。
我们知道A.B = C，当且仅当：
C[i][j] = sum(A[i][k] * B[k][j]) for k = 0 .. n
于是，我们有一个n^3复杂度的操作。现在，让我们尽力找一个分治策略的算法。
这个对于矩阵来说确实并不难，因为我们知道，一个矩阵可以被分成很多更小的子矩阵。
现在，我们有什么？
再一次——同样的时间复杂度——我们有了8个乘积和4个和，那么，计算量在哪？
当然， 为了得到更快的解决方案，我们不得不看一下Strassen在1969做过的工作。他如下图定义了P1, P2, P3, P4, P5, P6 和 P7。
时间复杂度
正如我以上提到的，Strassen算法仅仅比通用矩阵相乘算法好一点点。通用矩阵相乘算法时间复杂度是O(n^3)，然而Strassen算法复杂度则是O(n^2.80)。
你能在下图观察到，随着n的变大，Strassen算法是如何比通用矩阵相乘算法变得更有效率的。
虽然这个算法看起来更接近纯数学领域，而不是计算机领域。但在实际应用中，任何用到NxN数组的地方，我们都可以从矩阵相乘算法中获益。
另一方面，Strassen算法并不比n^3复杂度的通用矩阵相乘算法快很多。这很重要，因为对于一个很小的n(通常n&45)来说，通用矩阵相乘算法在实践中往往是更好的选择。然而，你可以从以上的图片中看到，对于n&100的情况来说，这两个算法的差别还是相当大的。
同时，当我们谈到|V| = n的邻接矩阵，以及一些依赖矩阵相乘的图论算法的时候，NxN数组经常会在这些领域中使用。
原文链接：
C++控，C控，算法控，QT控，Auto-Compile控，Meta-Programming控，排名分先后。代码洁癖症患者。
爱钻牛角尖，喜欢啃晦涩难懂的东西。I wrote two Matrix Multiplications programs in C++: Regular MM , and Strassen's MM , both of which operate on square matrices of sizes 2^k x 2^k(in other words, square matrices of even size).
Results are just terrible. For 1024 x 1024 matrix, Regular MM takes 46.381 sec, while Strassen's MM takes
sec (25 minutes !!!!).
I attempted to keep the code as simple as possible. Other Strassen's MM examples found on the web are not that much different from my code. One issue with Strassen's code is obvious - I don't have cutoff point, that switches to regular MM.
What other issues my Strassen's MM code has ???
Direct links to sources
Fist, a lot of great advices. Thank you for taking your time and sharing knowledge.
I implemented changes(kept all of my code), added cut-off point.
matrix, with cutoff 512 already gives good results.
Regular MM: 191.49s
Strassen's MM: 112.179s
Significant improvement.
Results were obtained on prehistoric Lenovo X61 TabletPC with Intel Centrino processor, using Visual Studio 2012.
I will do more checks(to make sure I got the correct results), and will publish the results.
One issue with Strassen's code is obvious - I don't have cutoff point,
that switches to regular MM.
It's fair to say that recursing down to 1 point is the bulk of (if not the entire) problem. Trying to guess at other performance bottlenecks without addressing this is almost moot due to the massive performance hit that it brings. (In other words, you're comparing Apples to Oranges.)
As discussed in the comments, cache alignment could have an effect, but not to this scale. Furthemore, cache alignment would likely hurt the regular algorithm more than the Strassen algorithm since the latter is cache-oblivious.
void strassen(int **a, int **b, int **c, int tam) {
// trivial case: when the matrix is 1 X 1:
if (tam == 1) {
c[0][0] = a[0][0] * b[0][0];
That's far too small. While the Strassen algorithm has a smaller complexity, it has a much bigger Big-O constant. For one, you have function call overhead all the way down to 1 element.
This is analogous to using merge or quick sort and recursing all the way down to one element. To be efficient you need to stop the recursion when the size gets small and fall back to the classic algorithm.
In quick/merge sort, you'd fall back to a low-overhead O(n^2) insertion or selection sort. Here you would fall back to the normal O(n^3) matrix multiply.
The threshold which you fall back the classic algorithm should be a tunable threshold that will likely vary depending on the hardware and the ability of the compiler to optimize the code.
For something like Strassen multiplication where the advantage is only O(2.8074) over the classic O(n^3), don't be surprised if this threshold turns out to be very high. (thousands of elements?)
In some applications there can be many algorithms each with decreasing complexity but increasing Big-O. The result is that multiple algorithms become optimal at different sizes.
Large integer multiplication is a notorious example of this:
Grade-school Multiplication: O(N^2) optimal for & ~100 digits*
: O(N^1.585) faster than above at ~100 digits*
: O(N^1.465) faster than Karatsuba at ~3000 digits*
: O(> N log(N)) faster than Karatsuba/Toom-3 at ~700 digits*
: O(N log(n) loglog(n)) faster than FFT at ~ a billion digits*
: O(N log(n) faster than SSA at ~ a few billion digits?*
*Note these example thresholds are approximate and can vary drastically - often by more than a factor of 10.
本文地址： &
我在C ++中写了两个矩阵乘法程序：Regular MM 和Strassen的MM ，它们都对大小为2 ^ kx 2 ^ k的方阵进行操作（换句话说， ）。
结果太糟糕了。对于1024 x 1024矩阵，常规MM需要 46.381秒，而Strassen的MM需要 秒 > 25分钟 !!!!）。
我试图保持代码尽可能简单。其他Strassen在网络上找到的MM示例与我的代码没有太大的不同。 Strassen的代码的一个问题是显而易见的 - 我没有截止点，切换到常规MM。
我的Strassen的MM代码有什么其他问题？
直接链接到源
Edit1。 拳头，很多很好的建议。谢谢你花时间和分享知识。
我实现了更改（保留了我的所有代码），添加了截止点。
MM为矩阵，截止512已经给出了良好的结果。 常规MM：191.49s
Strassen的MM：112.179s 显着改进。 结果是使用Visual Studio 2012在具有Intel Centrino处理器的史前联想X61 TabletPC上获得的结果。我将进行更多检查（以确保获得正确的结果），并将发布结果。 p>
Strassen的代码的一个问题是显而易见的 - 我没有临界点，
这是公平的说，递归到1点是大部分（如果不是整个）问题。试图猜测其他性能瓶颈而不解决这个问题几乎是不可能的，因为它带来了巨大的性能影响。 （换句话说，你正在比较苹果和橘子。）
正如在注释中讨论的，缓存对齐可能有效果，但不是这个尺度。由于后者是缓存不存在的，所以缓存对齐可能比Strassen算法更容易损害正则算法。
void strassen int ** a，int ** b，int ** c，int tam）{
//简单情况：矩阵为1时X 1： if（tam == 1 ）{c [0] [0] = a [0] [0] * b [0] [0];
这太小了。虽然Strassen算法具有较小的复杂性，但它具有更大的Big-O常数。一个，你有函数调用开销一直到1元素。
这类似于使用合并或快速排序和递归到一个元素。为了提高效率，您需要在大小变小并回到经典算法时停止递归。
在快速/合并排序中，您会回到低开销 O（n ^ 2）插入或选择排序。在这里，您将回到正常的 O（n ^ 3）矩阵乘法。
经典算法的阈值应该是一个可调阈值，可能会因硬件和编译器优化代码的能力而有所不同。
对于像Strassen乘法那样的优势只有 O（2.8074）超过经典的 O（n ^ 3），不要惊讶，如果这个阈值变得非常高。 （数千个元素？）
在某些应用程序中，可能有许多算法，每个都有递减的复杂性，但会增加Big-O。
大整数乘法是一个臭名昭着的例子：
成绩 - 乘法： O（N ^ 2）</?100 digit *
： O（N ^ 1.585 ）的速度超过100位数字*
： O（N ^ 1.465）比Karatsuba快约3000位数*
： O（> N log（N））比Karatsuba / Toom- 3 at?700 digits *
：<?10亿个数字
href =“http://en.wikipedia.org/wiki/Discrete_Fourier_transform_%28general%29#Number-theoretic_transform”>固定数字 - 理论变换： O（N log（n）比SSA快几十亿个数字？
*请注意，这些示例阈值是近似值， - 通常超过10倍。
本文地址： &
扫一扫关注官方微信下次自动登录
现在的位置:
& 综合 & 正文
第五篇&#8211;算法导论-矩阵乘法的Strassen算法
本篇文章主要介绍的是递归式的求解方法，strassen理论价值高于实际价值。
求解递归式的方法有三种：
代入法。猜测解的形式，然后用数学归纳法证明；
递归树法，这个方法简单易用；
主方法：对于形如：T(n)=aT(n/b)+f(n)
（a&=1 ,b&1)
朴素矩阵乘法伪码：
SQUARE-MATRIX-MULTIPLY(A,B)
let C be a new matrix
for i=1 to n
for j=1 to n
for k=1 to n
cij=cij+aik+bkj
其运行时间为theta(n^3)
Strassen算法的运行时间是theta(n^2.81)
对于C=A*B：
这样分解可降低乘法运算的规模；
即使这样，我们需要做对于n/2*n/2规模的矩阵乘法做8次，矩阵加法做4*n^2/4=n^2次，写出递归式如下：
=8T(n/2)+theta(n^2)
根据主方法：a=8,b=2,f(n)=theta(n^2),我们知道这属于第一种情况，此时得T(n)=theta(n^3)
再加上多出来的常数因子，这种方法效率低于朴素矩阵乘法；
而Strassen算法的运行时间却是T(n)=7T(n/2)+theta(n^2)，这样一来时间复杂度成为theta(n^2,81)，具体做法如下：
1.先定义十个矩阵S1...10：
这共进行了10次n/2*n/2的矩阵加减法，花费theta(n^2)
2.再定义7个矩阵P1...7，进行7次n/2*n/2乘法：
3.最后得：
C11=P5+P4-P2+P6
C22=P5+P1-P3-P7
总8次n/2*n/2矩阵加减法，花费theta(n^2)
strassen算法的具体代码后面同矩阵运算，稀疏矩阵乘法等一块实现；
从实用角度，Strassen算法通常不是一个好的选择：
1.隐藏在运行时间theta(N^2.81)后面的常数因子极大，当n&2000时，才能保证效率高于朴素矩阵乘法；
2.对于稀疏矩阵，专用算法更快；
3.Strassen算法数值稳定性不高；
4.消耗空间大；
【上篇】【下篇】Strassen矩阵乘法_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
Strassen矩阵乘法
&&矩阵乘法
阅读已结束，下载本文需要
想免费下载本文？
定制HR最喜欢的简历
你可能喜欢