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

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

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

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

No.2 回答者： Tacosan 回答日時： 2014/09/12 13:32

ちょろっと検索して出てきた現状:

http://en.wikipedia.org/wiki/Computational_compl …

No.1 回答者： tknakamuri 回答日時： 2014/09/12 09:52

ABはシュトラッセンの方法がn^2.8

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

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

この回答への補足

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

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

補足日時：2014/09/13 05:40

この回答へのお礼

有難うございます。

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

お礼日時：2014/09/13 05:34