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

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

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

このとき、

の関係が成り立つ。

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

精度保証付き数値計算