大きな行列の逆行列を高速に求めるアルゴリズムがあれば教えて下さい。
現在作成中のプログラムで、3万行×3万列の行列の逆行列を求める必要があります。試しにGauss-Jordan法で解いてみたら17時間弱かかり、実用的な時間ではありませんでした（出来れば数分～10分程度で解きたいです）。
そこで、正確な逆行列ではなくその近似解でいいので、何とか高速に解けないものかと考えています。
Sherman-Morrison法というのは見つけましたが（http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1505-16.pdf）、他に良いアルゴリズムがあれば教えて下さい。
ちなみに、行列自体は密行列です。
回答はURL必須とさせて貰います。解説等がのっているページを書いてもらえればありがたいです。
URLはウェブサイト・論文・書籍なんでもかまいませんが、日本語の情報に限定させてもらいます。
※ 有料アンケート・ポイント付き質問機能は2023年2月28日に終了しました。
ログインして回答する
ベストアンサー
-
Baku7770
満足100pt
AISM法というのがあります。Sherman-Morrison法にこだわるなら、それにシュールコンプリトメントを施したものです。
-
その他の回答
この質問へのコメント
質問の情報
- 登録日時
- 2012-01-30 21:24:41
- 終了日時
- 2012-02-05 10:26:33
- 回答条件
- 回答にURL必須 1人5回まで
この質問のカテゴリ
この質問に含まれるキーワード
人気の質問
-
この英文どうなってますか？ The boy seemed to be waiting for his mother to come.（その少年は母親が来…
匿名質問者
3
1
-
不定詞の形容詞的用法らしいんですけど、副詞的用法と書いたら✖️ですか？ I want to buy a book to read …匿名質問者11
-
日向陽葵という○V女優が好きなのですが似ている○V女優はいますか匿名質問者
-
共通テストで使われるプログラミング言語は共通テスト特有の言語と聞いたのですが、受験勉強で身につけたプ…匿名質問者21
-
内定してほしいポケモンはいますか？匿名質問者
計算せずにxを求める手法がいろいろありますが、どうなんでしょうか。
BiCGSTABとかいろいろ。
私がやりたいのは、とある機械学習アルゴリズムの実装で、その一部で大きな行列の逆行列が必要になる状況です。
ですので、多少精度が落ちてもいいから逆行列の近似が得られないかと考えた次第です。
密でしょうか？
どのような実行環境において17時間弱掛かったのでしょうか。
現在のハードウェアは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ですが、メモリの容量的に多分厳しいんじゃないかと考えています。
（そもそもページファイルを作っていないので、原理上起きないはずです。）