如何优化矩阵乘法CPP的时间复杂度？

Question

给定任意两个矩阵A和B（不具有特殊性能）我们是否有计算乘法比这更好的方法：？

for(i=0; i<r1; ++i)
for(j=0; j<c2; ++j)
for(k=0; k<c1; ++k)
{
    mult[i][j]+=a[i][k]*b[k][j];
}

Answer 1

如果你是好奇，如果他们在理论上存在，那么肯定的。例如，Strassen的算法（见https://en.wikipedia.org/wiki/Strassen_algorithm）。而且它甚至不是我们所知道的最快的。至于我而言最好的，现在是铜匠，威诺格拉德算法（参见https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm），它是像O(n^{2.37})（施特拉森的时间复杂度是一样的东西O(n^{2.8})。

但在实践中，他们更难比你写的一个实现，也他们有相当大的时间常数O()你写的，甚至更好的和O(n^3)的低值更容易实现这样n算法下隐藏。

也有一个施特拉森的假说声称，每eps > 0有一个算法，它乘两个矩阵与时间复杂度O(n^{2 + eps})。但是，正如你可能已经注意到，这只是一个假设现在。

Answer 2

作为一个非常简单的解决方案，您可以移调乘法之前的第二矩阵，所以你的代码就会变得更少的处理器高速缓存未命中。复杂性将是相同的，但它可以改善的时间常数的位。

Answer 3

这些都是在这个世界上许多鲜艳的灵魂在你面前已经解决了这个问题。不要折磨自己，并使用BLAS？GEMM。

http://www.netlib.org/blas/#_level_3

Answer 4

这是一个很好的问题，值得不是“使用库”一个更完整的答案。

当然，如果你想做好，你可能不应该尝试自己编写。但是，如果这个问题是学习如何做矩阵乘法快，这里是一个完整的答案。

1. 作为一个实际问题，你展示的代码写入到内存太多。如果内循环增加的点积在一个标量变量，那么只有在写结束时，代码会更快。大多数编译器不够聪明，明白这一点。 双点= 0;为（K = 0; k

这也提高了多核的性能，因为如果你使用多个内核，他们必须共享内存带宽。如果使用的行的阵列，切换广告表示以存储器的单个块。

2. 正如有人上面提到的，你可以做一个这样的转置矩阵遍历都按顺序。内存被设计成连续有效地读取，但你的B [k]的[j]的跳来跳去，所以这是大约3倍速度通常为尺寸变大（的1000×1000的顺序，初始转置的成本是可以忽略不计） 。
3. 当基质变得足够大，施特拉森和铜匠，威诺格拉德是乘法，从根本上改变规则的更快的方式，但他们通过巧妙地重新排列项目，实现了一个捆绑较低的复杂度相同的理论结果这样做。在实践中，他们改变了答案，因为舍入误差是不同的，对于大型矩阵，这些算法产生的答案很可能是远高于蛮力乘法更糟。
4. 如果你有一个真正的并行计算机，你可以复制矩阵到多个CPU，并让它们并行工作的答案。
5. 你可以把代码到你的显卡，并使用更并行的CPU有它有更多的内存带宽。这可能让你的计算机上的真正加速的最有效的方法（假设你有一个显卡）。见CUDA或福尔康。

最根本的问题是，多内核没有多大帮助的矩阵乘法，因为你是内存带宽的限制。这就是为什么做一个显卡上是如此的好，因为带宽有高得多。

Answer 5

你可以通过将乘法给他们使用多线程。所以划分第一矩阵或最后的最后一个维度的第一维度的行/列成数等于你在你的处理器具有核心任务。如果这些都不整除，一些核心必须做额外的周期。但无论如何，这个想法是给乘法更多的核心和例如划分在4份（I有4个内核）的第一矩阵，执行乘法与4级的任务，和重新组装（即不必需的，因为核可以在相同的数据工作）。