マルチグリッド法

数値解析において、マルチグリッド法（MG法）は、離散化の階層構造を用いて微分方程式を解くアルゴリズムです。これは、複数のスケールで挙動を示す問題に非常に有用な、マルチレゾリューション法と呼ばれる手法の一例です。例えば、多くの基本的な緩和法は、短波長成分と長波長成分で収束速度が異なるため、マルチグリッドに対するフーリエ解析アプローチのように、これらの異なるスケールを異なる方法で扱う必要があることが示唆されます。^{[ 1 ]} MG法は、ソルバーとしても前処理器としても使用できます。

マルチグリッドの主なアイデアは、粗い問題を解くことによって、細かいグリッド解の近似を時折グローバルに修正することで、基本的な反復法（一般的に短波長誤差を低減する緩和法として知られる）の収束を加速することです。粗い問題は、解くコストは低いものの、短波長誤差と長波長誤差の両方を持つ点で細かいグリッド問題と似ています。また、緩和法とさらに粗いグリッドへの適用を組み合わせることによっても解くことができます。この再帰的なプロセスは、細かいグリッドでの1回の緩和スイープのコストと比較して、そのグリッドでの直接解法のコストが無視できるほど小さくなるまで繰り返されます。このマルチグリッドサイクルでは、通常、細かいグリッドのメッシュサイズに関係なく、すべての誤差成分が1よりかなり小さい固定値で低減されます。マルチグリッドの典型的な応用例は、2次元以上の楕円型偏微分方程式の数値解法です。 ^{[ 2 ]}

マルチグリッド法は、一般的な離散化手法のいずれとも組み合わせて適用できます。たとえば、有限要素法をマルチグリッド法として再定式化することができます。^{[ 3 ]}これらの場合、マルチグリッド法は、現在知られている中で最も高速な解法の一つです。他の方法とは対照的に、マルチグリッド法は任意の領域と境界条件を扱うことができるという点で汎用的です。方程式の分離可能性や方程式のその他の特別な性質に依存しません。また、ラメ弾性方程式やナビエ・ストークス方程式のような、より複雑な非対称および非線形方程式系にも広く使用されています。^{[ 4 ]}

マルチグリッドアルゴリズムには多くのバリエーションがありますが、共通の特徴は、離散化（グリッド）の階層を考慮することです。重要な手順は次のとおりです。^{[ 5 ] [ 6 ]}

• 平滑化– 例えばガウス・ザイデル法を数回繰り返すことで、高周波誤差を低減する。
• 残差計算–平滑化処理後の残差誤差を計算します。
• 制約–残差誤差をより粗いグリッドにダウンサンプリングする。
• 補間または延長– より粗いグリッドで計算された補正値を、より細かいグリッドに補間すること。
• 修正– より細かいグリッドに、より粗いグリッドによる長時間の解を追加します。

マルチグリッド法には、1回の反復の解決速度と、その反復における収束速度のトレードオフが異なる多くの選択肢があります。主なタイプは、Vサイクル、Fサイクル、Wサイクルの3つです。これらは、細かい反復ごとに実行される粗粒度サイクルの種類と数で異なります。Vサイクルアルゴリズムは、1つの粗粒度Vサイクルを実行します。Fサイクルは、粗粒度Vサイクルの後に粗粒度Fサイクルを実行しますが、各Wサイクルは、反復ごとに2つの粗粒度Wサイクルを実行します。離散2D問題の場合、FサイクルはVサイクル反復よりも計算に83%多くかかり、Wサイクル反復は125%多くかかります。問題が3D領域に設定されている場合、オーバーヘッドを無視すると、Fサイクル反復とWサイクル反復は、それぞれVサイクル反復よりも約64%と75%多くかかります。通常、WサイクルはFサイクルと同様の収束性を示します。しかし、ペクレ数が大きい対流拡散方程式の場合、Wサイクルは反復ごとの収束率においてFサイクルよりも優れている場合があります。平滑化演算子の選択肢は非常に多様で、クリロフ部分空間法や前処理法などが含まれます。

幾何学的マルチグリッドサイクル反復は、グリッドの階層構造上で実行されるため、再帰を用いてコーディングできます。関数はより小さな（粗い）パラメータで自身を呼び出すため、再帰は最も粗いグリッドで停止します。システムの条件数が高い場合、修正手順が変更され、粗いグリッドで得られた解のごく一部のみが細かいグリッドに追加されます。

この手法は、他の手法に比べて、使用する離散ノードの数に比例して計算量が直線的に増加するという利点があります。つまり、未知数の数に比例した演算回数で、所定の精度でこれらの問題を解決できるということです。

グリッド上で（所定の精度で）近似的に解ける微分方程式があると仮定する。${\displaystyle i}$与えられたグリッド点密度で${\displaystyle N_{i}}$さらに、任意のグリッド上の解は${\displaystyle N_{i}}$一定の努力で得られる可能性がある${\displaystyle W_{i}=\rho KN_{i}}$より粗いグリッド上の解から${\displaystyle i+1}$。 ここ、${\displaystyle \rho =N_{i+1}/N_{i}<1}$は「隣接する」グリッド上のグリッド点の比率であり、グリッド階層全体で一定であると仮定され、${\displaystyle K}$これは、1つのグリッドポイントの結果を計算するのに必要な労力をモデル化する定数です。

グリッド上で解を求めるための努力に対して、次の漸化式が得られる。${\displaystyle k}$: $${\displaystyle W_{k}=W_{k+1}+\rho KN_{k}}$$

そして特に、最も細かいグリッドでは${\displaystyle N_{1}}$それ $${\displaystyle W_{1}=W_{2}+\rho KN_{1}}$$ これら2つの表現を組み合わせると（そして${\displaystyle N_{k}=\rho ^{k-1}N_{1}}$) は $${\displaystyle W_{1}=KN_{1}\sum _{p=0}^{n}\rho ^{p}}$$

等比級数を用いると、(有限の場合)${\displaystyle n}$） $${\displaystyle W_{1}<KN_{1}{\frac {1}{1-\rho }}}$$

つまり、解決策は${\displaystyle O(N)}$時間。ただし、例外が1つあることを述べておく必要がある。${\displaystyle O(N)}$つまり、1D問題にWサイクルマルチグリッドを使用すると、${\displaystyle O(N\log N)}$複雑。

意図的に許容誤差を小さくしたマルチグリッド法は、外部反復ソルバーの効率的な前処理として使用できます。例えば、 ^{[ 7 ]}解は依然として得られます。${\displaystyle O(N)}$時間だけでなく、マルチグリッド法をソルバーとして使用する場合にも同様です。マルチグリッド前処理は、実際には線形システムにも使用され、通常は反復ごとに1サイクルで行われます（例：Hypre ）。純粋なマルチグリッドソルバーと比較した場合の主な利点は、固有値問題などの非線形問題で特に明確になります。

元の方程式または固有値問題の行列が対称正定値 (SPD) である場合、前処理行列も一般的に SPD となるように構築されるため、標準的な共役勾配法(CG)反復法を引き続き使用できます。このような SPD 制約を課すと、前処理行列の構築が複雑になる場合があり、たとえば、前処理と後処理の平滑化を協調して行う必要が生じます。ただし、SPD 線形システムに対する前処理付き最急降下法と柔軟な CG 法、および対称固有値問題に対するLOBPCG法は、前処理行列が SPD でない場合でもすべてロバストであることが示されています^{[ 8 ] 。}

BPX前処理法は、もともとXuの博士論文^{[ 9 ]}で記述され、後にBramble-Pasciak-Xu ^{[ 10 ]}で発表されたもので、偏微分方程式で記述される科学および工学モデルの離散化から生じる大規模な代数システムを解くための2つの主要なマルチグリッドアプローチ（もう1つはVサイクルなどの古典的なマルチグリッドアルゴリズム）の1つです。部分空間補正フレームワーク^{[ 11 ]}の観点から見ると、 BPX前処理法は並列部分空間補正法であり、古典的なVサイクルは逐次部分空間補正法です。BPX前処理法は、古典的なVサイクルマルチグリッド法よりも自然に並列性が高く、一部のアプリケーションではより堅牢であることが知られています。この方法は、1990年以来、研究者や実務家によって広く使用されています。

マルチグリッド法は、さまざまな方法で一般化できます。放物型偏微分方程式の時間ステップ解法に自然に適用することも、時間依存偏微分方程式に直接適用することもできます。^{[ 12 ]}双曲型偏微分方程式 に対するマルチレベル手法の研究が進行中です。^{[ 13 ]}マルチグリッド法は、積分方程式や統計物理学の問題にも適用できます。^{[ 14 ]}

多重解像度法のもう1つのセットはウェーブレットに基づいています。これらのウェーブレット法は、マルチグリッド法と組み合わせることができます。^{[ 15 ] [ 16 ]}例えば、ウェーブレットの用途の1つは、有限要素法をマルチレベル法の観点から再定式化することです。^{[ 17 ]}

適応型マルチグリッドは適応型メッシュ細分化を示し、つまり、計算自体に依存する方法で、計算の進行に伴ってグリッドを調整します。^{[ 18 ]}そのアイデアは、必要な解の領域でのみグリッドの解像度を上げることです。

マルチグリッド法の実際的に重要な拡張には、多段階階層を構築するために偏微分方程式や幾何学的問題の背景を使用しない手法が含まれます。^{[ 19 ]}このような代数的マルチグリッド法（AMG）は、システム行列から直接演算子の階層を構築します。古典的なAMGでは、階層のレベルは、幾何学的解釈のない未知数のサブセットです。（より一般的には、粗いグリッドの未知数は、細かいグリッドの未知数の特定の線形結合である可能性があります。）したがって、AMG法は、特定のクラスの疎行列のブラックボックスソルバーになります。AMGは、主に幾何学的マルチグリッドの適用が難しすぎる場合に有利であると考えられていますが、^{[ 20 ]}真のマルチグリッド実装に必要なコーディングを回避するためだけによく使用されます。古典的なAMGが最初に開発されましたが、関連する代数的手法は平滑化集約（SA）として知られています。

Jinchao XuとLudmil Zikatanovによる概説論文^{[ 21 ]}では、「代数的マルチグリッド」法が抽象的な観点から理解されています。彼らは統一的なフレームワークを開発し、既存の代数的マルチグリッド法を首尾一貫して導出できるようになりました。最適な粗空間と準最適な空間を構築する方法に関する抽象的な理論が導出されました。この結果は、BrannickとZikatanovによる代数的マルチグリッドに関するノートに最初に登場し、概説論文で書き直されただけであることに注意してください。また、適切な仮定の下で、抽象的な2レベルAMG法は、線形システムのサイズ、係数変動、および異方性に関して一様に収束することを証明しました。彼らの抽象的なフレームワークは、古典的AMG、エネルギー最小化AMG、平滑化されていないおよび平滑化された集約AMG、スペクトルAMGeなど、既存のほとんどのAMG法を網羅しています。

マルチグリッド法は、初期値問題の解法にも採用されています。^{[ 22 ]} ここで特に注目すべきは、時間的に並列なマルチグリッド法です。^{[ 23 ]}古典的なルンゲ・クッタ法や線形多段階法 とは対照的に、時間方向の並列性を提供できます。よく知られているパラリアル時間並列積分法も、2 レベルの時間マルチグリッドとして再定式化できます。

ほぼ特異な問題は、多くの重要な物理学および工学の応用分野で発生します。ほぼ特異な問題の単純かつ重要な例は、ほぼ非圧縮性材料の線形弾性の変位定式化に見られます。通常、このようなほぼ特異なシステムを解くための主要な問題は、次のほぼ特異な演算子を扱うことに帰着します。${\displaystyle A+\varepsilon M}$正の値だが小さいパラメータに対して頑健${\displaystyle \varepsilon }$。 ここ${\displaystyle A}$は大きな零空間を持つ対称半正定値演算子であり、${\displaystyle M}$は対称正定値演算子です。このようなほぼ特異な問題に対して、堅牢で高速なマルチグリッド法を設計しようとする研究が数多くありました。このようなほぼ特異なシステムに適用されるマルチグリッド法の収束率をパラメータ（例えば、メッシュサイズや、ほぼ特異な演算子に現れるポアソン比などの物理パラメータ）に依存しないようにするための設計原理として、一般的なガイドが提供されています。 ^{[ 24 ]}つまり、各グリッドにおいて、平滑化の基となる空間分解を構築し、ほぼ特異な演算子の特異部分の零空間が、局所零空間の和、零空間と空間分解から生じる局所空間の交差に含まれるようにする必要があります。

• AMGのプレゼンテーションへのリンク