c - 行列-行列乗算

Question

行列の乗算を含む C コードを書いており、その操作に 3 つのネストされたループを使用しています。では、ネストされたループの 1 つを削除して、そのコードを改善する方法を知っている人はいますか?

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];

score 3 · Accepted Answer

密行列の行列乗算は O(n^3) です。これはStrassen のアルゴリズムを O(n^(2.8)) に、またはCoppersmith-Winogarを O(n^(2.37))に使用することで加速できます。

score 1 · Accepted Answer

Strassen アルゴリズムは、試すべき古典的なアルゴリズムです。

3 つのループを記述するよりも複雑であり、行列のサイズが小さい場合、全体的な速度の向上が見られない可能性があります。

私の知る限り、Mathematica と Matlab は小さな行列には 3 つのネストされたループ乗算を使用し、大きな行列には Strassen に切り替えます。

理論的には漸近的により優れたパフォーマンスを発揮するアルゴリズムは他にもありますが、非常に大きな行列の乗算を行っていない限り、それほど役立つとは思いません。

2 に答える 2