algorithm - Strassen アルゴリズムのインプレース実装?

Question

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

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

Answer 1

2 つの nxn 行列を乗算しているとします。4n^2 の整数のためのスペースが必要です: 2n^2 は乗算される行列用、n^2 は結果用、最後の n^2 はスクラッチ作業用です。スクラッチ ワーク マトリックスを再帰的に使用します。つまり、Strassen を追加して作成する 2 つの部分行列のそれぞれにその 1/4 を使用し、乗算の結果に 1/4 を使用し、最後の 1/4 をその乗算のスクラッチ作業に使用します。など...再帰したい限り。