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

シュトラッセンのアルゴリズム（Strassen algorithm）は、行列の積を高速に計算するアルゴリズムである。通常、<math>N \\times N</math>行列同士の積を計算するには<math>O(N^3)</math>の時間が必要だが、このアルゴリズムを用いると、<math>O(N^) \\approx O(N^)</math>の時間で計算できる。1969年、フォルカー・シュトラッセン()が開発した。便宜上、<math>N</math>を偶数と考えて、以下のように<math>\\frac \\times \\frac</math>部分行列に分解する。:<math>\\beginC_ & C_ \\\\C_ & C_ \\\\\\end=\\beginA_ & A_ \\\\A_ & A_ \\\\\\end\\beginB_ & B_ \\\\B_ & B_ \\\\\\end</math>そして、以下の七つの行列をつくる。:<math>P_1 = (A_ + A_)(B_ + B_)</math>:<math>P_2 = (A_ + A_)B_</math>:<math>P_3 = A_(B_ - B_)</math>:<math>P_4 = A_(B_ - B_)</math>:<math>P_5 = (A_ + A_)B_</math>:<math>P_6 = (A_ - A_)(B_ + B_)</math>:<math>P_7 = (A_ - A_)(B_ + B_)</math>このとき、:<math>C_ = P_1 + P_4 - P_5 + P_7</math>:<math>C_ = P_3 + P_5</math>:<math>C_ = P_2 + P_4</math>:<math>C_ = P_1 + P_3 - P_2 + P_6</math>の関係が成り立つ。この関係を利用して計算すると、部分行列同士の乗算が、通常の方法では8回必要なのに、この方法では7回ですむようになり、計算時間が削減される。部分行列への分割を再帰的に行うことにより、さらに計算時間を削減することができる。