Linear systems with a singular symmetric positive semi-definite matrix appear frequently in practice. This usually does not lead to difficulties for CG methods as long as these systems are consistent. However, the construction of a preconditioner, especially the construction of two-level and multilevel methods, becomes more complicated, since singular coarse grid matrices or Galerkin matrices may occur. Here we continue the work started in [21,22] where deflation is used for some special singular coefficient matrices. Here we show that deflation and other projection-type preconditioners can be applied to arbitrary singular problems without any difficulties. In each of these methods, a two-level preconditioner is involved where coarse-grid systems based on a singular Galerkin matrix should be solved. We prove that each projection operator consisting of a singular Galerkin matrix can be written as an operator with a nonsingular Galerkin matrix. Therefore many results that hold for nonsingular Galerkin matrices are also valid for problems with singular Galerkin matrices.@en

Many important physical phenomena can be described by the Helmholtz equation. We investigate to what extent the convergence of the shifted Laplacian preconditioner for the Helmholtz equation can be accelerated using deflation with multigrid vectors. We therefore present a unified framework for two published algorithms. The first deflates the preconditioned operator and requires no further preconditioning. The second deflates the original operator and combines deflation and preconditioning in a multiplicative fashion. We pursue two scientific contributions. First we show, using a model problem analysis, that both algorithms cluster the eigenvalues. The new and key insight here is that the near-kernel of the coarse grid operator causes a limited set of eigenvalues to shift away from the center of the cluster with a distance proportional to the wave number. This effect is less pronounced in the first algorithmic variant at the expense of a higher computational cost. In the second contribution we quantify for the first time the large amount of reduction in CPU-time that results from the clustering of eigenvalues and the reduction in iteration count. We report to this end on the findings of an implementation in PETSc on two and three-dimensional problems with constant and variable wave number. @en