マルチグリッド法

数学 > 数値解析 > 偏微分方程式の数値解法 > マルチグリッド法

マルチグリッド（MG）法は、離散化を複数階層で多段階化することで、解が滑らかな微分方程式を解くための数値アルゴリズムの手法である[1][2][3][4][5]。間隔の異なる格子間での補外[6]と考えることもできる。マルチグリッド法は、主に多次元の楕円型偏微分方程式の数値計算に用いられる[7][8]。

マルチグリッド法は任意の離散化手法と組み合わせることができ、現在知られている解法のうちで漸近的に最も高速なものの一つである[1][2][3][4][5]。他の手法とは異なり、マルチグリッド法は任意の領域・境界条件を扱うことができる[1][2][3][4][5]。このことは微分方程式の性質（たとえば変数分離可能であるかどうかなど）には依存しない。マルチグリッド法は、弾性に関するラメの微分方程式やナビエ・ストークス方程式[9][10][11]などの、より複雑な非対称・非線形問題にもそのまま適用することができる[12]。

一般化

マルチグリッド法はさまざまな形に一般化することができる[1][2][3][4][5]。双曲型偏微分方程式の時間発展解や、時間依存型の偏微分方程式に適用することもできる。現在、双曲型方程式に関する研究が進められている[13]。積分方程式や、統計力学上の問題への応用も可能である[14][15]。

一方、偏微分方程式や問題の物理的な現象に由来する性質を仮定しない場合にも、係数行列から多段階の階層を構成することができる。これを代数的マルチグリッド法といい[16][17][18][19]、疎行列を対象としたブラックボックス型のソルバとして利用することができる。

有限要素法[20][21][22][23]において、線形なウェーブレットを基底に選ぶことにより、マルチグリッド法に帰着させることができる。

アルゴリズム

いろいろな手法があるが、多階層をわたる離散化を行うところが特徴である[1][2][3][4][5]。

  • 緩和 – ガウス・ザイデル法などを数回程度反復実行して、誤差の高周波成分を強く減少させる
  • 縮約 – より間隔の粗い格子に対して、残差のダウンサンプリングを行う
  • 補間 – 粗い格子上で計算した修正を細かい格子上に補間する

収束率

この手法の利点は、計算に用いるプロセッサの数に正比例して性能が向上する点にある。つまり、指定した精度の解を問題のサイズに比例した計算量で求めることができる。そのことを以下で示そう。

密度が N i {\displaystyle N_{i}} の格子 i {\displaystyle i} 上で、微分方程式の近似解を（与えられた精度まで）求めることを考える。 K {\displaystyle K} を格子上での解の計算に関する定数、また隣り合う格子の密度の比 ρ = N j + 1 / N j < 1 {\displaystyle \rho =N_{j+1}/N_{j}<1} は常に一定であるとする。格子 i + 1 {\displaystyle i+1} の解を用いて、格子 i {\displaystyle i} 上での解が W i = ρ K N i {\displaystyle W_{i}=\rho KN_{i}} の計算量で求められるとすると、

W k = W k + 1 + ρ K N k {\displaystyle W_{k}=W_{k+1}+\rho KN_{k}\,}

特に最も細かい格子 N 1 {\displaystyle N_{1}} に関して

W 1 = W 2 + ρ K N 1 {\displaystyle W_{1}=W_{2}+\rho KN_{1}\,}

の関係が格子 k {\displaystyle k} 上での計算量に関して成り立つ。これらと N k = ρ k − 1 N 1 {\displaystyle N_{k}=\rho ^{k-1}N_{1}} の関係から、

W 1 = K N 1 ∑ p = 0 n ρ p {\displaystyle W_{1}=KN_{1}\sum _{p=0}^{n}\rho ^{p}}

が得られる。幾何級数を使えば、（有限の n {\displaystyle n} について）

W 1 < K N 1 1 1 − ρ {\displaystyle W_{1}<KN_{1}{\frac {1}{1-\rho }}}

であるから、 O ( N ) {\displaystyle O(N)} の計算量により解が得られることが分かる。

関連項目

参考文献

  • Achi Brandt: Multi-Level Adaptive Solutions to Boundary-Value Problems, Math. Comp, vol.31(1977), pp.333-390 (jstor link).
  • Wolfgang Hackbusch: Multi-Grid Methods and Applications, Springer, ISBN 978-3-642-05722-9 (1985).
  • William L. Briggs, Van Emden Henson, and Steve F. McCormick: A Multigrid Tutorial, Second Edition, SIAM, 2000 (book home page), ISBN 0-89871-462-1 .

関連文献

  • Roman Wienands and Wolfgang Joppich:"Practical Fourier Analysis for Multigrid Methods", Chapman and Hall/CRC, ISBN 978-1584884927 (2004年).
  • Copper Mountain Conference on Multigrid Methods (Multigrid Conference materials) GitHub

脚注

  1. ^ a b c d e Wolfgang Hackbusch: Multi-Grid Methods and Applications, Springer, ISBN 978-3-642-05722-9 (1985).
  2. ^ a b c d e McCormick, S. F. (Ed.). (1987). Multigrid methods. Society for Industrial and Applied Mathematics.
  3. ^ a b c d e Hackbusch, W., & Trottenberg, U. (Eds.). (2006). Multigrid methods: proceedings of the conference held at Köln-Porz, November 23-27, 1981 (Vol. 960). Springer.
  4. ^ a b c d e Yavneh, I. (2006). Why multigrid methods are so efficient. Computing in science & engineering, 8(6), 12-22.
  5. ^ a b c d e Bramble, J. H. (2018). Multigrid methods. Routledge.
  6. ^ Brezinski, C., & Zaglia, M. R. (2013). Extrapolation methods: theory and practice. Elsevier.
  7. ^ Zubair, H. B., Oosterlee, C. W., & Wienands, R. (2007). Multigrid for high-dimensional elliptic partial differential equations on non-equidistant grids. SIAM Journal on Scientific Computing, 29(4), 1613-1636.
  8. ^ Fulton, S. R., Ciesielski, P. E., & Schubert, W. H. (1986). Multigrid methods for elliptic problems: A review. Monthly Weather Review, 114(5), 943-959.
  9. ^ Constantin, P., & Foias, C. (1988). Navier-stokes equations. University of Chicago Press.
  10. ^ Temam, R. (2001). Navier-Stokes equations: theory and numerical analysis (Vol. 343). American Mathematical Society.
  11. ^ Foias, C., Manley, O., Rosa, R., & Temam, R. (2001). Navier-Stokes equations and turbulence (Vol. 83). Cambridge University Press.
  12. ^ Henson, V. E. (2002). Multigrid methods for nonlinear problems: an overview (Vol. 5016, No. UCRL-JC-150259). Lawrence Livermore National Lab., CA (US).
  13. ^ Katzer, E. (1991). Multigrid methods for hyperbolic equations. In Multigrid methods III (pp. 253-263). Birkhäuser, Basel.
  14. ^ Schippers, H. (1982). Application of multigrid methods for integral equations to two problems from fluid dynamics. Journal of Computational Physics, 48(3), 441-461.
  15. ^ Von Petersdorff, T., & Stephan, E. P. (1992). Multigrid solvers and preconditioners for first kind integral equations. Numerical Methods for Partial Differential Equations, 8(5), 443-450.
  16. ^ Notay, Y. (2010). An aggregation-based algebraic multigrid method. Electronic transactions on numerical analysis, 37(6), 123-146.
  17. ^ Reitzinger, S., & Schöberl, J. (2002). An algebraic multigrid method for finite element discretizations with edge elements. Numerical linear algebra with applications, 9(3), 223-238.
  18. ^ Napov, A., & Notay, Y. (2012). An algebraic multigrid method with guaranteed convergence rate. SIAM journal on scientific computing, 34(2), A1079-A1109.
  19. ^ Van, P., Brezina, M., & Mandel, J. (2001). Convergence of algebraic multigrid based on smoothed aggregation. Numerische Mathematik, 88(3), 559-579.
  20. ^ 森正武. (1986) 有限要素法とその応用. 岩波書店.
  21. ^ 菊池文雄. (1999). 有限要素法概説 [新訂版]. サイエンス社.
  22. ^ 菊池文雄. (1994). 有限要素法の数理. 培風館.
  23. ^ 有限要素法で学ぶ現象と数理―FreeFem++数理思考プログラミング―, 日本応用数理学会 監修・大塚 厚二・高石 武史著, 共立出版.
  • 表
  • 話
  • 編
  • 歴
有限差分法
放物型偏微分方程式
  • FTCSスキーム（英語版）
  • クランク・ニコルソン法（英語版）
双曲型偏微分方程式
  • ラックス・フリードリヒ法（英語版）
  • ラックス・ウェンドロフ法（英語版）
  • マコマック法（英語版）
  • 風上スキーム（英語版）
  • 特性曲線法
その他
有限体積法
  • ゴドノフスキーム（英語版）
  • 高分解能スキーム（英語版）
  • 保存法則用単調性上流中心差分スキーム（英語版）
  • 移流上流分離法（英語版）
  • リーマン解法（英語版）
有限要素法
  • hp-FEM（英語版）
  • 拡張型有限要素法（英語版） (XFEM)
  • 不連続ガラーキン法（英語版） (DG)
  • スペクトル要素法（英語版） (SEM)
  • モルタル有限要素法（英語版）
メッシュフリー法・粒子法
  • SPH法
  • MPS法（英語版）
  • MPM法（英語版）
領域分割法
  • シューア補元法（英語版）
  • 仮想領域法（英語版）
  • シュヴァルツ交代法（加法シュヴァルツ法（英語版）・抽象加法シュヴァルツ法（英語版））
  • ノイマン・ディレクレ法（英語版）
  • ノイマン・ノイマン法（英語版）
  • ポアンカレ・ステクロフ法（英語版）
  • バランシング領域分割法（英語版） (BDD)
  • BDDC法（英語版）
  • FETI法（英語版）
  • FETI-DP法（英語版）
その他