問題タブ [strassen]

行列乗算の Strassen Algorithm について読んでいます。

コーメンによるアルゴリズムの紹介で述べたように、アルゴリズムは直感的ではありません。ただし、アルゴリズムの厳密な数学的証明が存在するかどうか、およびアルゴリズムの設計に実際に何が使用されたかを知りたいです。

Google と stackoverflow で検索してみましたが、すべてのリンクは、Strassen のアプローチを標準の行列乗算アプローチと比較するだけであるか、アルゴリズムによって提示される手順について詳しく説明しています。

Strassen の行列乗算アルゴリズムが実際のコンピューターでより効率的になるのはいつですか? 実際に実装されているところはありますか？どんな参考文献も大歓迎です。ありがとう。

各再帰で8回の再帰呼び出しを必要とする行列乗算の単純なDivide＆Conquerアルゴリズムのインデックス操作により、インプレースソリューションを実装することができました。しかし、Strassen アルゴリズムを実装しようとすると、その場で実装する方法が見つかりませんでした。代わりに、C を使用してプログラムするときに、7 回の再帰呼び出しのために 19 個のサブ行列を malloc する必要があります。

Strassenアルゴリズムをインプレースで実装する方法は? それとも可能ですか？

Strassen アルゴリズムを C++ で実装しようとしています。正方行列 'hA' を 4 つの等しいブロックに分割したいと考えています。

上記の方法でパーティショニングを行ったところ、以下の出力に示すようにエラーが発生しました。しかし、「if else」はしごの最後の比較を削除すると、うまく機能します。

'i' の値がループ条件外でも間違っているのはなぜですか? この方法よりもパーティショニングを行う便利な方法はありますか?

休憩時間の宿題として、私たちの教授は、Strassen のアルゴリズムがブルート フォースよりも効率が低くなるポイントを見つけるように私たちに依頼しました (具体的には、ブルート フォースに行く前に、このマシンで何回の再帰を行う必要がありますか?)。

私はJavaにいますが、ブルートフォースに戻すのに本当に苦労しています。ランナー クラス、ブルート フォース クラス、Strassen を呼び出すクラス、Strassen 自体のクラスがあります。今のところ、ストラッセンのクラスだけを上げます。ユーザーに再帰を何回実行したいか尋ね、それをパラメーターとして Strassen に渡します。アイデアは、「深さ」が割り当てられた再帰回数よりも大きくなると、ブルートフォースメソッドを呼び出して終了するというものです。私は完全に途方に暮れており、おそらくこれに正しくアプローチしていませんが、明確な指示が得られず、1週間さまざまなアプローチを試みてきましたが、役に立ちませんでした.

行列乗算の Strassen アルゴリズムを作成しています。このアルゴリズムの基本は、行列 A (N * N) を四分の一 A1 ～ A4 (N / 2 * N / 2) に分割することです。これを行うには、サイクルを使用して、行列の各 4 分の 1 にメモリを割り当てます。

追加のマトリックスなしで、これを行う簡単な方法はありますか? (A1=A [0 ... (n / 2)-1, 0 ... (n / 2)-1] 例)?

Strassen 行列乗算アルゴリズムを順次および並列の両方で実装しようとしています。次のコードを並列に実行したいのですが、並列プログラミングの経験がありません。

私はウェブを検索し、可能な解決策を見つけて、コードを再度整理しました：

2、4、8、16 のような少数の配列次元に対してプログラムを実行すると、順次バージョンとほぼ同じ時間で動作します。100 や 1000 などの大きな次元の場合、結果の計算には順次バージョンよりもはるかに長い時間がかかります。私の並列実装は間違っていますか?

私はPythonが初めてです。Strassenのアルゴリズムを実装しようとしています。私の実装では、行列のサイズは常に 2 の累乗になります。では、マトリックスを 4 つの等しいサイズの象限に分割するにはどうすればよいでしょうか。ありがとう