c++ - Strassen のアルゴリズムにおける再帰

Question

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

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

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

Answer 1

これらの 7 つの乗数を計算しながら、再帰呼び出しを行います。最初に行列のサイズを 2 の累乗に拡張し、次に各ステップで各行列を 4 つの部分に分割します。

Answer 2

A と B を 4 分の 1、16 分の 1、64 分の 1 などに均等に分割して、2x2 の行列にします。Strassen の方法は、2^nx 2^n 型の行列にのみ適用できます。

タイプ 2^nx 2^n でない行列の場合、要件が満たされるまでゼロ パディングできます。