12

最良の行列乗算アルゴリズムは何ですか? 私にとっての「最高」とは？これは、今日のマシンで最速かつ準備ができていることを意味します。

可能であれば、疑似コードへのリンクを提供してください。

4

8 に答える 8

12

BLAS は、すぐに使える効率的な行列乗算ライブラリです。多くの異なる実装があります。これは、デュアルコア Intel Core 2 Duo 2.66 GHz を搭載した MacBook Pro でのいくつかの実装に対して作成したベンチマークです。

代替テキスト

ここでテストしなかった他の商用実装もあります。

于 2010-12-16T09:51:00.917 に答える
8

最良の行列乗算アルゴリズムは、詳細なアーキテクチャの知識を持つ誰かが既にターゲット プラットフォーム用に手動で調整したものです。

調整された行列乗算の実装を提供する優れたライブラリがたくさんあります。それらの1つを使用してください。

于 2010-12-15T22:50:04.523 に答える
8

おそらくもっと良いものがありますが、これらは私が頭を悩ませているものです（標準の3次複雑度アルゴリズムよりも優れています）。

Strassen's - O(N^2.8)

銅細工師ウィノグラード- O(N^2.376)

于 2010-12-15T22:53:48.357 に答える
6

なぜ疑似コード？なぜ自分で実装するのですか？速度が気になる場合は、特定の命令セット (SIMD など) の最適化を含む、高度に最適化されたアルゴリズムが利用可能です。それらをすべて自分で実装すると、(おそらく学習を除いて) 本当の利点はありません。

次のようなさまざまなBLAS実装を見てみましょう。

http://www.netlib.org/blas/

http://math-atlas.sourceforge.net/

于 2010-12-15T22:38:43.843 に答える
3

MITのアルゴリズム講座と行列乗算の講義はこちら

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-19-shortest- paths-iii-all-pairs-shortest-paths-matrix-multiplication-floyd-warshall-johnson/

行列の乗算 - O(n^3)

Strassen のアルゴリズム - O(n^2.8) http://en.wikipedia.org/wiki/Strassen_algorithm

Coppersmith–Winograd - O(n^2.376) http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm

于 2010-12-16T05:38:59.830 に答える
2

行列のサイズと、疎であるかどうかによって異なります。

小規模から中規模の密行列の場合、キャッシュの一貫性に注意を払い、プラットフォームのベクトル命令を使用する場合、「素朴な」O(N^3) アルゴリズムのいくつかのバリエーションが有利であると私は信じています。

データの配置は重要です。標準の行列レイアウトがキャッシュに適していない場合 (例: 列優先 * 行優先)、行列乗算のバイナリ分解を試す必要があります。 「高速」アルゴリズムの場合、この操作順序により、すべてのレベルのキャッシュを自動的に有効活用する「キャッシュ無視」アルゴリズムを生成できます。行列を並べ替える余裕がある場合は、これをデータ要素のビット インターリーブ (または「Z オーダー」) 順序付けと組み合わせてみてください。

最後に、時期尚早の最適化は諸悪の根源であることを忘れないでください。そして、時期尚早ではない場合は、最適化の前、最中、後に常にプロファイリングとベンチマークを行ってください....

于 2010-12-16T00:54:53.730 に答える
0

Cannon's algorithm分散行列乗算アルゴリズムと呼ばれるアルゴリズムがあります。詳細はこちら

于 2010-12-15T22:37:44.230 に答える
0

最新のすべての CPU のすべての行列に「最適なアルゴリズム」はありません。

利用可能な多くの方法について調査を行い、扱っている特定のハードウェアで計算している特定の問題に対する最適な解決策を見つける必要があります。

たとえば、ハードウェア プラットフォームでの「最速」の方法は、「遅い」アルゴリズムを使用することですが、GPU にそれを 256 の行列に並列に適用するように依頼することです。または、「高速」な汎用 (mxn) アルゴリズムを使用すると、最適化された 3x3 行列乗算を使用するよりもはるかに遅い結果が生成される場合があります。本当に高速にしたい場合は、移植性を犠牲にして、SIMD 命令、分岐予測、キャッシュ コヒーレンスなどの特定の CPU 機能を最大限に活用するために、ベア メタルに移行することを検討することをお勧めします。

于 2010-12-15T23:07:22.400 に答える