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

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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


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

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

P_1 = (A_{11} + A_{22})(B_{11} + B_{22})
P_2 = (A_{21} + A_{22})B_{11}
P_3 = A_{11}(B_{12} - B_{22})
P_4 = A_{22}(B_{21} - B_{11})
P_5 = (A_{11} + A_{12})B_{22}
P_6 = (A_{21} - A_{11})(B_{11} + B_{12})
P_7 = (A_{12} - A_{22})(B_{21} + B_{22})

このとき、

C_{11} = P_1 + P_4 - P_5 + P_7
C_{12} = P_3 + P_5
C_{21} = P_2 + P_4
C_{22} = P_1 + P_3 - P_2 + P_6

の関係が成り立つ。

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

脚注[編集]

[ヘルプ]
  1. ^ a b 奥村晴彦 『C言語による最新アルゴリズム事典』 技術評論社1991年、51頁。ISBN 4-87408-414-1
  2. ^ Strassen, Volker, Gaussian Elimination is not Optimal, Numer. Math. 13, p. 354-356, 1969