マルチグリッド法

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

マルチグリッド（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}$ の格子 $i$ 上で、微分方程式の近似解を（与えられた精度まで）求めることを考える。 $K$ を格子上での解の計算に関する定数、また隣り合う格子の密度の比 $\rho =N_{j+1}/N_{j}<1$ は常に一定であるとする。格子 $i+1$ の解を用いて、格子 $i$ 上での解が $W_{i}=\rho KN_{i}$ の計算量で求められるとすると、

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

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

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

の関係が格子 $k$ 上での計算量に関して成り立つ。これらと $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 }}

であるから、 $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 .

脚注

^ ^a ^b ^c ^d ^e Wolfgang Hackbusch: Multi-Grid Methods and Applications, Springer, ISBN 978-3-642-05722-9 (1985).
^ ^a ^b ^c ^d ^e McCormick, S. F. (Ed.). (1987). Multigrid methods. Society for Industrial and Applied Mathematics.
^ ^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.
^ ^a ^b ^c ^d ^e Yavneh, I. (2006). Why multigrid methods are so efficient. Computing in science & engineering, 8(6), 12-22.
^ ^a ^b ^c ^d ^e Bramble, J. H. (2018). Multigrid methods. Routledge.
^ Brezinski, C., & Zaglia, M. R. (2013). Extrapolation methods: theory and practice. Elsevier.
^ 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.
^ Fulton, S. R., Ciesielski, P. E., & Schubert, W. H. (1986). Multigrid methods for elliptic problems: A review. Monthly Weather Review, 114(5), 943-959.
^ Constantin, P., & Foias, C. (1988). Navier-stokes equations. University of Chicago Press.
^ Temam, R. (2001). Navier-Stokes equations: theory and numerical analysis (Vol. 343). American Mathematical Society.
^ Foias, C., Manley, O., Rosa, R., & Temam, R. (2001). Navier-Stokes equations and turbulence (Vol. 83). Cambridge University Press.
^ Henson, V. E. (2002). Multigrid methods for nonlinear problems: an overview (Vol. 5016, No. UCRL-JC-150259). Lawrence Livermore National Lab., CA (US).
^ Katzer, E. (1991). Multigrid methods for hyperbolic equations. In Multigrid methods III (pp. 253-263). Birkhäuser, Basel.
^ Schippers, H. (1982). Application of multigrid methods for integral equations to two problems from fluid dynamics. Journal of Computational Physics, 48(3), 441-461.
^ 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.
^ Notay, Y. (2010). An aggregation-based algebraic multigrid method. Electronic transactions on numerical analysis, 37(6), 123-146.
^ 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.
^ Napov, A., & Notay, Y. (2012). An algebraic multigrid method with guaranteed convergence rate. SIAM journal on scientific computing, 34(2), A1079-A1109.
^ Van, P., Brezina, M., & Mandel, J. (2001). Convergence of algebraic multigrid based on smoothed aggregation. Numerische Mathematik, 88(3), 559-579.
^ 森正武. (1986) 有限要素法とその応用. 岩波書店.
^ 菊池文雄. (1999). 有限要素法概説 [新訂版]. サイエンス社.
^ 菊池文雄. (1994). 有限要素法の数理. 培風館.
^ 有限要素法で学ぶ現象と数理―FreeFem++数理思考プログラミング―, 日本応用数理学会監修・大塚厚二・高石武史著, 共立出版.

[wolf-1] Wolfgang Hackbusch: Multi-Grid Methods and Applications, Springer, ISBN 978-3-642-05722-9 (1985).

[mc-2] McCormick, S. F. (Ed.). (1987). Multigrid methods. Society for Industrial and Applied Mathematics.

[ht-3] Hackbusch, W., & Trottenberg, U. (Eds.). (2006). Multigrid methods: proceedings of the conference held at Köln-Porz, November 23-27, 1981 (Vol. 960). Springer.

[why-4] Yavneh, I. (2006). Why multigrid methods are so efficient. Computing in science & engineering, 8(6), 12-22.

[bra-5] 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.

[mori-20] 森正武. (1986) 有限要素法とその応用. 岩波書店.

[kikuchi1999-21] 菊池文雄. (1999). 有限要素法概説 [新訂版]. サイエンス社.

[kikuchi1994-22] 菊池文雄. (1994). 有限要素法の数理. 培風館.

[freefem-23] 有限要素法で学ぶ現象と数理―FreeFem++数理思考プログラミング―, 日本応用数理学会監修・大塚厚二・高石武史著, 共立出版.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

マルチグリッド法

一般化

アルゴリズム

収束率

関連項目

参考文献

関連文献

脚注