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

シュトラッセンのアルゴリズム（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}}$部分行列に分解する。

${\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}}$

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

$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回ですむようになり、計算時間が削減される。部分行列への分割を再帰的に行うことにより、さらに計算時間を削減することができる。

その後、多くの研究者がNの指数2.807を下げる研究を進めた（ただし小さい指数は巨大なNに対してのものになる）。

指数　　　  : 発表年　:著者

2.81  : 1969  : Strassen

2.79  : 1979  : Pan

2.78  : 1979  : Bini, Capovani, Romani and Lotti

2.55  : 1981  : Schōnhage

2.53  : 1981  : Pan

2.52  : 1982  : Romani

2.50  : 1982  : Coppersmith and Winograd

2.48  : 1986  : Strassen

2.376  : 1987  : Coppersmith and Winograd

2.374  : 2010  : Stothers

2.3729  : 2012  : Vassilevska Williams

2.3728639  : 2014  : Le Gall

関連文献

• 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日) #近似計算法
• Jerzy S. Respondek: "Fast Matrix Multiplication with Applications", Springer, ISBN 978-3-031-76929-0 (2025).

解説記事

• 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.
• 京都大学大学院 情報学研究科通信情報システム専攻 François Le Gall 特定准教授インタビュー －量子計算の考え方を用いて世界最速の“行列のかけ算”を実現－(文部科学省科学技術・学術政策研究所 (NISTEP)), STI Horizon, Vol.4, No.1 (2018年2月26日)

精度保証付き数値計算

• 荻田武史, 大石進一, 後保範「Strassen のアルゴリズムによる行列乗算の高速精度保証 (微分方程式の数値解法と線形計算)」『数理解析研究所講究録』第1320巻、京都大学数理解析研究所、2003年5月、151-161頁、CRID 1050282677273376512、hdl:2433/43088、ISSN 1880-2818。 
• 森山敦史, 荻田武史, 後保範, 大石進一「拡張Strassen法による連立一次方程式の精度保証 (数値解析と新しい情報技術)」『数理解析研究所講究録』第1362巻、京都大学数理解析研究所、2004年4月、47-55頁、CRID 1050001202108508672、hdl:2433/25277、ISSN 1880-2818。