線形連立方程式を解くのに特に適した反復法は、どのアプリケーションに適していますか?

2
The Pheromone Kid 2019-04-03 10:59.

線形連立方程式は、LU分解としての直接法または反復法のいずれかで解くことができます。これらの反復法は、ガウス・ザイデル法、連続過緩和法、ヤコビ法などです。

反復法は、行列とベクトルの乗算のみを必要とするため、計算量が少なくて済みます。ただし、選択した方法が収束しない場合、反復アプローチを使用しても機能しない場合や、収束が遅い場合があります。

一方、収束と精度を気にせずに正確な解を得ることができるため、直接的なアプローチは簡単です。

では、直接法よりも反復法を好むアプリケーションは何でしょうか。

編集:コメントに記載されているように、反復法は、解の精度がそれほど重要ではない大規模な連立方程式に使用できます。ただし、これらの条件はどのアプリケーションにあるのでしょうか。

2 answers

0
Vítězslav Štembera 2019-04-14 15:35.

線形方程式の大規模なスパースシステム(100万以上の未知数があるとしましょう)を考えてみましょう。

一般に、直接法は反復法よりも多くのメモリを必要とします。反復法は完全に並列化できますが、直接法は部分的にしか並列化できません。また、反復法を使用すると、発散や遅い収束の問題が常に発生する可能性があります。反復法がうまく機能するには、適切な前処理が必要ですが、問題ごとに異なります。前処理行列の選択が不適切な場合、収束が非常に遅くなる可能性があります。経験則として、設定について心配する必要がないため、常に直接法を使用することをお勧めします(少なくとも、私が使用する有限要素のフレームワークでは)。

以前は、直接法が小さな線形システムに使用されていました(小さいとは、計算に必要なすべての割り当てが、ハードドライブにスワップすることなくRAMで実行できることを意味します)、大きなシステムは繰り返し解決されました。ただし、現在、標準のRAMメモリは非常に高くなる可能性があるため、標準のPCで最大約2,000万の未知数を持つ線形システムを解くことができます。

ただし、本当に効率的な実装が必要です。独自のインバーターを実装することを忘れることができます。これは、現在利用可能な最高のソルバーを打ち負かすでしょう。(もちろん、何年も費やしたくない場合。簡単な作業ではありません。)個人的には、入手可能な最高の直接スパース線形ソルバーの1つであるOlafSchlenk製のPardisoライブラリを使用することをお勧めします。Intel Pardisoと呼ばれる無料バージョンもあります。これはIntel Webサイトからダウンロードできます(実際には、2006年のPardisoライブラリの古いバージョンです)。これは、METIS並べ替えアルゴリズムを備えたスパースコレスキーインバーターであり、対称および非対称のスパース行列を解きます。もう1つの良い可能性は、MUMPSライブラリを使用することです。

0
The Pheromone Kid 2019-04-20 05:38.

私の質問に答えるために、反復行列反転法に関する最近の出版物について短い文献レビューを行いました。

ガウス・ザイデル法(GS)

  • に https://arxiv.org/pdf/1411.2791.pdf、多くのアンテナと多くのユーザーを備えた無線通信システムでの信号検出が考慮されています。そこでは、最小平均二乗誤差解を計算するために線形方程式系を解く必要があります。変数の数は約2000になる可能性があります。これは劇的に高くはないようですが、計算は非常に高速である必要があります。

  • に https://dl.acm.org/citation.cfm?id=2982437、GSは、ビデオゲームで使用される可能性のあるソフトボディの物理ベースのアニメーションに使用されます。ここでの課題は、数ミリ秒未満でなければならない計算時間の厳しい要件です。「これらの場合、線形反復法が推奨されます。これは、与えられた許容誤差内で短時間で近似解を提供するためです。」この出版物では、GSは並行して適用されます。並列化は、他の反復法に対するGSの強力な利点であることに注意してください。

  • https://www.researchgate.net/profile/Matthias_Mueller14/publication/274479082_Unified_Particle_Physics_for_Real-Time_Applications/links/5538d62a0cf247b8587d5a6f.pdfリアルタイムアプリケーションでの視覚効果のシミュレーションを扱います。後者の作業では、オブジェクトは粒子の蓄積としてモデル化されます。これらの粒子は、たとえば衝突を通じて相互作用します。オブジェクトの動きをシミュレートするために、最適化問題を解いて運動エネルギーの最小変化を見つけます。これらの最適化問題は、線形方程式のセットを解く必要があります。GSは、並列化のために特に適しています。さらに、GSを使用すると、シミュレーションの精度と、反復回数によって調整される計算時間との間のトレードオフを取得できます。

連続過緩和(SOR)

  • https://arxiv.org/pdf/1507.04588.pdf 無線通信システムでの信号検出も扱います。

  • に http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.56.8725&rep=rep1&type=pdfSORは、分類に使用されるサポートベクターマシンアルゴリズムに適用されます。サポートベクターマシンの大まかな考え方は、機能に基づいて2つのクラスの要素を区別することです。目標は、1つのクラスの要素が一方の側にあり、他の要素がもう一方の側にあるように、多次元特徴空間を平面で分割することです。この計画の計算には、逆行列を含む最適化問題を解く必要があります。要素の数が多い場合、たとえば100000を超える場合、要素の数が多くなる可能性があります。

    つづく...

MORE COOL STUFF

ダイアナ妃は、8歳でウィリアム王子を寄宿学校に送るという決定に「涙を流した」

ダイアナ妃は、8歳でウィリアム王子を寄宿学校に送るという決定に「涙を流した」

ウィリアム王子が 8 歳のときに寄宿学校に通わせたことについて、ダイアナ妃がどのように感じたかを学びましょう。

シャキール・オニールは、レイカーズのスターが彼のチキン帝国を北テキサスに拡大するにつれて、ダラスの外に永住権を購入しました

シャキール・オニールは、レイカーズのスターが彼のチキン帝国を北テキサスに拡大するにつれて、ダラスの外に永住権を購入しました

Shaquille O'Neal は最近、Big Chicken レストラン帝国を拡大するため、ダラス郊外に住居を購入しました。

「90 日間の婚約者」: イヴが逮捕され、浮気スキャンダルの後、モハメドに対する家庭内暴力の容疑に直面している — 何が起こったのか?

「90 日間の婚約者」: イヴが逮捕され、浮気スキャンダルの後、モハメドに対する家庭内暴力の容疑に直面している — 何が起こったのか?

「90日の婚約者」シーズン9のスター、イヴ・アレラーノが逮捕され、モハメド・アブデルハメドへの暴行容疑で家庭内暴力の罪に問われている.

ナターシャ・リオンは、ピーウィー・ハーマンは「ビジネスで最高のGIFを送る」と言います

ナターシャ・リオンは、ピーウィー・ハーマンは「ビジネスで最高のGIFを送る」と言います

ナターシャ・リオンは、ピーウィー・ハーマン自身、ポール・ルーベンスと親密です。彼らの友情について彼女が言ったことを発見してください。

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セントヘレナのジェイコブのはしごを登るのは、気弱な人向けではありません

セント ヘレナ島のジェイコブズ ラダーは 699 段の真っ直ぐ上る階段で、頂上に到達すると証明書が発行されるほどの難易度です。

The Secrets of Airline Travel Quiz

The Secrets of Airline Travel Quiz

Air travel is far more than getting from point A to point B safely. How much do you know about the million little details that go into flying on airplanes?

Where in the World Are You? Take our GeoGuesser Quiz

Where in the World Are You? Take our GeoGuesser Quiz

The world is a huge place, yet some GeoGuessr players know locations in mere seconds. Are you one of GeoGuessr's gifted elite? Take our quiz to find out!

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

Razer Phoneレビュー:ゲーム用電話を作る正しい方法

Razer Phoneレビュー:ゲーム用電話を作る正しい方法

ゲーム中心のスマートフォンを作成する以前の試みには、スライド式ゲームコントローラーを備えた電話、Sony PlayStationPortableと電話とNokiaN-Gageのクロスが含まれます。Razerは、最初のゲーミングフォンとして、見事なディスプレイと優れたスピーカーを備えた強力な黒い長方形を採用しました。

2018年のビデオゲームの予測

2018年のビデオゲームの予測

キングダムハーツIII私たち全員が核のホロコーストで死ぬわけではないと仮定すると、ビデオゲームは2018年に何をもたらすでしょうか?今週のKotakuSplitscreenで、いくつかの予測の時間です。最初のカークと私は、Gravity Rush 2ファン、警察のスワッティングコールで死にかけている罪のない男、そして以前のローガンポールの激しい論争を含む今週のニュース(13:46)について話します来年の大きな予測を立てます(34:16)。

スイス航空ショーで2機の曲技飛行機が衝突、1人のパイロットが死亡したと報告

スイス航空ショーで2機の曲技飛行機が衝突、1人のパイロットが死亡したと報告

昨日のショアハム航空ショーでの恐ろしい墜落に続いて、ドイツのグラスホッパーズ曲技飛行チームに所属する2機のイカルスC42航空機が、スイスのディッティンゲンでの航空ショーで演奏中に空中で衝突しました。報告によると、1人のパイロットが衝突中に飛行機から投げ出され、地面にパラシュートで降下しました。

Chromebookをたった150ドルで購入できるようになりました(そしてさらに良くなっています)

Chromebookをたった150ドルで購入できるようになりました(そしてさらに良くなっています)

5年前、GoogleのCEOであるEric Sc​​hmidtは、ラップトップは使い捨てになると宣言しました。もうすぐです。

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、彼らが子供たちと行っているスパイをテーマにした活動を共有しています

ケイト・ミドルトンとウィリアム王子は、子供向けのパズルの本の序文を書き、ジョージ王子、シャーロット王女、ルイ王子と一緒にテキストを読むと述べた.

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

事故で押しつぶされたスイカは、動物を喜ばせ水分補給するために野生生物保護団体に寄付されました

Yak's Produce は、数十個のつぶれたメロンを野生動物のリハビリ専門家であるレスリー グリーンと彼女のルイジアナ州の救助施設で暮らす 42 匹の動物に寄付しました。

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

デミ・ロヴァートは、新しいミュージシャンのボーイフレンドと「幸せで健康的な関係」にあります: ソース

8 枚目のスタジオ アルバムのリリースに向けて準備を進めているデミ ロヴァートは、「スーパー グレート ガイ」と付き合っている、と情報筋は PEOPLE に確認しています。

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

Plathville の Kim と Olivia Plath が数年ぶりに言葉を交わすことへようこそ

イーサン プラスの誕生日のお祝いは、TLC のウェルカム トゥ プラスビルのシーズン 4 のフィナーレで、戦争中の母親のキム プラスと妻のオリビア プラスを結びつけました。

水門の修理

水門の修理

天王星と海王星の間の領域に向かって宇宙を 3/4 g の低温で航行しながら、私たちは数週間燃え続けていました。Dawson Trawler の科学者が Yggdrasil ポータルと呼んだもの。

美しいもの

美しいもの

女性として、私は通常、関係を築くことをためらっています。私はいつも彼らに負けないように苦労しました。私は誰かと共有したいという衝動と戦わなければなりません。

逃走中の女性からの発信

最も家が必要なときに家のように感じる場所はありません。

逃走中の女性からの発信

私は誰よりも移動しました。父が住んでいた土地には、父が 1 歳馬を折るミニチュアの競馬場がありました。

死にゆく男から学んだ最大の人生の教訓

彼は、私たちが持っているのはこの現在の瞬間だけであることを知るのが遅すぎました。

死にゆく男から学んだ最大の人生の教訓

ブラッドは、カーキ色のショート パンツとポロ シャツを着たまま、白いゴルフ グローブを両手で高く引っ張ったまま、ベッドルームに入ってきました。彼は満面の笑みを浮かべながら、「今年は私の人生で最高の年だったと思います!」と言いました。通常は保守的な消費者である私たちは、通常とは異なることをしました。

Language