■シュトラッセン法とラダーマン法(その4)

ふたつのnxn行列の普通の掛け算ではn^3回の乗算が必要になる。

1960年代に見いだされたシュトラッセン法は2次の行列同士の積に対して,8回のかけ算を7回ですませる方法であった.

 N=2^nの場合,行列を2^n-1×2^n-1の4つのコンパートメントに分割して,それぞれに対してシュトラッセン法を適用することができる.このとき,

  log2(7)=2.80735

より,計算量は

  O(N^3)→O(N^2.807・・・)

シュトラッセン法は大きなサイズの行列には有効な方法である。

===================================

 ラダーマン法は3次の行列同士の積に対して,27回のかけ算を23回ですませる方法であった.

 N=3^nの場合,log323=2.85405より,計算量は

  O(N^3)→O(N^2.85)

になる.

  log27<log323

より,ラダーマン法はシュトラッセンの方法を改良したことにはなっていないのである.

===================================