Multigrid methods
From CFD-Wiki
Introduction
The iterative solvers have a tendency to 'stall', that is to stop removing errors after some number of iterations. The problem is more prominent when the meshes are refined or if the meshes are very very fine. For many iterative methods the number of iteration required to converge the solution are linearly proportional to number of nodes in one direction. This behavior could be rooted out to the fact that during the iteration process, the information travels only one grid size per iteration. And for proper convergence the information has to travel back and forward several times.
Since direct matrix inversion is out of the question for realistic problems and the solvers that rely on conjugate-gradient methods have robustness problems associated with them. The methods of choice are point implicit solvers like Gauss-Seidel and Jacobi. Although the Gauss-Seidel scheme rapidly removes local or high-frequency errors in the solution, global or low-frequency errors are reduced at prohitively slow rates, which is inversely related to the grid size.
Multistage solution schemes reduce low frequency errors nicely and this make them ideal solvers when used with combination of good smoothers as Gauss-Seidel solvers.
Classification
Based on the solution approach, multigrid methods are mainly divided into two classes:
- Full Geometric Multigrid or FAS
- Additive Corrective Multigrid
Both of them have lot of things in common.
For each type of multigrid, the coarser grids are generated from finer girds. The approach for generating coarser grids could vary from algorithm to algorithm. For more details see Multigrid coarsening algorithms.
A typical multigrid cycle starts at a finest level. The fine level solution is then transferred to next coarser level, this is called restriction. After some relaxation cycles this coarse level the solution is then restricted to next coarser level until the coarsest level is reached. The solution obtained at the coarsest level is than interpolated back to finer level, this step is called prolongation. The solution from this finer level is interpolated to next finer level after some relaxation iterations, called post multigrid sweeps. The solution is prorogated till the finest level is reached. The whole process is repeated until satisfactory convergence is reached.
