マルチグリッド法

数値解析において、マルチグリッド法（MG法）は、離散化の階層を使用して微分方程式を解くアルゴリズムです。これは、多重解像度法と呼ばれる一連の手法の一例であり、複数の動作スケールを示す問題で非常に役立ちます。たとえば、多くの基本的な緩和法は、短波長成分と長波長成分に対して異なる収束率を示します。これは、マルチグリッドに対するフーリエ解析アプローチのように、これらの異なるスケールを別々に扱うことを示唆しています。 ^{[1] MG法は、ソルバーとしても、}前処理としても使用できます。

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

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

アルゴリズム

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

スムージング- たとえば、ガウス・ザイデル法を数回反復して、高周波エラーを減らします。
残差計算–平滑化操作後の残差誤差を計算します。
制限–残差誤差をより粗いグリッドにダウンサンプリングします。
補間または延長- 粗いグリッド上で計算された補正をより細かいグリッドに補間します。
修正– より細かいグリッドに、より粗いグリッドソリューションを追加します。

マルチグリッド法には多くの選択肢があり、単一の反復を解く速度とその反復での収束率との間のトレードオフはさまざまです。主な 3 つのタイプは、V サイクル、F サイクル、および W サイクルです。これらは、細かい反復ごとに実行される粗粒度サイクルとその回数が異なります。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 サイクルよりも優れている可能性があります。スムージング演算子の選択肢は、クリロフ部分空間法を含み、事前条件付けできるため、非常に多様です。

幾何学的マルチグリッドサイクルの反復は、グリッドの階層で実行されるため、再帰を使用してコード化できます。関数は、より小さいサイズ (粗い) のパラメーターで自身を呼び出すため、最も粗いグリッドで再帰が停止します。システムの条件数が高い場合、補正手順が変更され、延長された粗いグリッドソリューションの一部だけがより細かいグリッドに追加されます。

計算コスト^[要出典]

2 次元の問題設定を想定すると、計算はさまざまなマルチグリッドサイクルごとに異なる方法でグリッド階層を移動します。

このアプローチは、使用される離散ノードの数に応じて線形にスケールすることが多いという点で、他の方法よりも優れています。言い換えると、未知数の数に比例する操作の数で、これらの問題を所定の精度で解くことができます。

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

グリッド上で解を得るための努力に対して、次の再帰関係が得られます。 $k$

W_{k}=W_{k+1}+\rho KN_{k}

そして特に、最も細かいグリッドでは、 $N_{1}$

W_{1}=W_{2}+\rho KN_{1}

これら2つの式を組み合わせると（を使用）、 $N_{k}=\rho ^{k-1}N_{1}$

W_{1}=KN_{1}\sum _{p=0}^{n}\rho ^{p}

等比級数を用いて、（有限に対して） $n$

W_{1}<KN_{1}{\frac {1}{1-\rho }}

つまり、時間内に解が得られる可能性がある。1D問題で使用されるWサイクルマルチグリッドには例外が1つあることに注意する必要がある。それは、複雑性が生じるということである。^[^要出典^] $O(N)$ $O(N)$ $O(Nlog(N))$

マルチグリッド前処理

意図的に許容誤差を減らしたマルチグリッド法は、外部反復ソルバーの効率的な前処理として使用できます。たとえば、 ^[7]マルチグリッド法をソルバーとして使用した場合と同様に、ソリューションは時間内に取得できます。マルチグリッド前処理は、線形システムでも実際には使用され、通常はHypreなどで反復ごとに 1 サイクルです。純粋なマルチグリッドソルバーと比較した主な利点は、非線形問題、たとえば固有値問題で特に明らかです。 $O(N)$

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

Bramble-Pasciak-Xu プリコンディショナー

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

一般化されたマルチグリッド法

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

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

適応型マルチグリッドは適応型メッシュリファインメントを示し、つまり計算自体に依存した方法で計算の進行に合わせてグリッドを調整します。^[18]その考え方は、必要なソリューションの領域でのみグリッドの解像度を上げるというものです。

代数マルチグリッド (AMG)

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

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

時間法におけるマルチグリッド

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

ほぼ特異な問題に対するマルチグリッド

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

注記

^ Roman Wienands、Wolfgang Joppich (2005)。マルチグリッド法のための実用的なフーリエ解析。CRC Press。p. 17。ISBN 978-1-58488-492-7。
^ U. トロッテンベルク; CWオースタリー。 A. シュラー (2001)。マルチグリッド。学術出版局。ISBN 978-0-12-701070-0。
^ Yu Zhu、Andreas C. Cangellaris (2006) 。電磁場モデリングのためのマルチグリッド有限要素法。Wiley。p . 132 ff。ISBN 978-0-471-74110-7。
^ Shah, Tasneem Mohammad (1989).マルチグリッド法の分析(論文). オックスフォード大学. Bibcode :1989STIN...9123418S.
^ MT Heath (2002)。「 セクション11.5.7 マルチグリッド法」。科学計算入門調査。McGraw -Hill Higher Education。p. 478 ff。ISBN 978-0-07-112229-0。
^ P. Wesseling (1992). マルチグリッド法入門. Wiley. ISBN 978-0-471-93083-9。
^ Andrew V Knyazev、Klaus Neymeyr。局所最適ブロック共役勾配法におけるマルチグリッド前処理を使用した対称固有値問題の効率的な解。数値解析に関する電子取引、15、38–55、2003年。
^ Bouwmeester, Henricus; Dougherty, Andrew; Knyazev, Andrew V. (2015). 「共役勾配法と最急降下法 1 の非対称前処理」. Procedia Computer Science . 51 : 276–285. arXiv : 1212.6680 . doi : 10.1016/j.procs.2015.05.241 . S2CID 51978658.
^ Xu, Jinchao. マルチレベル法の理論。第8924558巻。ニューヨーク州イサカ：コーネル大学、1989年。
^ Bramble、James H.、Joseph E. Pasciak、Jinchao Xu. 「並列マルチレベル前提条件」。計算の数学 55、いいえ。 191 (1990): 1–22。
^ Xu, Jinchao. 「空間分解と部分空間補正による反復法」 SIAM review 34, no. 4 (1992): 581-613.
^ F. Hülsemann; M. Kowarschik; M. Mohr; U. Rüde (2006)。「並列ジオメトリックマルチグリッド」。Are Magnus Bruaset、Aslak Tveito (編)。並列コンピュータ上の偏微分方程式の数値解。Birkhäuser。p. 165。ISBN 978-3-540-29076-6。
^ 例えば、J. Blaz̆ek (2001)。計算流体力学：原理と応用。Elsevier。p. 305。ISBN 978-0-08-043009-6。およびAchi Brandt と Rima Gandlin (2003)。「大気データ同化のためのマルチグリッド: 分析」。Thomas Y. Hou、Eitan Tadmor (編)。双曲型問題: 理論、数値、アプリケーション: 2002 年第 9 回双曲型問題に関する国際会議の議事録。Springer。p. 369。ISBN 978-3-540-44333-9。
^ Achi Brandt (2002)。「マルチスケール科学計算：レビュー」。Timothy J. Barth、Tony Chan、Robert Haimes（編）「マルチスケールおよびマルチ解像度法：理論と応用」。Springer。p. 53。ISBN 978-3-540-42420-8。
^ Björn Engquist、Olof Runborg (2002)。「ウェーブレットベースの数値均質化とその応用」。Timothy J. Barth、Tony Chan、Robert Haimes (編)。マルチスケールおよびマルチ解像度法。計算科学および工学の講義ノート第 20 巻。Springer。140ページ以降。ISBN 978-3-540-42420-8。
^ U. トロッテンベルク; CWオースタリー。 A. シュラー (2001)。マルチグリッド。学術出版局。ISBN 978-0-12-701070-0。
^ アルバート・コーエン (2003). ウェーブレット法の数値解析. エルゼビア. p. 44. ISBN 978-0-444-51124-9。
^ U. Trottenberg、CW Oosterlee、A. Schüller (2001)。「第 9 章: 適応型マルチグリッド」。マルチグリッド。Academic Press。p. 356。ISBN 978-0-12-701070-0。
^ Yair Shapira (2003). 「代数マルチグリッド」。行列ベースのマルチグリッド: 理論と応用。 Springer。 p. 66。ISBN 978-1-4020-7485-1。
^ U. トロッテンベルク; CWオースタリー。 A. シュラー (2001)。マルチグリッド。学術出版局。 p. 417.ISBN 978-0-12-701070-0。
^ Xu, J. および Zikatanov, L.、2017。代数マルチグリッド手法。 Acta Numerica、26、591-721ページ。 [1]
^ Hackbusch, Wolfgang (1985). 「放物線型マルチグリッド法」.応用科学と工学における計算方法, VI : 189–197. ISBN 9780444875976. 2015年8月1日閲覧。
^ Horton, Graham (1992). 「時間並列マルチグリッド法」.応用数値計算法の通信. 8 (9): 585–595. doi :10.1002/cnm.1630080906.
^ Young-Ju Lee、Jinbiao Wu、Jinchao Xu、Ludmil Zikatanov、「ほぼ特異なシステムに対する堅牢なサブスペース補正法」、応用科学における数学モデルと方法、第 17 巻、第 11 号、pp. 1937-1963 (2007)

参考文献

GP Astrachancev (1971)「楕円ネット問題を解く反復法」USSR Comp. Math. Math. Phys. 11, 171–182。
NS Bakhvalov (1966)「楕円演算子に対する自然な制約条件を伴う緩和法の収束について」USSR Comp. Math. Math. Phys. 6, 101–13。
Achi Brandt (1977 年 4 月)、「境界値問題に対する多段階適応型ソリューション」、Mathematics of Computation、31 : 333–90。
William L. Briggs、Van Emden Henson、Steve F. McCormick (2000)、「A Multigrid Tutorial (第 2 版)」、フィラデルフィア: Society for Industrial and Applied Mathematics、ISBN 0-89871-462-1。
RP Fedorenko (1961)、「楕円差分方程式を解くための緩和法」USSR Comput. Math. Math. Phys. 1、p. 1092。
RP Fedorenko (1964)、「1つの反復プロセスの収束速度」、USSR Comput. Math. Math. Phys. 4、p. 227。
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)。「セクション 20.6. 境界値問題に対するマルチグリッド法」。数値レシピ: 科学計算の技法(第 3 版)。ニューヨーク: Cambridge University Press。ISBN 978-0-521-88068-8。

外部リンク

マルチグリッド、マルチレベル、マルチスケール、集約、欠陥修正、および領域分割法のリポジトリ
マルチグリッドチュートリアル
代数マルチグリッドチュートリアル
AMGプレゼンテーションへのリンク

[1] Roman Wienands、Wolfgang Joppich (2005)。マルチグリッド法のための実用的なフーリエ解析。CRC Press。p. 17。ISBN 978-1-58488-492-7。

[2] U. トロッテンベルク; CWオースタリー。 A. シュラー (2001)。マルチグリッド。学術出版局。ISBN 978-0-12-701070-0。

[3] ^ Yu Zhu、Andreas C. Cangellaris (2006) 。電磁場モデリングのためのマルチグリッド有限要素法。Wiley。p . 132 ff。ISBN 978-0-471-74110-7。

[4] Shah, Tasneem Mohammad (1989).マルチグリッド法の分析(論文). オックスフォード大学. Bibcode :1989STIN...9123418S.

[5] ^ MT Heath (2002)。「 セクション11.5.7 マルチグリッド法」。科学計算入門調査。McGraw -Hill Higher Education。p. 478 ff。ISBN 978-0-07-112229-0。

[6] P. Wesseling (1992). マルチグリッド法入門. Wiley. ISBN 978-0-471-93083-9。

[7] Andrew V Knyazev、Klaus Neymeyr。局所最適ブロック共役勾配法におけるマルチグリッド前処理を使用した対称固有値問題の効率的な解。数値解析に関する電子取引、15、38–55、2003年。

[8] Bouwmeester, Henricus; Dougherty, Andrew; Knyazev, Andrew V. (2015). 「共役勾配法と最急降下法 1 の非対称前処理」. Procedia Computer Science . 51 : 276–285. arXiv : 1212.6680 . doi : 10.1016/j.procs.2015.05.241 . S2CID 51978658.

[9] Xu, Jinchao. マルチレベル法の理論。第8924558巻。ニューヨーク州イサカ：コーネル大学、1989年。

[10] Bramble、James H.、Joseph E. Pasciak、Jinchao Xu. 「並列マルチレベル前提条件」。計算の数学 55、いいえ。 191 (1990): 1–22。

[11] Xu, Jinchao. 「空間分解と部分空間補正による反復法」 SIAM review 34, no. 4 (1992): 581-613.

[12] F. Hülsemann; M. Kowarschik; M. Mohr; U. Rüde (2006)。「並列ジオメトリックマルチグリッド」。Are Magnus Bruaset、Aslak Tveito (編)。並列コンピュータ上の偏微分方程式の数値解。Birkhäuser。p. 165。ISBN 978-3-540-29076-6。

[13] 例えば、J. Blaz̆ek (2001)。計算流体力学：原理と応用。Elsevier。p. 305。ISBN 978-0-08-043009-6。およびAchi Brandt と Rima Gandlin (2003)。「大気データ同化のためのマルチグリッド: 分析」。Thomas Y. Hou、Eitan Tadmor (編)。双曲型問題: 理論、数値、アプリケーション: 2002 年第 9 回双曲型問題に関する国際会議の議事録。Springer。p. 369。ISBN 978-3-540-44333-9。

[14] Achi Brandt (2002)。「マルチスケール科学計算：レビュー」。Timothy J. Barth、Tony Chan、Robert Haimes（編）「マルチスケールおよびマルチ解像度法：理論と応用」。Springer。p. 53。ISBN 978-3-540-42420-8。

[15] Björn Engquist、Olof Runborg (2002)。「ウェーブレットベースの数値均質化とその応用」。Timothy J. Barth、Tony Chan、Robert Haimes (編)。マルチスケールおよびマルチ解像度法。計算科学および工学の講義ノート第 20 巻。Springer。140ページ以降。ISBN 978-3-540-42420-8。

[16] U. トロッテンベルク; CWオースタリー。 A. シュラー (2001)。マルチグリッド。学術出版局。ISBN 978-0-12-701070-0。

[17] アルバート・コーエン (2003). ウェーブレット法の数値解析. エルゼビア. p. 44. ISBN 978-0-444-51124-9。

[18] U. Trottenberg、CW Oosterlee、A. Schüller (2001)。「第 9 章: 適応型マルチグリッド」。マルチグリッド。Academic Press。p. 356。ISBN 978-0-12-701070-0。

[19] Yair Shapira (2003). 「代数マルチグリッド」。行列ベースのマルチグリッド: 理論と応用。 Springer。 p. 66。ISBN 978-1-4020-7485-1。

[20] U. トロッテンベルク; CWオースタリー。 A. シュラー (2001)。マルチグリッド。学術出版局。 p. 417.ISBN 978-0-12-701070-0。

[21] Xu, J. および Zikatanov, L.、2017。代数マルチグリッド手法。 Acta Numerica、26、591-721ページ。 [1]

[22] Hackbusch, Wolfgang (1985). 「放物線型マルチグリッド法」.応用科学と工学における計算方法, VI : 189–197. ISBN 9780444875976. 2015年8月1日閲覧。

[23] Horton, Graham (1992). 「時間並列マルチグリッド法」.応用数値計算法の通信. 8 (9): 585–595. doi :10.1002/cnm.1630080906.

[24] Young-Ju Lee、Jinbiao Wu、Jinchao Xu、Ludmil Zikatanov、「ほぼ特異なシステムに対する堅牢なサブスペース補正法」、応用科学における数学モデルと方法、第 17 巻、第 11 号、pp. 1937-1963 (2007)