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

シュトラッセンのアルゴリズム（Strassen algorithm）は、行列の積を高速に計算するアルゴリズムである。通常、n×n行列同士の積を計算するにはO(n³)の時間が必要だが、このアルゴリズムを用いると、<math>O(n^{\log_2 7}) \approx O(n^{2.807})</math>の時間で計算できる。1969年、フォルカー・シュトラッセン(Volker Strassen)が開発した。

便宜上、nを偶数と考えて、以下のようにn/2×n/2部分行列に分解する。

<math>

\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} </math>

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

<math>P_1 = (A_{11} + A_{22})(B_{11} + B_{22})</math>

<math>P_2 = (A_{21} + A_{22})B_{11}</math>

<math>P_3 = A_{11}(B_{12} - B_{22})</math>

<math>P_4 = A_{22}(B_{21} - B_{11})</math>

<math>P_5 = (A_{11} + A_{12})B_{22}</math>

<math>P_6 = (A_{21} - A_{11})(B_{11} + B_{12})</math>

<math>P_7 = (A_{12} - A_{22})(B_{21} + B_{22})</math>

このとき、

<math>C_{11} = P_1 + P_4 - P_5 + P_7</math>

<math>C_{12} = P_3 + P_5</math>

<math>C_{21} = P_2 + P_4</math>

<math>C_{22} = P_1 + P_3 - P_2 + P_6</math>

の関係が成り立つ。

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

脚注

テンプレート:Reflist