矩阵-矩阵乘法

Question

我正在写一个包含矩阵乘法的C代码，并且我使用了3个嵌套循环来实现这个操作。那么，有谁知道我们如何通过删除其中一个嵌套循环来改进代码？

for (i = 0; i < SIZE; ++i)
    for (j = 0; j < SIZE; ++j)
        for (k = 0; k < SIZE; ++k)
            c[i][j] += a[i][k] * b[k][j];

Answer 1

稠密矩阵的矩阵乘法有O(n^3)。这可以通过使用Strassen's algorithm to O(n^(2.8))或Coppersmith-Winogar to O(n^(2.37))来加速。

Answer 2

Strassen算法是一个值得尝试的经典算法。

http://en.wikipedia.org/wiki/Strassen_algorithm

这比写三个循环更复杂，如果矩阵大小很小，总体速度增益可能不会显示出来。

据我所知，Mathematica和Matlab对较小的矩阵使用三嵌套循环乘法，对于较大的矩阵则切换到Strassen。

从理论上讲，还有其他算法的渐近性能更好，但除非您正在进行非常非常大的矩阵乘法，否则我认为它不会有太大帮助。