問題タブ [strassen]

kxk行列を乗算するためのStrassenのアルゴリズムのこの分析を理解しようとしています。しかし、いくつの操作が関与しているのかはまだよくわかりません。誰かがこれを明確にするのを助けることができますか?

誰かが直感的な方法で行列乗算のための Strassen のアルゴリズムを説明できますか? 本と wiki の説明を確認しました (まあ、確認しようとしました) が、2 階をクリックしていません。正式な表記法などではなく英語を多く使用している Web 上のリンクも役立ちます。このアルゴリズムを暗記せずにゼロから構築するのに役立つ類似点はありますか?

アルゴリズムとデータ構造の自習をしているところですが、Strassenの行列乗算アルゴリズムのC＃（またはC ++）実装を持っている人がいるかどうか知りたいですか？

私はそれを実行して、それが何をするのかを見て、それがどのように機能するのかについてもっと理解したいと思います。

C++ で行列乗算用のStrassen アルゴリズムを実装しようとしましたが、期待どおりの結果が得られませんでした。ご覧のとおり、strassen は常に標準の実装よりも時間がかかり、次元が 2 の累乗の場合のみ、標準の実装と同じくらい高速です。何が悪かったのか？

g++ main.cpp matrix.cpp -o matrix -O3.

Strassen のアルゴリズムをどこかからコピーして実行しました。ここに出力があります

ここで、はキャッシュ用strassen1の動的アプローチで、は古い行列乗算です。これは、私たちの古くて簡単な古典的なものが最高であることを意味します. これは本当ですか、それともどこか間違っていますか? ここにJavaのコードがあります。strassen2classical

実験として、Strassen Matrix Multiplication Algorithm を実装して、大きな n に対して本当に高速なコードが得られるかどうかを確認しました。

https://github.com/wcochran/strassen_multiplier/blob/master/mm.c

驚いたことに、n が大きいほど高速でした。たとえば、n=1024 の場合、従来の方法を使用すると 17.20 秒かかりましたが、Strassen 方法 (2x2.66 GHz Xeon) を使用すると 1.13 秒しかかかりませんでした。なんと -- 15 倍のスピードアップ!? わずかに高速になるだけです。実際、小さな 32x32 行列にも同じように適しているように見えました!?

これほどの高速化を説明できる唯一の方法は、アルゴリズムがよりキャッシュに適しているということです。つまり、アルゴリズムは行列の小さな断片に焦点を当てているため、データがよりローカライズされています。可能であれば、すべての行列演算を少しずつ行う必要があるかもしれません。

なぜこれがとても速いのかについての他の理論はありますか?

私はCでのシュトラッセンのアルゴリズムの実装を探していましたが、最後にこのコードを見つけました。

関数を使用するにはmultiply：

aこれは2つの行列を乗算bし、その結果をc（d中間行列）に入れます。マトリックスaとbは、次のタイプである必要があります。

私は動的に4つの行列、、、（adoubleの2次元配列）を割り当て、それらのアドレスをフィールドに割り当てました：bcd_matrix.d

このコードは正常にコンパイルされますが、n>でクラッシュしますBREAK。

strassen.c：

strassen.h：

私の質問は、関数の使用方法multiply（マトリックスの実装方法）です。

strassen.h

strassen.c

Strassen のアルゴリズムの奇数行列の問題に対処しようとしています。私の実装では、特定の時点で再帰を切り捨て、それを Q と呼び、標準の実装に切り替えます。したがって、静的なパディングを行う場合、実際には次の 2 のべき乗までパディングする必要はありません。m < Q となるように、入力行列の次元よりも大きい最小の m*2^k までパディングする必要があるだけです。

これを実装するのに問題があります-主に、何が最も効率的かがわからないためです。可能なすべての m 値をループする必要がありますか?それとも、与えられた各入力からインクリメントして、それらが基準を満たしているかどうかをテストする必要がありますか?