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

シュトラッセンのアルゴリズム（Strassen algorithm）は、行列の積を高速に計算するアルゴリズムである。通常、[math]N \times N[/math]行列同士の積を計算するには[math]O(N^3)[/math]の時間が必要だが、このアルゴリズムを用いると、[math]O(N^{\log_2 7}) \approx O(N^{2.807})[/math]の時間で計算できる。1969年、フォルカー・シュトラッセンが開発した。

便宜上、[math]N[/math]を偶数と考えて、以下のように[math]\frac{N}{2} \times \frac{N}{2}[/math]部分行列に分解する。

[math] \begin{pmatrix} C_{11} & C_{12} \\ C_{21} & C_{22} \\ \end{pmatrix} = \begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \\ \end{pmatrix} \begin{pmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \\ \end{pmatrix} [/math]

そして、以下の七つの行列をつくる。

[math]P_1 = (A_{11} + A_{22})(B_{11} + B_{22})[/math]

[math]P_2 = (A_{21} + A_{22})B_{11}[/math]

[math]P_3 = A_{11}(B_{12} - B_{22})[/math]

[math]P_4 = A_{22}(B_{21} - B_{11})[/math]

[math]P_5 = (A_{11} + A_{12})B_{22}[/math]

[math]P_6 = (A_{21} - A_{11})(B_{11} + B_{12})[/math]

[math]P_7 = (A_{12} - A_{22})(B_{21} + B_{22})[/math]

このとき、

[math]C_{11} = P_1 + P_4 - P_5 + P_7[/math]

[math]C_{12} = P_3 + P_5[/math]

[math]C_{21} = P_2 + P_4[/math]

[math]C_{22} = P_1 + P_3 - P_2 + P_6[/math]

の関係が成り立つ。

この関係を利用して計算すると、部分行列同士の乗算が、通常の方法では8回必要なのに、この方法では7回ですむようになり、計算時間が削減される。部分行列への分割を再帰的に行うことにより、さらに計算時間を削減することができる。