行列乗算の Strassen Algorithm について読んでいます。
コーメンによるアルゴリズムの紹介で述べたように、アルゴリズムは直感的ではありません。ただし、アルゴリズムの厳密な数学的証明が存在するかどうか、およびアルゴリズムの設計に実際に何が使用されたかを知りたいです。
Google と stackoverflow で検索してみましたが、すべてのリンクは、Strassen のアプローチを標準の行列乗算アプローチと比較するだけであるか、アルゴリズムによって提示される手順について詳しく説明しています。
Strassen のアルゴリズムが存在することの証明は、単純な次元カウントです (単純な次元カウントが正しい答えを与えるという証明と組み合わせて)。すべての双一次写像 のベクトル空間を考えてみましょう$C^n\times C^n \rightarrow C^n$。これは次元のベクトル空間です$n^3$(行列の乗算の場合$n=m^2$、たとえば$n=4$の$2\times 2$場合)。ランク 1 の双一次写像のセット、つまり、1 つのスカラー乗算のみを使用するアルゴリズムで計算可能なものは次元$3(n-1)+1$を持ち、最大でもランクの双一次写像のセットは(の最小値とほとんどの値の$r$次元を持ち、次のことを確認できます。これは、次の場合に正しいです。したがって、任意の双一次写像は、確率で 1 が最大でもランク$r[3(n-1)]+r$$n^3$$n,r$$r=7,n=4$$C^4\times C^4\rightarrow C^4$$7$であり、最大でも のランクの双一次写像によって常に任意の精度で近似される可能性があります$7$。