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

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

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

$\left(\begin{array}{cc}{C}_{11}& C_{12}\\ C_{21}& C_{22}\end{array}\right)=\left(\begin{array}{cc}{A}_{11}& A_{12}\\ A_{21}& A_{22}\end{array}\right)\left(\begin{array}{cc}{B}_{11}& B_{12}\\ B_{21}& B_{22}\end{array}\right)$

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

$P_1=(A_{11}+A_{22})(B_{11}+B_{22})$

$P_2=(A_{21}+A_{22})B_{11}$

$P_3=A_{11}(B_{12}-B_{22})$

$P_4=A_{22}(B_{21}-B_{11})$

$P_5=(A_{11}+A_{12})B_{22}$

$P_6=(A_{21}-A_{11})(B_{11}+B_{12})$

$P_7=(A_{12}-A_{22})(B_{21}+B_{22})$

このとき、

$C_{11}=P_1+P_4-P_5+P_7$

$C_{12}=P_3+P_5$

$C_{21}=P_2+P_4$

$C_{22}=P_1+P_3-P_2+P_6$

の関係が成り立つ。

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

関連文献

• Ushiro, Y. (1998). An extension of Strassen's algorithm on matrix multiplication, Hitachi, Ltd. General Purpose Computer Division.

解説記事

• Huang, J., Smith, T. M., Henry, G. M., & van de Geijn, R. A. (2016, November). Strassen's algorithm reloaded. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis (p. 59). IEEE Press.
• Gates, A. Q., & Kreinovich, V. (2001). Strassen's Algorithm Made (Somewhat) More Natural: A Pedagogical Remark. Bulletin of the EATCS, 73, 142-145.
• Grochow, J. A., & Moore, C. (2017). Designing Strassen's algorithm. arXiv preprint arXiv:1708.09398.
• Ikenmeyer, C., & Lysikov, V. (2017). Strassen's 2x2 matrix multiplication algorithm: A conceptual perspective. arXiv preprint arXiv:1708.08083.

精度保証付き数値計算

• テンプレート:Cite journal
• テンプレート:Cite journal