問題タブ [strassen]

Pythonを使用してStrassenのMatrix Multiplicationを実装しています。分割ステップでは、大きなマトリックスを小さなサブマトリックスに分割します。行列を分割する組み込みの numpy 関数はありますか?

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

• C++ : 15 秒 (ソース)
• Python : 6 分 13 秒 (ソース)

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

• C++ : 45 分 (ソース)
• Python : 10 時間後に強制終了 ( Source )

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

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

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

• Strassen Matrix 乗数が非常に高速なのはなぜですか?
• 行列の乗算: Strassen vs. Standard - Strassen も彼にとっては遅かったのですが、少なくとも同程度でした。

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

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

Strassen のアルゴリズムで再帰呼び出しを行う方法と、それらが必要な正確な場所を知りたいです。

7 つの乗数が 8 つの乗数よりも効率的であることは理解していますが、これらの乗数が再帰的にどのように計算されるかについては混乱しています。特に、分割統治のパラダイムに従っている場合、マトリックスの正確にどの部分を「分割」しているか、再帰部分を個別に征服できる基本ケースに到達するまで、どのように分割を行うのでしょうか?

ありがとうございました！

私はJavaでStrassenのアルゴリズムを実装しようとしていますが、出力を単一の行列/2D配列に結合する必要がある段階にあります。私はSystem.arraycopy配列をコピーするために使用しています。これは、2つの配列をトップダウンで連結するのに適していますが、それらを並べて連結する必要もあり、問題が発生しています。私はに遭遇しArrayOutOfBoundsExceptionます。これが私のコードです

最後の行

例外をスローします。配列を並べて（列単位で）連結する方法はありますか？

1 から 10 の範囲のランダムな整数でいっぱいの NxN 行列があるとします。PROC(A(1:n/2, 1:n/2)+A(n/2+1:n, n/2+1:n)...ここで、 n が行列のサイズである場所を呼び出したいと思います 。言い換えれば、A の最初の行と列から始まり、A の半分のサイズになるまで部分行列を作成し、それを A の半分のサイズから始まり、最後まで続く部分行列に追加したいと考えています。 A.

私が使用しているパーティション関数は次のとおりです。

これで、特定の行列の左上 ( Matrix C = m.partition(1, m.size()/2, 1, m.size()/2);) にある部分行列を見つけることができます。

しかし、別のサブマトリックス ( Matrix D = m.partition(m.size()/2+1, m.size(), m.size()/2+1, m.size());) を取得しようとすると、ArrayIndexOutOfBoundsException: 2. パーティション関数に個別の行カウンターと列カウンターを追加しようとしましたが、同じエラーが発生しました。パーティション関数を変更して、すべての入力で動作し、正しい出力が得られるようにするにはどうすればよいですか?

Python で Strassen Matrix 乗算を実装しようとしています。だいぶ効いてきました。これが私のコードです：

適切な目的の出力を参照するために、ストレート行列乗算を含めました。基本的にこれは起こります：

Strassen 出力:

次のようにする必要があります。

問題の原因がわかりません。つまり、解決できません。

私はC++で2つの行列乗算プログラムを作成しました。通常のMM （ソース）とStrassenのMM （ソース）です。どちらもサイズ2 ^ kx 2 ^ kの正方行列（つまり、偶数サイズの正方行列）で動作します。

結果はひどいです。1024 x 1024マトリックスの場合、通常のMMは46.381 sec、を取りますが、StrassenのMMは1484.303 sec（25 minutes!!!!）を取ります。

私はコードをできるだけ単純に保つように努めました。Web上にある他のStrassenのMMの例は、私のコードとそれほど変わりません。Strassenのコードに関する1つの問題は明らかです。通常のMMに切り替わる、カットオフポイントがありません。

私のStrassenのMMコードには他にどのような問題がありますか？

ありがとう ！

ソースへの直接リンク
http://pastebin.com/HqHtFpq9http://pastebin.com/USRQ5tuy

編集1。拳、たくさんの素晴らしいアドバイス。時間を割いて知識を共有していただきありがとうございます。

変更を実装し（すべてのコードを保持）、カットオフポイントを追加しました。2048x2048マトリックスのMM、カットオフ512は、すでに良好な結果をもたらしています。通常のMM：191.49s StrassenのMM：112.179s大幅な改善。結果は、Visual Studio 2012を使用して、IntelCentrinoプロセッサーを搭載した先史時代のLenovoX61 TabletPCで取得されました。さらにチェックを行い（正しい結果が得られたことを確認するため）、結果を公開します。

さて、《アルゴリズム入門》からの質問で、番号は4.2-6です。次のように説明されています。

をとしてa kn*n matrix by an n*kn matrix使用して、どのくらい速く掛けることができますか?Strassen's algorithmsubroutine

2 つの行列の両方を に拡張することを考えていkn*kn matrixます。その後、この質問に Strassen のアルゴリズムを適用できます。しかし、私はMath.pow(kn, lg7) running time.

誰もがより良い解決策を持っていますか。皆様、新年あけましておめでとうございます。

Strassen の実装が非常に遅い理由を特定するのに苦労しています。反復ごとにメモリを割り当てますが、必要に応じてすべて解放しています。