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

シュトラッセンのアルゴリズム（Strassen algorithm）は、行列の積を高速に計算するアルゴリズムである。通常、行列同士の積を計算するにはの時間が必要だが、このアルゴリズムを用いると、の時間で計算できる。1969年、フォルカー・シュトラッセンが開発した。

便宜上、を偶数と考えて、以下のように部分行列に分解する。

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

このとき、

の関係が成り立つ。

この関係を利用して計算すると、部分行列同士の乗算が、通常の方法では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.

精度保証付き数値計算
 荻田武史, 大石進一, & 後保範. (2003). Strassen のアルゴリズムによる行列乗算の高速精度保証 (微分方程式の数値解法と線形計算). 京都大学数理解析研究所講究録.
 森山敦史, 荻田武史, 後保範, & 大石進一. (2004). 拡張 Strassen 法による連立一次方程式の精度保証 (数値解析と新しい情報技術). 京都大学数理解析研究所講究録.

数値線形代数
アルゴリズム
数学に関する記事
数学のエポニム