■加減法(その9)

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

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

  log27=2.80735

より,計算量は

  O(N^3)→O(N^2.8)

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

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

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

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

になる.

  log27<log323

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

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