マルチグリッド法

マルチグリッド（MG）法は、階層間での多段階の離散化を行うことで、滑らかな解を持つ微分方程式を解くための数値アルゴリズムの手法であるWilliam L. Briggs: A Multigrid Tutorial, SIAM, ISBN 0-89871-221-1 (1987).Wolfgang Hackbusch: Multi-Grid Methods and Applications, Springer, ISBN 978-3-642-05722-9 (1985).McCormick, S. F. (Ed.). (1987). Multigrid methods. Society for Industrial and Applied Mathematics.Hackbusch, W., & Trottenberg, U. (Eds.). (2006). Multigrid methods: proceedings of the conference held at Köln-Porz, November 23-27, 1981 (Vol. 960). Springer.Yavneh, I. (2006). Why multigrid methods are so efficient. Computing in science & engineering, 8(6), 12-22.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++数理思考プログラミング―, 日本応用数理学会 監修・大塚 厚二・高石 武史著, 共立出版.は、解の展開基底に線形なウェーブレットを選ぶと、マルチグリッド法に帰着する。

 アルゴリズム 
いろいろな手法があるが、階層間での離散化を多段階行うところが特徴である。
 緩和 – ガウス・ザイデル法などを数回程度反復実行して、誤差の高周波成分を強く減少させる
 縮約 – より間隔の粗い格子に対して、残差のダウンサンプリングを行う
 補間 – 粗い格子上で計算した修正を細かい格子上に補間する

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

密度がの格子上で、微分方程式の近似解を（与えられた精度まで）求めることを考える。を格子上での解の計算に関する定数、また隣り合う格子の密度の比は常に一定であるとする。格子の解を用いて、格子上での解がの計算量で求められるとすると、

特に最も細かい格子に関して

の関係が格子上での計算量に関して成り立つ。これらとの関係から、

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

であるから、の計算量により解が得られることが分かる。

 関連項目 
 数値解析
 偏微分方程式の数値解法
 有限要素法
 差分法
 スペクトル法
 領域分割法

 参考文献 
 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-1-58488492-7 (2004年).
 Copper Mountain Conference on Multigrid Methods (Multigrid Conference materials) GitHub

脚注

Category:数値解析
Category:数値微分方程式
Category:数学に関する記事