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

シュトラッセンのアルゴリズム（Strassen algorithm）は、行列の積を高速に計算するアルゴリズムである。通常、${\displaystyle N\times N}$行列同士の積を計算するには${\displaystyle O(N^{3})}$の時間が必要だが、このアルゴリズムを用いると、${\displaystyle O(N^{\log _{2}7})\approx O(N^{2.807})}$の時間で計算できる^[1]。1969年、フォルカー・シュトラッセンが開発した^[1][2]。

便宜上、${\displaystyle N}$を偶数と考えて、以下のように${\displaystyle {\frac {N}{2}}\times {\frac {N}{2}}}$部分行列に分解する。

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

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

${\displaystyle P_{1}=(A_{11}+A_{22})(B_{11}+B_{22})}$

${\displaystyle P_{2}=(A_{21}+A_{22})B_{11}}$

${\displaystyle P_{3}=A_{11}(B_{12}-B_{22})}$

${\displaystyle P_{4}=A_{22}(B_{21}-B_{11})}$

${\displaystyle P_{5}=(A_{11}+A_{12})B_{22}}$

${\displaystyle P_{6}=(A_{21}-A_{11})(B_{11}+B_{12})}$

${\displaystyle P_{7}=(A_{12}-A_{22})(B_{21}+B_{22})}$

このとき、

${\displaystyle C_{11}=P_{1}+P_{4}-P_{5}+P_{7}}$

${\displaystyle C_{12}=P_{3}+P_{5}}$

${\displaystyle C_{21}=P_{2}+P_{4}}$

${\displaystyle C_{22}=P_{1}+P_{3}-P_{2}+P_{6}}$

の関係が成り立つ。

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