行列の掛け算と逆行列にて最も少ない計算量は?

質問

宜しくお願い致します。
行列の計算の評価を探しています。
n×n実行列A,Bの掛け算ABと逆行列A^-1を計算するのに一番少ない計算法はどのくらいで評価できるのでしょうか?

Time(ABの計算)=O(??),
Time(A^-1の計算)=O(??)

よろしければそのサイトもご紹介頂けましたら有難いです。

回答No.2

Tacosan

ちょろっと検索して出てきた現状:
http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

回答No.1

中村 拓男（@tknakamuri）

ABはシュトラッセンの方法がn^2.8
だけど、手間がかかりすぎて使われて
いません(係数が大きい)。単純に定義通り掛けるだけの
方法は０(n^3)

逆行列は私の知る限りLU分解が最速(係数が小さい)。
Ｏ(n^3)

お礼

有難うございます。

シュトラッセンの方法とLU分解を使うと,AとBを掛けて,ABの逆行列を求める計算量は
Time((AB)^-1)=O(n^2.8)+O(n^3)=O(n^3)
とO(n^3)で評価できるのですね。

補足

すいません。もし,
A,Bの成分が高々ln(k)ビット長なら,
Time(AB)とTime(A^-1)は何で評価できるのでしょうか?

Time(AB)=O(n^2ln(k))
とTime(A^-1)=O(n^2ln(k))
ですか?