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

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

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

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

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

このとき、

の関係が成り立つ。

この関係を利用して計算すると、部分行列同士の乗算が、通常の方法では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