行列乗算の計算複雑性

n × n行列AとBの積を計算する最も簡単な方法は、行列乗算の定義から得られる算術式を計算することです。擬似コードでは次のようになります。

入力AとB はどちらもn × n行列です 。 C をn × n行列で 初期化します 。iが 1 からnまでの場合: jが 1 からnまでの場合: kが 1 からnまでの場合: C [ i ][ j ] = C [ i ][ j ] + A [ i ] [ k ]* B [ k ][ j ] 出力C (A*B として)

このアルゴリズムには⁠$\displaystyle n^{3}}$乗算と​${\displaystyle n^{3}-n^{2}}$2つのn × n正方行列の積を計算するためのスカラーの加算。したがって、その計算複雑度は${\displaystyle O(n^{3})}$⁠ 、フィールド演算（加算と乗算）が一定時間で完了する計算モデルにおいて（実際には、これは浮動小数点数の場合に当てはまりますが、整数の場合は必ずしも当てはまりません）。

Strassen のアルゴリズムは、分割統治法によって単純な行列乗算を改善します。重要な点は、2 × 2行列の乗算は、通常の 8 回ではなく、わずか 7 回の乗算で実行できるということです (ただし、11 回の加算と減算の演算が追加されます)。つまり、入力n × n行列をブロック2 × 2行列として扱うと、2 つのn × n行列の乗算タスクは、 2 つのn /2 × n /2行列の乗算という 7 つのサブ問題に縮小できます。これを再帰的に適用すると、次のアルゴリズムが得られます。${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})}$現場作戦。

漸近的複雑性が速いアルゴリズムとは異なり、Strassen のアルゴリズムは実際に使用されています。数値安定性はナイーブなアルゴリズム^{[ 5 ]}に比べて低下しますが、 n > 100程度の場合^{[ 6 ]}は高速で、 BLAS ^{[ 7 ]}などのいくつかのライブラリに登場します。高速行列乗算アルゴリズムはコンポーネントごとの安定性を達成できませんが、ノルムごとの安定性を示すことが示されるものもあります。^{[ 8 ]}数値安定性が問題にならない有限体などの正確な領域上の大きな行列には非常に役立ちます。

Henry Cohn、Robert Kleinberg、Balázs Szegedy、Chris Umans は、有限群の部分集合の 3 つ組が三重積特性 (TPP)と呼ばれる非交差性特性を満たすことを利用して、 Strassen アルゴリズムや Coppersmith–Winograd アルゴリズムなどの手法を全く異なる群論的文脈に置きました。また、もしこれが正しければ、本質的に 2 乗算の複雑さを持つ行列乗算アルゴリズムが存在することになるという予想も示しています。これは、行列乗算の最適な指数が 2 であることを意味し、ほとんどの研究者は実際にそうであると考えています。^{[ 4 ]}そのような予想の 1 つは、アーベル群と対称群のリース積の族が、TPP の同時バージョンを持つ部分集合の 3 つ組の族を実現するというものです。^{[ 27 ] [ 28 ]}その後、Blasiak、Cohn、Church、Grochow、Naslund、Sawin、およびUmansがスライスランク法を用いて、彼らの予想のいくつかを反証しました。^{[ 29 ]}さらに、Alon、Shpilka、およびChris Umansは最近、高速行列乗算を意味するこれらの予想のいくつかが、別のもっともらしい予想であるヒマワリ予想[ ^{30 ]}と互換性がないことを示しました。これは、キャップセット問題に関連してい^ます。^{[ 29 ]}

の自明な下限が存在する${\displaystyle \omega \geq 2}$⁠ 。2 つのn × n行列を乗算するアルゴリズムは、すべての2 n ²エントリを処理する必要があるため、任意の行列乗算アルゴリズムに対して、 Ω( n ² )演算という自明な漸近的下限が存在します。したがって、${\displaystyle 2\leq \omega <2.37188}$⁠。 ⁠ かどうかは不明です。${\displaystyle \omega >2}$行列乗算の複雑さに関する最もよく知られている下限は、^実数または複素数上の有界係数算術回路の場合、 Ω( n ² log( n ))であり、これはRan Razによるものです。 ^[ 31 ^]

一般的に研究されている計算モデルの下では、正確にO ( n ^ω )回の演算を使用する行列乗算アルゴリズムは存在せず、 n ^o(1)という追加の係数が必要であることが知られています。^{[ 13 ]}

同様の手法は長方形行列の乗算にも適用されます。研究の中心となるのは${\displaystyle \omega (k)}$これは最小の${\displaystyle c}$サイズ の行列を乗算できる${\displaystyle n\times \lceil n^{k}\rceil }$サイズが の行列${\displaystyle \lceil n^{k}\rceil \times n}$と${\displaystyle O(n^{c+o(1)})}$算術演算。代数的複雑性の結果によれば、サイズの行列の乗算は${\displaystyle n\times \lceil n^{k}\rceil }$そして${\displaystyle \lceil n^{k}\rceil \times n}$サイズ の行列を乗算する場合と同じ数の算術演算が必要です${\displaystyle n\times \lceil n^{k}\rceil }$そして${\displaystyle n\times n}$そしてその大きさは${\displaystyle n\times n}$そして${\displaystyle n\times \lceil n^{k}\rceil }$、したがって、これは長方形行列の乗算の複雑さを包含する。^{[ 32 ]}これは、正方行列の乗算指数を一般化したものである。${\displaystyle \omega (1)=\omega }$。

行列乗算問題の出力はサイズであるため${\displaystyle n^{2}}$、 我々は持っています${\displaystyle \omega (k)\geq 2}$すべての値に対して${\displaystyle k}$. いくつかの値に対して証明できる場合${\displaystyle k}$0から1の間で${\displaystyle \omega (k)\leq 2}$すると、このような結果は次のことを示している。${\displaystyle \omega (k)=2}$それらの人々のために${\displaystyle k}$最大のkは、${\displaystyle \omega (k)=2}$は、通常αで表される双対行列乗算指数として知られています。α は、次のことを示すため「双対」と呼ばれます。${\displaystyle \alpha =1}$これは、${\displaystyle \omega =2}$行列乗算指数と同様に、双対行列乗算指数は数値線形代数や最適化のアルゴリズムの複雑さの中に現れることがある。^{[ 33 ]}

αに関する最初の境界は 1982 年にCoppersmithによって示され、${\displaystyle \alpha >0.17227}$[ ^{34 ]} αに関する現在の最良の^査読済み上限は${\displaystyle \alpha \geq 0.321334}$ウィリアムズ、シュー、シュー、ジョウによって与えられた。^{[ 23 ]}

1969年の論文で彼は複雑性を証明した${\displaystyle O(n^{\log _{2}7})\approx O(n^{2.807})}$行列計算に関して、ストラッセンは、行列の逆行列、行列式、ガウス消去法は、乗法定数を除いて、行列乗算と同じ計算複雑度を持つことを証明した。証明では、使用される行列乗算について、その複雑度が${\displaystyle O(n^{\omega })}$一部の人にとって${\displaystyle \omega \geq 2}$。

ストラッセンの証明の出発点は、ブロック行列乗算を用いることである。具体的には、偶数次元の行列2n × 2nは、 4 つのn × nブロック に分割できる。$${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}.}$$ この形式では、その逆は $${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}^{-1}={\begin{bmatrix}{A}^{-1}+{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1}{CA}^{-1}&-{A}^{-1}{B}({D}-{CA}^{-1}{B})^{-1}\\-({D}-{CA}^{-1}{B})^{-1}{CA}^{-1}&({D}-{CA}^{-1}{B})^{-1}\end{bmatrix}},}$$ ただし、Aと${\displaystyle {D}-{CA}^{-1}{B}}$可逆である。

したがって、 2n × 2n行列の逆行列は、 2回の逆行列計算、6回の乗算、4回の加算、またはn × n行列の加法逆行列計算によって求めることができます。ここで、n×n行列の逆行列計算、乗算、加算に必要な演算回数をそれぞれI ( n ) 、 M ( n ) 、 A ( n ) = n / 2^とすると、次の式が得られます 。$${\displaystyle I(2n)\leq 2I(n)+6M(n)+4A(n).}$$ もし${\displaystyle n=2^{k},}$この公式は再帰的に適用できる。 $${\displaystyle {\begin{aligned}I(2^{k})&\leq 2I(2^{k-1})+6M(2^{k-1})+4A(2^{k-1})\\&\leq 2^{2}I(2^{k-2})+6(M(2^{k-1})+2M(2^{k-2}))+4(A(2^{k-1})+2A(2^{k-2}))\\&\,\,\,\vdots \end{aligned}}}$$ もし${\displaystyle M(n)\leq cn^{\omega },}$そして${\displaystyle \alpha =2^{\omega }\geq 4,}$最終的には $${\displaystyle {\begin{aligned}I(2^{k})&\leq 2^{k}I(1)+6c(\alpha ^{k-1}+2\alpha ^{k-2}+\cdots +2^{k-1}\alpha ^{0})+k2^{k+1}\\&\leq 2^{k}+6c{\frac {\alpha ^{k}-2^{k}}{\alpha -2}}+k2^{k+1}\\&\leq d(2^{k})^{\omega }\end{aligned}}}$$ ある定数dに対して。

次元が2のべき乗でない行列の場合、対角成分が1でそれ以外の成分が0である行と列を追加して行列の次元を2のべき乗にすることで、同じ複雑さを実現できます。

これは、逆行列を求める必要のあるすべての部分行列が実際に可逆であるような行列について、主張されている複雑性が証明される。このように、ランダムに選択された要素を持つ行列は確率1で可逆であるため、この複雑性はほぼすべての行列について証明される。

LU分解についても同じ議論が成り立ちます。行列Aが可逆であれば、等式が成り立ちます。 $${\displaystyle {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}={\begin{bmatrix}I&0\\CA^{-1}&I\end{bmatrix}}\,{\begin{bmatrix}A&B\\0&D-CA^{-1}B\end{bmatrix}}}$$ ブロックLU分解を定義し、再帰的に適用することができます${\displaystyle A}$そして${\displaystyle D-CA^{-1}B,}$最終的に元の行列の真のLU分解を得るため。

この議論は行列式にも当てはまります。なぜなら、それはブロックLU分解から得られるからです。 $${\displaystyle \det {\begin{bmatrix}{A}&{B}\\{C}&{D}\end{bmatrix}}=\det(A)\det(D-CA^{-1}B).}$$

算術演算の回数を最小化する問題に関連して、乗算の回数を最小化する問題があります。乗算は通常、加算よりもコストのかかる演算です。${\displaystyle O(n^{\omega })}$行列乗算のアルゴリズムは、必ず${\displaystyle O(n^{\omega })}$乗算演算だが、これらのアルゴリズムは実用的ではない。素朴な方法から改善する${\displaystyle n^{3}}$教科書の掛け算、${\displaystyle 4\times 4}$行列${\displaystyle \mathbb {Z} /2\mathbb {Z} }$47回の乗算で実行できます。^{[ 36 ]}${\displaystyle 3\times 3}$可換環上の行列乗算は21 回乗算で実行できます^{[ 37 ] [ 38 ]} (非可換環の場合は 23 回^{[ 39 ]} )。必要な乗算の下限は 2 mn +2 n − m −2 (置換法を使用したn × m行列とm × n行列の乗算、${\displaystyle m\geq n\geq 3}$)、つまりn=3の場合は少なくとも19回の乗算が必要で、n=4の場合は少なくとも34回必要です。 ^{[ 40 ]} n=2の場合、最適な7回の乗算と15回の加算が最小限で済み、8回の乗算でわずか4回の加算で済みます。^{[ 41 ] [ 42 ]}