クリロフ部分空間法
クリロフ部分空間法は、行列の要素ではなくその作用のみを必要とし、繰り返し行列-ベクトル積によって生成される部分空間から最良の近似を抽出することにより、大規模な疎線形システムを解く。
Definition
クリロフ部分空間法は、m番目のステップで、残差とその行列による連続的な像によって張られるm次元のクリロフ部分空間内で近似解を探索し、射影または最小化条件によって反復解を選択する反復ソルバーである。
Scope
このトピックでは、クリロフ部分空間とそのArnoldi法およびLanczos法による構築、対称正定値システムに対する共役勾配法、対称不定値行列および一般行列に対するMINRESおよびGMRES、BiCGSTABなどの双直交化法、そして反復回数とスペクトルおよび条件数とを結びつける収束理論について扱う。
Core questions
- クリロフ部分空間とは何か、またその正規直交基底はどのように安定的に構築されるのか？
- 共役勾配法が対称正定値システムに対して最適であり、短い漸化式であるのはなぜか？
- GMRESは一般的な非対称システムをどのように処理し、なぜストレージの増加が必要なのか？
- 行列のスペクトル特性は収束率をどのように決定するのか？
Key theories
- 共役勾配法
- 対称正定値システムの場合、共役勾配法はクリロフ部分空間上の誤差のエネルギーノルムを、短い3項漸化式を用いて最小化する。厳密な算術では最大nステップで収束し、固有値が集中している場合ははるかに速く収束する。
- GMRESとArnoldi法
- 一般行列の場合、GMRESはArnoldi法を用いて正規直交クリロフ基底を構築し、部分空間上の残差ノルムを最小化する。しかし、一般には短い漸化式が存在しないため、すべての基底ベクトルを保存する必要があり、再起動型が考案された。
Mechanisms
各手法は、行列とベクトルを繰り返し乗算してクリロフ部分空間を拡張し、新しい方向を以前の方向に対して直交化する。対称行列の場合、Lanczos法は三重対角射影と短い漸化式を生成するため、共役勾配法とMINRES法は少数のベクトルストレージしか必要としない。非対称行列の場合、Arnoldi法は完全な上ヘッセンベルグ射影を生成し、GMRESは各ステップで小さな最小二乗問題を解くことで残差を最小化するが、その代償として基底全体を保存する必要がある。再起動はこのコストを制限する。収束は固有値がどれほど有利に分布しているかによって決定され、前処理はこの分布を改善するために設計されている。
Clinical relevance
クリロフ法、特に前処理付き共役勾配法とGMRESは、有限要素法および有限体積法シミュレーションコード、大規模最適化、および一般科学計算における標準的なソルバーである。その行列フリーな性質により、直接法では因数分解できない数百万または数十億の未知数を持つシステムを解くことができる。
History
共役勾配法は1952年にHestenesとStiefelによって導入され、その基礎となるLanczos法は1950年に発表された。反復ソルバーとしてのその真の力は1970年代に認識され、1986年のSaadとSchultzによるGMRESの開発、および安定化された双直交法の開発により、このアプローチは一般的な非対称システムにまで拡張された。
Key figures
- Magnus Hestenes
- Eduard Stiefel
- Cornelius Lanczos
- Yousef Saad
- Henk van der Vorst
Related topics
Seminal works
- saad2003
- greenbaum1997
Frequently asked questions
- 共役勾配法が対称正定値行列にしか機能しないのはなぜですか？
- その短く効率的な漸化式と、エネルギーノルムにおける最適性は、行列が対称正定値であることに依存しています。対称不定値行列や非対称行列の場合、MINRESやGMRESなどの異なる手法が必要となり、一般により多くのストレージやステップあたりの計算量が必要となります。
- GMRESはなぜそんなに多くのメモリを必要とするのですか？
- 一般的な非対称行列の場合、クリロフ基底を直交に保つ短い漸化式が存在しないため、GMRESは残差を最小化するためにすべての基底ベクトルを保存する必要があります。再起動型GMRESは、基底を定期的に破棄することでメモリを制限しますが、その代償として収束が遅くなります。