1

我正在编写一个包含矩阵乘法的 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];
4

2 回答 2

3

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

于 2012-11-20T08:38:50.333 回答
1

Strassen algorithm is a classic one to try.

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

It is more complicated than writing three loops and the overall speed gain might not show through if the matrix size is small.

As far as I know, Mathematica and Matlab use the three nested loop multiplication for small matrices and switch to Strassen for larger ones.

There are other algorithms that theoretically perform better asymptotically, but unless you are doing very very large matrix multiplication, I don't think it will help that much.

于 2012-11-20T08:41:38.867 回答