シュトラッセンアルゴリズム

線型代数において、フォルカー・シュトラッセンにちなんで名付けられたシュトラッセンアルゴリズムは、行列乗算アルゴリズムである。このアルゴリズムは、大規模な行列に対しては標準的な行列乗算アルゴリズムよりも高速で、漸近的複雑度も優れているが、小規模な行列に対しては単純なアルゴリズムの方が優れていることが多い。シュトラッセンアルゴリズムは、極めて大規模な行列に対しては既知の最速アルゴリズムよりも低速であるが、このような銀河的なアルゴリズムは実用的なサイズの行列に対しては非常に低速であるため、実際には役に立たない。小規模な行列に対しては、さらに高速なアルゴリズムが存在している。

シュトラッセンのアルゴリズムは、加算/乗算などの任意の環に対して機能しますが、最小加算やブール代数などのすべての半環に対して機能するわけではありません。これらの半環では、ナイーブなアルゴリズムが依然として機能し、いわゆる組み合わせ行列乗算が機能します。

フォルカー・シュトラッセンが1969年に初めてこのアルゴリズムを発表し、一般的な行列乗算アルゴリズムが最適ではないことを証明しました。^[1]シュトラッセンアルゴリズムの発表により、行列乗算に関する研究がさらに進み、漸近的に下限が下がり、計算の上限が改善されました。 ${\displaystyle n^{3}}$

、をリング上の2 つの正方行列、たとえば要素が整数または実数である行列とします。行列の乗算の目的は、行列の積を計算することです。以下のアルゴリズムの説明では、これらすべての行列のサイズが 2 の累乗 (つまり) であると仮定していますが、これは概念的に必要なだけです。行列、が 型でない場合は、「欠落している」行と列をゼロで埋めて、サイズが 2 の累乗の行列を取得できますが、アルゴリズムの実際の実装では実際にはこれを行いません。 ${\displaystyle A}$${\displaystyle B}$ ${\displaystyle {\mathcal {R}}}$${\displaystyle C=AB}$${\displaystyle A,\,B,\,C\in \operatorname {Matr} _{2^{n}\times 2^{n}}({\mathcal {R}})}$${\displaystyle A}$${\displaystyle B}$${\displaystyle 2^{n}\times 2^{n}}$

ストラッセンアルゴリズムは、、およびを等しいサイズのブロック行列に分割する。${\displaystyle A}$${\displaystyle B}$${\displaystyle C}$

${\displaystyle A={\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}},\quad B={\begin{bmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{bmatrix}},\quad C={\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}},\quad }$

とします。単純なアルゴリズムは次のようになります。 ${\displaystyle A_{ij},B_{ij},C_{ij}\in \operatorname {Mat} _{2^{n-1}\times 2^{n-1}}({\mathcal {R} })}$

${\displaystyle {\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}}={\begin{bmatrix}A_{11}{\color {red}\times }B_{11}+A_{12}{\color {red}\times }B_{21}\quad &A_{11}{\color {red}\times }B_{12}+A_{12}{\color {red}\times }B_{22}\\A_{21}{\color {red}\times }B_{11}+A_{22}{\color {red}\times }B_{21}\quad &A_{21}{\color {red}\times }B_{12}+A_{22}{\color {red}\times }B_{22}\end{bmatrix}}.}$

この構成では乗算の回数は減りません。行列を計算するには、依然として行列ブロックの乗算が 8 回必要であり、これは標準の行列乗算を使用する場合に必要な乗算回数と同じです。 ${\displaystyle C_{ij}}$

Strassen アルゴリズムは代わりに新しい値を定義します。

${\displaystyle {\begin{aligned}M_{1}&=(A_{11}+A_{22}){\color {red}\times }(B_{11}+B_{22});\\M_{2}&=(A_{21}+A_{22}){\color {red}\times }B_{11};\\M_{3}&=A_{11}{\color {red}\times }(B_{12}-B_{22});\\M_{4}&=A_{22}{\color {red}\times }(B_{21}-B_{11});\\M_{5}&=(A_{11}+A_{12}){\color {red}\times }B_{22};\\M_{6}&=(A_{21}-A_{11}){\color {red}\times }(B_{11}+B_{12});\\M_{7}&=(A_{12}-A_{22}){\color {red}\times }(B_{21}+B_{22}),\\\end{aligned}}}$

8 回の乗算ではなく7 回の乗算 ( ごとに 1 回) のみを使用します。を で表すことができます。 ${\displaystyle M_{k}}$${\displaystyle C_{ij}}$${\displaystyle M_{k}}$

${\displaystyle {\begin{bmatrix}C_{11}&C_{12}\\C_{21}&C_{22}\end{bmatrix}}={\begin{bmatrix}M_{1}+M_{4}-M_{5}+M_{7}\quad &M_{3}+M_{5}\\M_{2}+M_{4}\quad &M_{1}-M_{2}+M_{3}+M_{6}\end{bmatrix}}.}$

この除算プロセスは、部分行列が数値（環 の要素）に縮退するまで再帰的に繰り返されます。前述のように、元の行列のサイズが 2 の累乗でなかった場合、結果の積は や と同様に 0 行と 0 列になります。この時点でこれらが削除され、実際に必要な（より小さい）行列が得られます。 ${\displaystyle {\mathcal {R}}}$${\displaystyle A}$${\displaystyle B}$${\displaystyle C}$

ストラッセンのアルゴリズムの実際の実装では、十分に小さいサブマトリックスに対しては標準的なマトリックス乗算法に切り替えられ、それらのアルゴリズムの方が効率的です。ストラッセンのアルゴリズムの方が効率的である特定の交差点は、特定の実装とハードウェアによって異なります。以前の著者は、最適化された実装では、幅が 32 から 128 のマトリックスに対してストラッセンのアルゴリズムの方が高速であると推定していました。^[2]しかし、この交差点は近年増加していることが観察されており、2010 年の調査では、ストラッセンのアルゴリズムの 1 ステップでさえ、マトリックス サイズが 1000 以上になるまでは、現在のアーキテクチャでは、高度に最適化された従来の乗算と比較してメリットがないことが多く、数千のマトリックス サイズでもメリットは通常、せいぜいわずか (約 10% 以下) であることがわかりました。^[3] より最近の調査 (2016 年) では、512 の小さいマトリックスに対してメリットがあり、メリットは約 20% でした。^[4]

1971年にウィノグラードが発見した次の形式を使用することで、行列の加算回数を減らすことができます。^[5]

${\displaystyle {\begin{bmatrix}a&b\\c&d\end{bmatrix}}{\begin{bmatrix}A&C\\B&D\end{bmatrix}}={\begin{bmatrix}t+b{\color {red}\times }B&w+v+(a+b-c-d){\color {red}\times }D\\w+u+d{\color {red}\times }(B+C-A-D)&w+u+v\end{bmatrix}}}$

どこ。 ${\displaystyle t=a{\color {red}\times }A,\;u=(c-a){\color {red}\times }(C-D),\;v=(c+d){\color {red}\times }(C-A),\;w=t+(c+d-a){\color {red}\times }(A+D-C)}$

これにより、行列の加算と減算の回数が18回から15回に減ります。行列の乗算の回数は7回のままで、漸近的な複雑さは同じです。^[6]

このアルゴリズムは2017年にさらに最適化され^[7]、行列乗算の回数は維持しながら、ステップあたりの行列加算の回数を12に減らし、2023年に再度最適化されました^[8]。

上記のアルゴリズムの概要は、行列のサブブロックに対して、従来の 8 回の行列間乗算ではなく、わずか 7 回の行列間乗算で済むことを示しています。一方、ブロックの加算と減算を行う必要がありますが、これは全体的な複雑さには関係ありません。サイズの行列を加算するには演算のみが必要ですが、乗算は大幅にコストがかかります (従来の加算または乗算演算)。 ${\displaystyle N/2}$${\displaystyle (N/2)^{2}}$${\displaystyle 2(N/2)^{3}}$

問題は、Strassen のアルゴリズムに必要な演算が正確にいくつあるか、また、これが、およそ(ここで) の算術演算、つまり漸近的複雑度 を要する標準的な行列乗算とどのように比較されるかということです。 ${\displaystyle 2N^{3}}$${\displaystyle N=2^{n}}$${\displaystyle \Theta (N^{3})}$

シュトラッセンアルゴリズムで必要な加算と乗算の回数は、次のように計算できます。を行列の演算回数とします。次に、シュトラッセンアルゴリズムを再帰的に適用すると、 であることがわかります。ただし、この定数は、アルゴリズムの各適用で実行される加算回数によって異なります。したがって、 、つまり、シュトラッセンアルゴリズムを使用してサイズの行列を乗算するための漸近的複雑性は です 。ただし、算術演算回数の削減には、数値安定性がいくらか低下するという代償が伴います。^[9]また、このアルゴリズムでは、単純なアルゴリズムに比べて大幅に多くのメモリが必要です。両方の初期行列の次元を 2 の次の累乗に拡張する必要があり、その結果、最大 4 倍の要素を格納することになり、7 つの補助行列にはそれぞれ、拡張された行列の要素の 4 分の 1 が含まれます。 ${\displaystyle f(n)}$${\displaystyle 2^{n}\times 2^{n}}$${\displaystyle f(n)=7f(n-1)+l4^{n}}$${\displaystyle l}$${\displaystyle f(n)=(7+o(1))^{n}}$${\displaystyle N=2^{n}}$${\displaystyle O([7+o(1)]^{n})=O(N^{\log _{2}7+o(1)})\approx O(N^{2.8074})}$

Strassen のアルゴリズムは、サブブロックの乗算を 7 回ではなく 8 回必要とする「単純な」行列乗算方法と比較する必要があります。これにより、標準的なアプローチから予想される複雑さが生じます。これら 2 つのアルゴリズムを比較すると、漸近的にStrassen のアルゴリズムの方が高速であることがわかります。行列が大きいほど、Strassen のアルゴリズムを使用した方が「従来の」方法よりも効率的に乗算されるサイズが存在します。ただし、漸近的な記述は、小さな行列でも Strassen のアルゴリズムが常に高速であることを意味するわけではなく、実際にはそうではありません。小さな行列の場合、行列ブロックの追加コストが乗算回数の節約を上回ります。上記の分析では把握されていない他の要因もあります。たとえば、今日のハードウェアでは、メモリからプロセッサにデータをロードするコストと、このデータに対して実際に操作を実行するコストの差などです。このような考慮の結果、Strassen のアルゴリズムは通常、「大きな」行列にのみ使用されます。この種の効果は、Coppersmith と Winogradによるアルゴリズムなどの代替アルゴリズムではさらに顕著です。漸近的にはより高速ですが、クロスオーバー ポイントが非常に大きいため、このアルゴリズムは、実際に遭遇する行列にはあまり使用されません。 ${\displaystyle O(8^{n})=O(N^{\log _{2}8})=O(N^{3})}$${\displaystyle N_{\text{threshold}}}$${\displaystyle N_{\text{threshold}}}$

双線型写像の階数は、行列乗算の漸近的複雑性における重要な概念である。体F上の双線型写像の階数は、次のように定義される（多少表記法の乱用であるが）。 ${\displaystyle \phi :\mathbf {A} \times \mathbf {B} \rightarrow \mathbf {C} }$

${\displaystyle R(\phi /\mathbf {F} )=\min \left\{r\left|\exists f_{i}\in \mathbf {A} ^{*},g_{i}\in \mathbf {B} ^{*},w_{i}\in \mathbf {C} ,\forall \mathbf {a} \in \mathbf {A} ,\mathbf {b} \in \mathbf {B} ,\phi (\mathbf {a} ,\mathbf {b} )=\sum _{i=1}^{r}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}\right.\right\}}$

言い換えれば、双線型写像の階数は、その最短の双線型計算の長さである。^[10] シュトラッセンのアルゴリズムの存在は、行列乗算の階数が 7 以下であることを示す。これを理解するために、このアルゴリズムを（標準アルゴリズムと並べて）そのような双線型計算として表現しよう。行列の場合、双対空間A * とB * は、スカラー二重ドット積（この場合はアダマール積のすべての要素の合計） によって誘導される体Fへの写像から構成される。${\displaystyle 2\times 2}$

行列の乗算に必要な基本乗算の総数は、階数、すなわち、またはより具体的には、定数が既知であるため に漸近的に密接に結びついていることが示されます。階数の便利な特性の 1 つは、階数がテンソル積に対して乗法未満であることであり、これにより、任意の に対して行列の乗算が基本乗算のみで実行できることを示すことができます。(この行列の乗算マップの 倍のテンソル積は、それ自身と、つまり テンソル乗数であり、示されているアルゴリズムの再帰ステップによって実現されます。) ${\displaystyle L}$${\displaystyle R}$${\displaystyle L=\Theta (R)}$${\displaystyle R/2\leq L\leq R}$${\displaystyle 2^{n}\times 2^{n}\times 2^{n}}$${\displaystyle 7n}$${\displaystyle n}$${\displaystyle n}$${\displaystyle 2\times 2\times 2}$${\displaystyle n}$

ストラッセンのアルゴリズムはキャッシュを無視します。そのキャッシュ動作アルゴリズムの分析により、次のような結果が出ています。

${\displaystyle \Theta \left(1+{\frac {n^{2}}{b}}+{\frac {n^{\log _{2}7}}{b{\sqrt {M}}}}\right)}$

理想的なキャッシュサイズ（つまり行の長さ）を仮定すると、実行中にキャッシュミスが発生する確率は となる。^{[11] : 13}${\displaystyle M}$${\displaystyle M/b}$${\displaystyle b}$

上記の説明では、行列は正方行列であり、サイズは 2 の累乗であり、必要に応じてパディングを使用する必要があると述べています。この制限により、スカラー乗算の限界に達するまで、行列を再帰的に半分に分割できます。この制限により、説明と複雑さの分析が簡素化されますが、実際には必要ありません。^[12] 実際、説明されているように行列にパディングを行うと、計算時間が増加し、そもそもこの方法を使用することで得られたかなりわずかな時間節約が簡単に失われる可能性があります。

適切な実装では、次の点が守られます。

• スカラーの限界まで Strassen アルゴリズムを使用する必要はなく、また望ましくもありません。従来の行列乗算と比較すると、このアルゴリズムは加算/減算にかなりの作業負荷を追加します。したがって、特定のサイズ以下では、従来の乗算を使用する方が適切です。したがって、たとえば、は にパディングする必要はありません。これは、 を行列に細分化して、そのレベルで従来の乗算を使用できるためです。${\displaystyle O(n^{2})}$${\displaystyle 1600\times 1600}$${\displaystyle 2048\times 2048}$${\displaystyle 25\times 25}$
• 実際、この方法は任意の次元の正方行列に適用できます。^[3]次元が偶数の場合、前述のように半分に分割されます。次元が奇数の場合、最初に 1 行 1 列のゼロ パディングが適用されます。このようなパディングはオンザフライで遅延適用することができ、結果が形成されるときに余分な行と列は破棄されます。たとえば、行列が であるとします。これらは、左上部分が、右下部分が となるように分割できます。操作で必要な場合は常に、 の次元に最初にゼロ パディングが行われます。たとえば、積は出力の下の行でのみ使用されるため、は行の高さだけでよいことに注意してください。したがって、それを生成するために使用される左の因子は行の高さだけで済みます。したがって、その合計を行にパディングする必要はなく、と一致するように列にパディングするだけで済みます。${\displaystyle 199\times 199}$${\displaystyle 100\times 100}$${\displaystyle 99\times 99}$${\displaystyle 99}$${\displaystyle 100}$${\displaystyle M_{2}}$${\displaystyle 99}$${\displaystyle A_{21}+A_{22}}$${\displaystyle 99}$${\displaystyle 100}$${\displaystyle A_{22}}$${\displaystyle 100}$${\displaystyle A_{21}}$

さらに、行列が正方行列である必要はありません。非正方行列は、同じ方法を使用して半分に分割することができ、より小さな非正方行列が生成されます。行列が十分に非正方である場合は 、次のような単純な方法を使用して、初期操作をより正方積に減らす価値があります。 ${\displaystyle O(n^{2})}$

• サイズの製品は、結果を形成するために配置されて20 個の個別の操作として実行できます。${\displaystyle [2N\times N]\ast [N\times 10N]}$${\displaystyle [N\times N]\ast [N\times N]}$
• サイズの積は10 個の個別の演算として実行でき、それらの合計によって結果が生成されます。${\displaystyle [N\times 10N]\ast [10N\times N]}$${\displaystyle [N\times N]\ast [N\times N]}$

これらの手法は、単純に 2 の累乗の平方にパディングするのに比べて実装をより複雑にします。ただし、従来の乗算ではなく Strassen の実装に取り​​組む人は、実装の単純さよりも計算効率を優先すると考えるのが妥当です。

実際には、シュトラッセンのアルゴリズムは、 ほど小さい行列や、まったく正方でない行列に対しても、従来の乗算よりも優れたパフォーマンスを達成するように実装することができ、高性能な従来の乗算にすでに必要なバッファを超える作業領域を必要としません。^[4]${\displaystyle 500\times 500}$

• 数学演算の計算複雑性
• ガウス・ジョルダン消去法
• 行列乗算の計算複雑度
• Zオーダー曲線
• カラツバアルゴリズム、n桁の整数を時間 ではなく時間で乗算する${\displaystyle O(n^{\log _{2}3})}$${\displaystyle O(n^{2})}$
  • 同様の複素乗算アルゴリズムは、 4回の実数乗算ではなく3回の実数乗算を使用して2つの複素数を乗算します。
• Toom-Cook アルゴリズム、Karatsuba アルゴリズムの高速一般化であり、一度に 2 つ以上のブロックへの再帰分割統治分解を可能にします。

• Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズム入門、第 2 版。MIT Press および McGraw-Hill、2001 年。ISBN 0-262-03293-7 。第 28 章: セクション 28.2: 行列乗算のための Strassen アルゴリズム、pp. 735–741。 
• クヌース、ドナルド (1997)。『コンピュータプログラミングの技法、半数値アルゴリズム』第 2 巻 (第 3 版)。Addison- Wesley。ISBN 0-201-89684-2。

• ワイスタイン、エリック W.「ストラッセンの数式」。マスワールド。（高速行列反転の公式も含まれています）
• Tyler J. Earnest、Cell Broadband Engine における Strassen のアルゴリズム