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

ウィキペディア

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/29 03:54 UTC 版)

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