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

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