为什么Strassen矩阵乘法比标准矩阵乘法慢得多？
我已经用C++、Python和Java编写了矩阵乘法程序，并测试了它们将两个2000 x 2000矩阵相乘的速度(请参阅post)。标准的ikj-implentation -它在
- took:
现在我已经实现了Strassen algorithm for matrix multiplication -它在
在Python和C++中的
- ，就像在维基百科上一样。下面是我拥有的时间：
为什么斯特拉森矩阵乘法比标准矩阵乘法慢得多？
想法：
出现effects
- Implementation：
- 错误(生成的2000 x 2000矩阵为correct)
- null-multiplication (对于2000 x 2000 effects
- Implementation: 2048 x 2048)
来说，这并不重要
这特别令人惊讶，因为它似乎与其他人的经验相矛盾：
- Why is my Strassen Matrix multiplier so fast?
- Matrix multiplication: Strassen vs. Standard - Strassen对他来说也更慢，但至少是在相同的数量级。
编辑: Strassen矩阵乘法在我的例子中速度较慢的原因是：
我让它完全递归(参见tam)，我有两个函数strassen和strassenRecursive。如果需要，第一个将矩阵调整为2的幂，然后调用第二个。但是strassen.并没有递归地调用strassenRecursive本身
回答 4
Stack Overflow用户
发布于 2012-07-16 05:30:18
基本的问题是，使用strassen实现，您会递归到叶大小为1。Strassen的算法具有更好的大O复杂度，但常量在现实中确实很重要，这意味着在现实中，对于较小的问题大小，使用标准的n^3矩阵乘法会更好。
因此，要大大改进你的程序，而不是做以下事情：
if (tam == 1) {
C[0][0] = A[0][0] * B[0][0];
return;
}使用if (tam == LEAF_SIZE) // iterative solution here。LEAF_SIZE应该是一个常量，对于给定的体系结构，您必须通过实验确定该常量。根据架构的不同，它可能更大，也可能更小--在某些架构中，strassen的常数因子非常大，以至于它基本上总是比更简单的n^3实现更差。这要视情况而定。
Stack Overflow用户
发布于 2012-07-16 05:37:22
好吧，“算术运算”并不是唯一重要的东西。并不是所有的东西都是免费的。
我天真的猜测是，所有这些内存分配和复制都超过了减少算术运算所带来的收益……
特别是内存访问，当它离开缓存时，它可能会非常昂贵，相比之下，算术操作可以被认为是免费的:-)
Stack Overflow用户
发布于 2012-07-16 05:34:09
虽然Strassen算法有一个较小的Big O符号，但为了利用这一点，您需要乘以在大多数标准机器甚至超级计算机上太大而无法求解的矩阵。
这样想吧
一个问题是x^3，另一个问题是X^1.6734 + 8x^(1/2) +x.....
https://stackoverflow.com/questions/11495723
复制相似问题
腾讯云开发者
