大きな行列の逆行列を高速に求めるアルゴリズムがあれば教えて下さい。


現在作成中のプログラムで、3万行×3万列の行列の逆行列を求める必要があります。試しにGauss-Jordan法で解いてみたら17時間弱かかり、実用的な時間ではありませんでした(出来れば数分~10分程度で解きたいです)。

そこで、正確な逆行列ではなくその近似解でいいので、何とか高速に解けないものかと考えています。

Sherman-Morrison法というのは見つけましたが(http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1505-16.pdf)、他に良いアルゴリズムがあれば教えて下さい。
ちなみに、行列自体は密行列です。

回答はURL必須とさせて貰います。解説等がのっているページを書いてもらえればありがたいです。
URLはウェブサイト・論文・書籍なんでもかまいませんが、日本語の情報に限定させてもらいます。

回答の条件
  • URL必須
  • 1人5回まで
  • 13歳以上
  • 登録:2012/01/30 21:24:41
  • 終了:2012/02/05 10:26:33

ベストアンサー

id:Baku7770 No.1

Baku7770回答回数2831ベストアンサー獲得回数1812012/02/02 11:40:26

ポイント100pt

 AISM法というのがあります。Sherman-Morrison法にこだわるなら、それにシュールコンプリトメントを施したものです。

id:Gasyou

回答有難う御座います。
Sherman-Morrison法にこだわる訳ではないので、性能とか実装の容易さとかを考えてどちらのアルゴリズムにするか決めたいと思います。

他の方の回答も参考にしたいので、質問終了はもう少し後にしようと考えています。

2012/02/02 20:31:25
  • id:ita
    特定のbに対して Mx=b を解くだけであれば逆行列を
    計算せずにxを求める手法がいろいろありますが、どうなんでしょうか。
    BiCGSTABとかいろいろ。
  • id:Gasyou
    それは連立方程式を解く場合の話ですよね?
    私がやりたいのは、とある機械学習アルゴリズムの実装で、その一部で大きな行列の逆行列が必要になる状況です。
    ですので、多少精度が落ちてもいいから逆行列の近似が得られないかと考えた次第です。
  • id:TAK_TAK
    行列は疎でしょうか?
    密でしょうか?
  • id:Gasyou
    密な行列です。
  • id:Beirii
    実行環境に制約はあるのでしょうか。
    どのような実行環境において17時間弱掛かったのでしょうか。
  • id:Gasyou
    「普通の(デュアルCPUとかクラスタとかではない)PCで動く」というのが制約条件になります。
    現在のハードウェアはCore i7 940とメモリ12GBですが、M/Bの仕様上メモリの最大搭載量は24GBですので、その範囲内で動くと嬉しいです。
    (参考までに、3万×3万の行列をC++言語のfloat型の配列に格納すると、行列一個で約4GBになります。)
    あと、OSはWindows 7 Home Premium x64版で、コンパイラはVisual C++ 2008、言語はC++です。
    この環境で開発・実行して17時間かかりました。
    (SSE未使用でシングルスレッドのアプリですので、後一桁位は高速化の余地がありますが、はっきり言って焼け石に水レベルだと思っています。)

    # CPUではなくGPUで高速に動くアルゴリズムがあればそれでもOKですが、メモリの容量的に多分厳しいんじゃないかと考えています。
  • id:Gasyou
    上で書き忘れていましたが、逆行列の計算中にスワップは起きていません。
    (そもそもページファイルを作っていないので、原理上起きないはずです。)

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません