如何在时间复杂度方面优化cpp中的矩阵乘法？

Question

鉴于任何2个matrics 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).它甚至不是我们所知道的最快的.就我而言,目前最好的是Coppersmith-Winograd算法(参见https://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm),它就像O(n^{2.37})(Strassen的时间复杂度就像O(n^{2.8}).

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

还有一个Strassen的假设,它声称每一个eps > 0都有一个算法,它将两个矩阵与时间复杂度相乘 O(n^{2 + eps}).但是你可能已经注意到它现在只是一个假设.