問題タブ [strassen]

結果は Strassen() : 27 秒および muliply_mat() : 5 秒です。

Multiply_mat() よりも短くするにはどうすればよいですか??

問題は、strassen 関数の new_mat 関数だと思います。

Strassen 関数を使用して時間を短縮するにはどうすればよいですか。

このコードは時間がかかると思います。

どうすれば Strassen() から抜け出すことができますか?

C++ で Strassen-Winograd アルゴリズムを作成するタスクがありました。2 回書きましたが、最初のバージョンのコードは機能しません。結果は、結果マトリックスの左下隅に表示されます。そして、私の 2 番目のバージョンは、N = 64+ であっても、単純なアルゴリズムよりも実行が遅くなります。

私は何を間違っていますか？

重要な注意: 再帰と構造で動的行列を使用することは許可されていません。さらに、部分行列のコーナー要素の座標を使用して、コピーせずに乗算を実行することをお勧めします。

正しくない：

遅い、締め切りのデフォルト 1:

私はアルゴリズムのコースを受講していて、行列を乗算するための Strassen のアルゴリズムについて学びました。これをノードに実装しましたが、小さな行列で動作します。非常に大きなマトリックスでテストしたいのですが、作成しようとするとノードのコア ダンプが発生します。サイズ 10000 の最初のマトリックスを作成できますが、2 番目のマトリックスを作成しようとするとクラッシュします。以下の完全なスタック トレース:

マトリックスを作成するために使用するコードを含めています。

この問題の解決策はありますか?

行列の乗算について、単純な Strassen 法をテストしようとしています。

ただし、Strassen アルゴリズムは単純なアプローチよりも動作が遅くなります。サイズが 1024 の行列の場合、単純なアプローチは 3542 ミリ秒で完了し、Strassen は 83602 ミリ秒で完了します。(Strassen はカットオフ/ナイーブ アプローチを使用していません) これが私が使用している Strassen コードです。LEAF SIZE は、単純なアプローチに切り替える数値です。

葉のサイズが約 32 の場合、実際に高速に実行されます (これは単純なアルゴリズムが作動するカットオフ ポイントです)。

これはJava言語です。コードはインターネットからのものですが、多かれ少なかれすべての実装は似ています。

カットオフポイントのないストラッセンだけでナイーブを倒すことはできないのでしょうか？どんなアイデアでも大歓迎です。ありがとうございました。

編集add メソッドと減算メソッドが追加されました。

EDIT2コードから、新しいサブマトリックスの作成による最大のオーバーヘッドはありますか? もしそうなら、可能な限り多くのオーバーヘッドを取り除くためにどのような方法を適用できますか? Java で何もできない場合、私は C++ の使用に反対していません。

EDIT3ここで使用されているメモリ割り当てを減らす方法を提案できる人はいますか? 提案に感謝します。