On the Spectrum of Deflated Matrices with Applications to the Deflated Shifted Laplace Preconditioner for the Helmholtz Equation
Luis García Ramos, Reinhard Nabben · SIAM Journal on Matrix Analysis and Applications · 2018
The deflation technique for accelerating Krylov subspace iterative methods for the solution of linear systems has long been well established. The first landmark papers of Nicolaides and Dostál date back to the late 1980s, where deflation is used for Hermitian positive definite (HPD) linear systems. In the last decade deflation has been used and analyzed in combination with domain decomposition and multigrid methods, leading to very efficient algorithms. Examples are the multilevel Krylov methods introduced by Erlangga and Nabben, and the works of Sheikh et al. in which multilevel deflation techniques are presented. Although these algorithms work very well in practice for non-Hermitian problems, not many theoretical results are yet known for this class of problems. We study here the general case of deflation operators in arbitrary inner products, and give inclusion regions for the spectrum of an arbitrary deflated matrix based on the field of values. The new inclusion regions generalize previous results for HPD matrices. Moreover, we give a bound based on the field of values for the norms of the residuals of deflated GMRES. We apply our results to linear systems arising from the Helmholtz equation, focusing on the combination of the complex shifted Laplace (CSL) preconditioner with a two-level deflation preconditioner, which is the basis of a multilevel method introduced by Erlangga and Nabben. The analysis here only covers the case of exact inversion of the CSL preconditioner. It has been observed in numerical experiments that the eigenvalues of the deflated CSL-preconditioned system lie on the exact same disks as the CSL-preconditioned linear systems and are shifted away from zero. Here we are able to prove these surprising results for a class of problems with Dirichlet and first-order Sommerfeld boundary conditions. Our results help to explain the high performance of multilevel Krylov methods based on deflation for the Helmholtz equation.