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

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

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

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

このとき、

の関係が成り立つ。

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

 脚注 

関連文献
 Ushiro, Y. (1998). An extension of Strassen's algorithm on matrix multiplication, Hitachi, Ltd. General Purpose Computer Division.
 Don Coppersmith and Shmuel Winograd: "Matrix multiplication via arithmetic progressions", J. Symbolic Computation, Vol.9 No.3 (1990), pp.251-280. # 漸近的な多項式オーダーの次数ωは2.375477未満。
 Virginia Vassilevska Williams: "Multiplying matrices faster than Coppersmith-Winograd", Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing (2012), pp. 887-898.
 Roser Homs, Joachim Jelisiejew, Mateusz Michałek and Tim Seynnaeve: "Bounds on complexity of matrix multiplication away from Coppersmith–Winograd tensors", Journal of Pure and Applied Algebra, Vol. 226, No. 12, (Dec. 2022), p.107142.
 Davis Blalock and John Guttag: "Multiplying Matrices Without Multiplying", https://doi.org/10.48550/arXiv.2106.10860 . #近似計算法
 加算も乗算も使わない行列積の100倍高速な近似計算手法(Maddness)を自分で再実装して検証する！！！(2023年5月13日) #近似計算法

解説記事
 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.

精度保証付き数値計算



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