This is joint work with Paul Childs (Schlumberger Gould Research, Cambridge), Martin Gander (Geneva), Euan Spence (Bath), Douglas Shanks (Bath) and Eero Vainikko (Tartu).
As a model problem for high-frequency wave scattering, we study the Helmholtz equation in a bounded, dd-dimensional domain subject to an impedance boundary condition. Our results also apply to sound-soft scattering problems in truncated exterior domains. Finite element approximations of this problem for high wavenumber kk are notoriously hard to solve. The analysis of Krylov space-based iterative solvers such as GMRES is also hard, since the corresponding system matrices are complex, non-Hermitian and usually highly non-normal, so information about spectra and condition numbers of the system matrices generally does not give much information about the convergence rate of iterative methods.
Quite a lot of recent research has focussed on preconditioning using an approximate solution of the shifted Laplace problem, in which the original PDE and boundary condition are modified by the addition of certain lower-order terms involving an absorption parameter ϵ>0ϵ>0. Let AA and AϵAϵ denote the system matrices for discretizations of the original and modified problems, respectively, and let B−1ϵBϵ−1 denote any (practically useful) approximate inverse for AϵAϵ. It is easy to see that sufficient conditions for B−1ϵBϵ−1 to be a good GMRES preconditioner for AA are: (i) A−1ϵAϵ−1 should be a good preconditioner for AA and (ii) B−1ϵBϵ−1 should be a good preconditioner for AϵAϵ. It is generally observed that (i) holds if the ϵϵ is not taken too large, while (ii) holds (e.g., for geometric multigrid) provided ϵϵ is large enough. However there is no rigorous explanation for these observations.
The first part of the talk will explore sufficient conditions on ϵϵ so that (i) holds. This uses techniques from PDE analysis in the high frequency case, in particular the application of Morawetz multiplier theory. These theoretical tools allow matrix estimates applicable in numerical linear algebra.
In the second part of the talk we consider requirement (ii), analysing the case when B−1ϵBϵ−1 is defined by classical additive Schwarz domain decomposition methods. The analysis here is quite different from the classical analysis of Cai and Widlund, which does not allow kk to become large. Here we use a coercivity argument in the natural kk-dependent energy norm to estimate the field of values of the preconditioned matrix. This analysis holds
for kk arbitrarily large.
The analysis shows that there is a gap between the ranges of ϵϵ which ensure conditions (i) and (ii). Practical exploration of the performance of the solver in the gap suggests that efficient algorithms can still be constructed for solving this problem with high wavenumber kk using several variants of classical domain decomposition methods. New directions for future analysis are also suggested by the experiments.