問題タブ [strassen]

初めて質問するので、間違っていたらすみません。

私はmatlabでStrassenのアルゴリズムをコーディングしようとしていますが、うまくいくようですが、非常に遅いです(カットオフによっては、64x64マトリックスですでに1秒以上かかる場合があります)。

単純な実装 (3 つのループ) よりも遅くなります。私がひどく間違っていることはありますか？以下は関数です。入力は既に正しいサイズ (2^n) です。

これは、stackoverflow に関する私の最初の質問です。私は、タマシアのグッドリッチによる「アルゴリズム設計」からいくつかの演習を解いてきました。しかし、私はこの問題についてまったく無知です。どこから始めて、どのように進めればよいか。どんなアドバイスも素晴らしいでしょう。問題は次のとおりです。

ブール行列は、各エントリが 0 または 1 である行列であり、* の場合は AND、+ の場合は OR を使用して行列の乗算が実行されます。2 つの NxN のランダムなブール行列 A と B が与えられ、いずれかのエントリが 1 である確率が 1/k であるとします。k が定数の場合、予想される実行時間が O(n^2) である A と B を乗算するアルゴリズムがあることを示します。k が n の場合はどうなりますか?

3 分割 (n ビット数を n/3 ビットの 3 つの部分に分割) を使用し、O(n^1.46) を取る整数乗算用の Strassen のアルゴリズムのバージョンがあります。

私の質問は、O(n^1.59) を使用する 2 分割の通常の方法よりも、この方法が一般的に好まれないのはなぜですか? 理解するのに役立つアイデアやリンクはありますか? （ネットで調べましたがわかりませんでした）

Strassen のアルゴリズムをブール行列の乗算に使用できるかどうか疑問に思っていますか? 通常の行列乗算に使用されることは知っていますが、ブール値についてはよくわかりません。

また、可能であれば、Four Russians メソッドを使用するよりも漸近的に高速であり、一般的にブール乗算に使用する必要がありますか?

私は初心者で、Strassen のアルゴリズムを実装して 2 つの NxN 行列を乗算しようとしました。私は現在、偶数次元に取り組んでいます。N の値が 4 を超えると、セグメンテーション違反が発生します。

デバッグ後、乗算関数の最初の呼び出しの前、および 2 つの行列を表示した直後にセグメンテーション違反が発生することがわかりました。

どんな助けでも大歓迎です。

どうもありがとう！