シュトラッセンのアルゴリズム
シュトラッセンのアルゴリズム(Strassen algorithm)は、行列の積を高速に計算するアルゴリズムである。通常、 N × N {\displaystyle N\times N} 行列同士の積を計算するには O ( N 3 ) {\displaystyle O(N^{3})} の時間が必要だが、このアルゴリズムを用いると、 O ( N log 2  7 ) ≈ O ( N 2.807 ) {\displaystyle O(N^{\log _{2}7})\approx O(N^{2.807})} の時間で計算できる。1969年、フォルカー・シュトラッセンが開発した。
便宜上、 N {\displaystyle N} を偶数と考えて、以下のように N 2 × N 2 {\displaystyle {\frac {N}{2}}\times {\frac {N}{2}}} 部分行列に分解する。
( C 11 C 12 C 21 C 22 ) = ( A 11 A 12 A 21 A 22 ) ( B 11 B 12 B 21 B 22 ) {\displaystyle {\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}}}