■行列の計算(その2)
シュトラッセン法は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
より,ラダーマン法はシュトラッセンの方法を改良したことにはなっていないのである.
===================================