マルチグリッド法
マルチグリッド（MG）法は、階層間での多段階の離散化を行うことで、滑らかな解を持つ微分方程式を解くための数値アルゴリズムの手法である[1][2][3][4][5][6]。間隔の異なる格子間での補外[7]と考えることもできる。マルチグリッド法は、主に多次元の楕円型偏微分方程式の数値計算に用いられる[8][9]。
マルチグリッド法は任意の離散化手法と組み合わせることが可能で、漸近的に最も高速な解法のうちの一つである[2][3][4][5][6]。他の手法とは異なり、マルチグリッド法では任意の領域・境界条件を扱うことができる[2][3][4][5][6]。それは微分方程式の性質（たとえば変数分離可能であるかどうかなど）には依存しないからである。マルチグリッド法は、弾性に関するラメの微分方程式やナビエ・ストークス方程式[10][11][12]などの、より複雑な非対称・非線形の問題にもそのまま適用できる[13]。
一般化
マルチグリッド法はさまざまな形に一般化が可能である[2][3][4][5][6]。双曲型偏微分方程式の時間発展解や、時間依存型の偏微分方程式に適用可能である。現在、双曲型方程式への適用について研究が進められている[14]。積分方程式や、統計力学上の問題にも応用が可能である[15][16]。
一方、偏微分方程式や問題の物理現象に由来する性質を仮定せずに、係数行列から多段階の階層を構成することができる。これを代数的マルチグリッド法といい[17][18][19][20]、疎行列を対象としたブラックボックス型のソルバとして利用することができる。
有限要素法[21][22][23][24]は、解の展開基底に線形なウェーブレットを選ぶと、マルチグリッド法に帰着する。
アルゴリズム
いろいろな手法があるが、階層間での離散化を多段階行うところが特徴である[2][3][4][5][6]。
- 緩和 – ガウス・ザイデル法などを数回程度反復実行して、誤差の高周波成分を強く減少させる
- 縮約 – より間隔の粗い格子に対して、残差のダウンサンプリングを行う
- 補間 – 粗い格子上で計算した修正を細かい格子上に補間する
収束率
この手法の利点は、計算に用いるプロセッサの数に正比例して性能が向上する点にある。つまり、指定した精度の近似解を問題のサイズに比例した計算量で求めることができる。そのことを以下で示そう。
密度が
- マルチグリッド法のページへのリンク
