ストラッセンアルゴリズム

Recursive algorithm for matrix multiplication

線形代数において、フォルカー・シュトラッセンにちなんで名付けられたシュトラッセンアルゴリズムは、行列乗算アルゴリズムである。このアルゴリズムは、大規模な行列に対しては標準的な行列乗算アルゴリズムよりも高速で、漸近的計算量（に対して）も優れているが、小規模な行列に対しては、単純なアルゴリズムの方が優れている場合が多い。シュトラッセンアルゴリズムは、極めて大規模な行列に対しては既知の最速アルゴリズムよりも遅いが、このような銀河的アルゴリズムは実用的なサイズの行列に対しては非常に遅いため、実際には役に立たない。小規模な行列に対しては、さらに高速なアルゴリズムが存在している。 ${\displaystyle O(n^{\log _{2}7})}$ ${\displaystyle O(n^{3})}$

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

歴史

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

アルゴリズム

左の列は、2x2行列乗算の結果を求めるために必要な計算を視覚化しています。単純な行列乗算では、左の列の「1」ごとに1回の乗算が必要です。他の列（M1～M7）はそれぞれ、ストラッセンアルゴリズムにおける7回の乗算のうち1回分を表します。列M1～M7の合計は、左の行列乗算全体と同じ結果になります。

環上の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個になります。そこで、これらの行と列が削除され、本来求めていた（より小さな）行列が得られます。 ${\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]

${\displaystyle {\begin{aligned}A_{22}&=A_{12}-A_{21}+A_{22};\\B_{22}&=B_{12}-B_{21}+B_{22},\end{aligned}}}$

${\displaystyle {\begin{aligned}t_{1}&=A_{21}+A_{22};\\t_{2}&=A_{22}-A_{12};\\t_{3}&=A_{22}-A_{11};\\t_{4}&=B_{22}-B_{11};\\t_{5}&=B_{21}+B_{22};\\t_{6}&=B_{22}-B_{12},\end{aligned}}}$

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

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

${\displaystyle {\begin{aligned}C_{12}&=C_{12}-C_{22};\\C_{21}&=C_{22}-C_{21},\end{aligned}}}$

漸近的複雑性

上記のアルゴリズムの概要は、行列のサブブロックに対する行列-行列乗算を、従来の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]また、このアルゴリズムでは、単純なアルゴリズムに比べて大幅に多くのメモリが必要です。両方の初期行列の次元は、最大で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})}$

ストラッセンアルゴリズムは、サブブロックの乗算を7回ではなく8回行う「単純な」行列乗算方法と比較する必要があります。これにより、標準的なアプローチから予想される複雑さが生じます。これら2つのアルゴリズムを比較すると、漸近的にストラッセンアルゴリズムの方が高速であることがわかります。行列のサイズが存在するため、より大きな行列は、ストラッセンアルゴリズムの方が「従来の」方法よりも効率的に乗算されます。しかし、この漸近的な記述は、ストラッセンアルゴリズムが小さな行列であっても常に高速であることを意味するわけではなく、実際にはそうではありません。小さな行列の場合、行列ブロックの追加にかかるコストが乗算回数の節約を上回ります。上記の分析では考慮されていない他の要因もあります。例えば、今日のハードウェアでは、メモリからプロセッサにデータをロードするコストと、実際にそのデータに対して演算を実行するコストの差があります。このような考慮の結果、ストラッセン法は通常「大きな」行列にのみ使用されます。この効果は、コッパースミスとウィノグラッドによるもののような代替アルゴリズムではさらに顕著です。漸近的にはより高速ですが、交差点が非常に大きいため、このアルゴリズムは実際に遭遇する行列にはあまり使用されません。 ${\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}$

	標準アルゴリズム				ストラッセンアルゴリズム
${\displaystyle i}$	${\displaystyle f_{i}(\mathbf {a} )}$	${\displaystyle g_{i}(\mathbf {b} )}$	${\displaystyle w_{i}}$		${\displaystyle f_{i}(\mathbf {a} )}$	${\displaystyle g_{i}(\mathbf {b} )}$	${\displaystyle w_{i}}$
1	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}1&0\\0&1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}1&0\\0&1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}1&0\\0&1\end{bmatrix}}}$
2	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}0&0\\1&1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\1&-1\end{bmatrix}}}$
3	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&1\\0&-1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&1\\0&1\end{bmatrix}}}$
4	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}-1&0\\1&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}1&0\\1&0\end{bmatrix}}}$
5	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}1&1\\0&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}-1&1\\0&0\end{bmatrix}}}$
6	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}-1&0\\1&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}1&1\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}}$
7	${\displaystyle {\begin{bmatrix}0&0\\1&0\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&1\\0&0\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}}$		${\displaystyle {\begin{bmatrix}0&1\\0&-1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\1&1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}1&0\\0&0\end{bmatrix}}}$
8	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {a} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}:\mathbf {b} }$	${\displaystyle {\begin{bmatrix}0&0\\0&1\end{bmatrix}}}$
	${\displaystyle \mathbf {a} \mathbf {b} =\sum _{i=1}^{8}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}}$				${\displaystyle \mathbf {a} \mathbf {b} =\sum _{i=1}^{7}f_{i}(\mathbf {a} )g_{i}(\mathbf {b} )w_{i}}$

行列の乗算に必要な基本乗算の総数は、階数、すなわち、またはより具体的には、定数が既知であるため に漸近的に拘束されることがわかります。階数の便利な特性の 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 7^{n}}$ ${\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アルゴリズムを使用する必要はなく、また望ましいものでもありません。従来の行列乗算と比較して、このアルゴリズムは加算/減算においてかなりの負荷を追加します。そのため、あるサイズ以下では、従来の乗算を使用する方が適切です。例えば、aはまでパディングする必要はありません。なぜなら、aは行列に分割でき、そのレベルでは従来の乗算を使用できるからです。 ${\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つ以上のブロックに再帰的に分割統治分解することを可能にする。

参考文献

1. Strassen, Volker (1969). 「ガウス消去法は最適ではない」. Numer. Math . 13 (4): 354– 356. doi :10.1007/BF02165411. S2CID  121656251.
2. Skiena, Steven S. (1998)、「§8.2.3 行列乗算」、アルゴリズム設計マニュアル、ベルリン、ニューヨーク：Springer-Verlag、ISBN 978-0-387-94860-7。
3. D'Alberto, Paolo; Nicolau, Alexandru (2005). 再帰を用いたATLASのパフォーマンス向上(PDF) . 第6回高性能コンピューティング国際シンポジウム.
4. Huang, Jianyu; Smith, Tyler M.; Henry, Greg M.; van de Geijn, Robert A. (2016年11月13日). Strassenのアルゴリズムのリローデッド. SC16: 高性能コンピューティング、ネットワーキング、ストレージ、分析に関する国際会議. IEEE Press. pp.  690– 701. doi :10.1109/SC.2016.58. ISBN 9781467388153. 2022年11月1日閲覧。
5. Winograd, S. (1971年10月). 「2×2行列の乗算について」 .線形代数とその応用. 4 (4): 381– 388. doi :10.1016/0024-3795(71)90009-7.
6. クヌース（1997年）、500ページ。
7. Karstadt, Elaye; Schwartz, Oded (2017-07-24). 「行列乗算、少しだけ高速化」.第29回ACMアルゴリズムとアーキテクチャにおける並列処理シンポジウム議事録. ACM. pp.  101– 110. doi :10.1145/3087556.3087579. ISBN 978-1-4503-4593-4。
8. Schwartz, Oded; Vaknin, Noa (2023-12-31). 「ペブリングゲームと高性能行列乗算のための代替基底」 . SIAM Journal on Scientific Computing . 45 (6): C277 – C303 . Bibcode :2023SJSC...45C.277S. doi :10.1137/22M1502719. ISSN  1064-8275.
9. Webb, Miller (1975). 「計算複雑性と数値安定性」SIAM J. Comput . 4 (2): 97– 107. doi :10.1137/0204009.
10. ブルギッサー;クラウゼン。ショクロラヒ (1997)。代数的複雑性理論。スプリンガー・フェルラーク。ISBN 3-540-60582-7。
11. Frigo, M.; Leiserson, CE ; Prokop, H. ; Ramachandran, S. (1999). キャッシュ忘却アルゴリズム(PDF) . Proc. IEEE Symp. on Foundations of Computer Science (FOCS). pp.  285– 297.
12. Higham, Nicholas J. (1990). 「レベル3 BLASにおける高速行列乗算の活用」(PDF) . ACM Transactions on Mathematical Software . 16 (4): 352– 368. doi :10.1145/98267.98290. hdl : 1813/6900 . S2CID  5715053.

• Thomas H. Cormen 、 Charles E. Leiserson、Ronald L. Rivest、Clifford Stein著『アルゴリズム入門第2版』MIT Press and McGraw-Hill、2001年。ISBN 0-262-03293-7第28章：セクション28.2：行列乗算のためのストラッセンのアルゴリズム、735～741ページ。
• ドナルド・クヌース（1997年）『コンピュータプログラミングの技法 半数値アルゴリズム』第2巻（第3版）Addison-Wesley社、ISBN 0-201-89684-2。

外部リンク

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Strassen_algorithm&oldid=1321323895"