c - 矩阵-矩阵乘法

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 来加速。到 O(n^(2.8)) 或 Coppersmith-Winogar到 O(n^(2.37))。