Multigrid
Multigrid is a general class of algorithms to solve partial differential equations, elliptic and parabolic ones such as Poisson's equation for self-gravity and diffusion-like equations in particular. Among many variants of Multigrid solvers, Athena++ adopts a simple geometric multigrid using cell-centered discretization. To learn practical usage with self-gravity, see [Self-Gravity with Multigrid].
Because Multigrid inherently involves global (i.e. over more than one MeshBlock) operations, the Multigrid solver consists of two components: MultigridDriver which contains global properties and controls the progress of the solver, and Multigrid which contains actual data. Roughly speaking, MultigridDriver corresponds to Mesh, which Multigrid corresponds to MeshBlock. This design is similar to FFT.
Although currently only self-gravity solver is implemented, the Multigrid solver is extensible to other physical processes. In order to achieve maximum flexibility, the actual solver is implemented as derived classes of MultigridDriver and Multigrid. While the base classes implement operations and data common to all physics, the derived classes implement operations and data specific to each physical process.
The solver works as follows. When MultigridDriver::Solver (a pure virtual function) is called, it loads the source function data (e.g. the density distribution for self-gavity) from MeshBlock to Multigrid objects. Then it sets up the data on the Multigrid hierarchy and runs the algorithm on it. Once the solution is obtained, it returns the data (e.g. the gravitational potential for self-gravity) to MeshBlock. Then the solution can be used in the integrator to update physical quantities. In the present implementation, Athena++ calls Multigrid at every subsycle so that the solution can be used in the time integrator without algorithmic complication and loss of the time accuracy.
The implemented algorithms are based on a textbook (U. Trottenberg, C. W. Osterlee and A. Schuller, Multigrid, 2000, Academic Press). This is a good, comprehensive and practical textbook. If you want to learn Multigrid and/or implement something on it, I highly recommend this textbook.
Currently two cycle modes are provided. One is "MGI (MultiGrid Iteration)" mode, which uses standard V-cycles iterations (left in the figure). In this mode, the solver starts from the finest level, and applies smoothing operations on each level by reducing the resolution (restriction). When it reaches the coarsest level, it calculates the solution on that level either analytically or numerically (anyway the cost is small), and then goes back the hierarchy to the finer levels (prolongation), applying smoothing operations on each level. Once it reaches the finest level, the residual is measured, and it repeats the process until the required accuracy is achieved or the convergence stalls. This mode requires a good initial guess to achieve fast and robust convergence. Each sweep typically reduces the error by a factor of 7-10 depending on physics and grid structures.
The other is "FMG (Full MultiGrid)" mode. In this mode, the solver stars from the coarsest level. On the coarsest level, the solution can be easily obtained either analytically or numerically. Then the solver interpolates the coarse grid solution to the finer grid, and uses it as an initial guess for the finer level. This FMG prolongation requires higher order interpolation than the prolongation in the normal V-cycle explained above. Then, it applies V-cycle once to improve the solution. It goes down to the finer levels applying the FMG prolongation and V-cycle on each level. Once it reaches the finest level, the residual is measured, and additional V-cycles are applied until the required accuracy is achieved or the convergence stalls. In general, this mode is superior to the MGI mode (i.e. faster and more robust), because it does not require any initial guess and it usually achieves reasonably good convergence even in the first sweep.
Currently, our restriction algorithm is simple volume-weighted average, prologantion is tri-linear interpolation which is second-order accurate, and FMG prolongation is tri-cubic interpolation. Overall, the solution should be second-order accurate as long as it is sufficiently converged.
The smoothing operation depends on physics, and currently the Red-Black Gauss-Seidel smoother is implemented for self-gravity.