algorithm - 高階行列乗算

Question

複数のプロセスを使用して C で行列乗算を実行しようとしています。各子プロセスは行列の 1 行を計算しています。しかし、例えば 200 程度の場合、200 個のプロセスがあり、2 3 個の CPU では非効率的です。プロセス数を 10 または 12 に維持したい場合、どうすれば同じように進めることができますか。計算順序に変更はありますか?

Answer 1

行列乗算で複数のプロセスを利用する 1 つの方法は、再帰アルゴリズムから始めることです。たとえば、Strassen アルゴリズムは問題を再帰的に小さな乗​​算に分割し、任意の数のプロセッサにオフロードできます。さらに、通常の行列乗算は O(N^3) のオーダーですが、Strassen アルゴリズムはこれを O(N^2.8) に下げることができます。これは、より大きな行列の場合に相当な数になる可能性があります。

注: 通常、高次とは級数展開の拡張された項、多項式のより多くの項などを指し、通常は正方行列のサイズではありません。