Accelerating the shifted Laplace preconditioner for the Helmholtz equation by multilevel deflation

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.