Multigrid preconditioner

The multigrid preconditioner is a key component of the field solver, providing both efficiency and robustness. For an easy accessible introduction to multigrid algorithms, we recommend the German textbook by Andreas Meister, Numerik linearer Gleichungssysteme, Springer Spektrum, 5th edition, (2015).

Mesh levels

At coarser levels, the meshes are generated by successively coarsening the resolution by factors of two. This process is controlled by the lvl parameter during mesh creation, where lvl=1 corresponds to the finest mesh. As the mesh is coarsened, the discrete boundary is also adapted, wrapping around the continuous boundary as closely as possible. Otherwise, the discrete elliptic operators are built in the same fashion, except for coarsened mesh distance.

Meshes at progressively coarser levels (blue -> green -> red). The adjustment of the discrete boundary shape is also highlighted.

The following operators are used for weighted restriction and prolongation for interior points: $$\begin{align} R = \begin{pmatrix} \tfrac{1}{16} &\tfrac{1}{8} & \tfrac{1}{16} \\ \tfrac{1}{8} &\tfrac{1}{4} & \tfrac{1}{8} \\ \tfrac{1}{16} &\tfrac{1}{8} & \tfrac{1}{16} \end{pmatrix}, \quad P = \begin{pmatrix} \tfrac{1}{4} &\tfrac{1}{2} & \tfrac{1}{4} \\ \tfrac{1}{2} & 1 & \tfrac{1}{2} \\ \tfrac{1}{4} &\tfrac{1}{2} & \tfrac{1}{4} \end{pmatrix} \end{align}$$ Near the boundaries, where neighboring points may not be available, these operators are adjusted accordingly. For details on how these adaptations are implemented, please refer to the source code. ​

Smoothers

Another key component of the multigrid algorithm is the smoother. PARALLAX supports both Jacobi and Gauss-Seidel smoothers, with the red-black Gauss-Seidel smoother being the most commonly used. This smoother exploits the five-point stencil of the elliptic problem, where grid points are divided into red and black sets in a checkerboard pattern. Additionally, boundary and ghost points are treated as further separate independent sets. The algorithm alternates between updating the red, black, boundary, and ghost points. This separation into independent sets enables efficient parallelization using OpenMP, improving the overall performance of the smoother.

Multigrid algorithm

The multigrid algorithm in PARALLAX is implemented based on the scheme outlined on page 137 of Andreas Meister's above mentioned book. A distinction is that boundary values are explicitly set after the prolongation step. On the coarsest level, a sparse direct solver is used. The number of pre- and post-smoothing steps, along with other relevant parameters, are configured through the variables of the parameters_helmholtz_solver_factory type.

Usage within the code

The multigrid object encompasses the meshes for all coarseness levels, along with the associated restriction and prolongation operators. It is created using the following call:

call multigrid%init(equi, phi, nlvls, spacing_f, size_neighbor, size_ghost_layer, mesh_finest)

Here, nlvls specifies the number of coarseness levels, and spacing_f defines the mesh distance on the finest level. The other parameters correspond to those used when creating the mesh. Notably, this call also returns a pointer to the finest-level mesh, which eliminates the need for an additional mesh creation call and prevents storing the finest mesh twice in memory.

Once initialized, the multigrid object is used directly when creating the field solver, and no further interaction with the multigrid object is necessary.