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

行列の積を高速に計算するアルゴリズム

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

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

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

このとき、

の関係が成り立つ。

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

脚注

編集
  1. ^ a b 奥村晴彦『C言語による最新アルゴリズム事典』技術評論社、1991年、51頁。ISBN 4-87408-414-1 
  2. ^ Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969

関連文献

編集
  • 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.

精度保証付き数値計算

編集