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

シュトラッセンのアルゴリズム（Strassen algorithm）は、行列の積を高速に計算するアルゴリズムである。通常、formula_1行列同士の積を計算するにはformula_2の時間が必要だが、このアルゴリズムを用いると、formula_3の時間で計算できる。1969年、フォルカー・シュトラッセンが開発した。
便宜上、formula_4を偶数と考えて、以下のようにformula_5部分行列に分解する。
そして、以下の七つの行列をつくる。
このとき、
の関係が成り立つ。
この関係を利用して計算すると、部分行列同士の乗算が、通常の方法では8回必要なのに、この方法では7回ですむようになり、計算時間が削減される。部分行列への分割を再帰的に行うことにより、さらに計算時間を削減することができる。