Iterative linear solvers - theory and best practice

Discretisation of partial differential equations (PDEs) in the framework of the Finite Volume Method (FVM) typically produces very large sparse matrices with a small number of nonzero entries. Choice of an appropriate solver is stronly related to the discretisation method, i.e. matrix properties. Most linear solvers have the optimal performance for certain types of matrices: diagonally dominant, symmetric and positive-definite. Simple iterative solvers such as Jacobi and Gauss-Seidel operate in a point-by-point manner and incrementally improve the solution. Thus, in an N-dimensional space of an N by N matrix, fixed-point methods visit each direction of the N-dimensional space separately. On the other hand, Krylov subspace methods, such as Generalised Minimal Residual (GMRES) and Conjugate Gradient (CG) methods and its variants, choose the solution direction by evaluating the residual and searching for its smallest components. The most powerful class of iterative linear solvers are the multigrid methods. They were originally created for systems of discretised elliptic PDEs but were later expanded and have proven to be efficient for general types of PDEs. Multigrid methods exploit the fact that beforementioned point-fixed methods tend to quickly reduce the high frequency solution errors, i.e. the erorrs whose direction corresponds to the largest eigenvalues of the matrix. However, the low frequency errors remain and this is why the performance (convergence) of the fixed-point methods deteriorates. To solve this issue, multigrid methods construct a hierarchy of grids by coarsening the initial grid. The low frequency errors of the finer grid become high frequency errors on the coarser grid and the fixed-point algorithms are able to efficiently reduce these errors.

In this teaching session, an overview of the beforementioned methods will be given as well as optimal setup for specific equations.