20

私は C++、Python、および Java で行列乗算用のプログラムを作成し、2 つの 2000 x 2000 行列を乗算する速度をテストしました (投稿を参照)。標準の ikj-implentation - にあるここに画像の説明を入力- は次のようになりました。

これで、ウィキペディアにあったように、行列乗算用の Strassen アルゴリズムをPythonここに画像の説明を入力と C++ で実装しました。これらは私が持っている時間です：

Strassen 行列乗算が標準の行列乗算よりも遅いのはなぜですか?

アイデア:

  • 一部のキャッシュ効果
  • 実装：
    • エラー (結果の 2000 x 2000 マトリックスは正しい)
    • null-multiplication (2000 x 2000 -> 2048 x 2048 ではそれほど重要ではないはずです)

これは、他の人の経験と矛盾しているように見えるため、特に驚くべきことです。

編集: 私の場合、Strassen 行列の乗算が遅くなった理由は次のとおりです。

  • 私はそれを完全に再帰的にしました (タムを見てください)
  • と の 2 つの機能がstrassenありstrassenRecursiveました。最初のものは、必要に応じて行列のサイズを 2 のべき乗に変更し、2 番目のものと呼びました。しかしstrassenRecursive、再帰的に自分自身を呼び出しませんでしたが、strassen.
4

4 に答える 4

17

基本的な問題は、strassen 実装でリーフ サイズ 1 まで再帰していることです。Strassen のアルゴリズムの Big O の複雑さは優れていますが、実際には定数が問題になります。つまり、実際には、問題のサイズが小さい場合は、標準の n^3 行列乗算の方が適しています。

したがって、次のことを行う代わりに、プログラムを大幅に改善するには:

if (tam == 1) {
        C[0][0] = A[0][0] * B[0][0];
        return;
    }

使用してif (tam == LEAF_SIZE) // iterative solution hereください。LEAF_SIZE特定のアーキテクチャに対して実験的に決定する必要がある定数である必要があります。アーキテクチャによっては、より大きくなったり小さくなったりする可能性があります - Strassen の定数係数が非常に大きく、合理的な行列サイズの単純な n^3 実装よりも基本的に常に悪いアーキテクチャがあります。それはすべて依存します。

于 2012-07-15T21:30:17.767 に答える
6

まあ、「算術演算」だけがカウントされるわけではありません。他のすべてが無料というわけではありません。

私の素朴な推測では、このすべてのメモリ割り当てとコピーは、算術演算が少ないことによる利益よりも優れていると思います...

特に、メモリアクセスは、キャッシュから取得すると非常に高価になる可能性があります。これに比べて、算術演算は無料と見なすことができます:-)

于 2012-07-15T21:37:21.913 に答える
0

Strassen アルゴリズムの Big O 表記は小さくなっていますが、これを利用するには、ほとんどの標準マシンやスーパー コンピューターで解くには大きすぎる行列を乗算する必要があります。

このように考えてみてください

1 つの問題は x^3 で、もう 1 つは X^1.6734 + 8x^(1/2) +x .....

于 2012-07-15T21:34:08.513 に答える