Spectral Preconditioners for High Frequency Wave Propagation Problems

When developing realistic mathematical models for large-scale physical applications, one bottleneck in the procedure is often the efficient and effective solution of the resulting matrix equations. In addition to the inherent difficulties one can encounter in complex applications, we often experience extra difficulties when dealing with time-harmonic wave propagation problems. These difficulties stem from the indefinite or non-self-adjoint nature of the operators involved. This requires a paradigm shift in the design and analysis of solvers. The aim of this project is to build and analyse a new generation of spectral preconditioners based on generalised eigenvalue problems allowing a robust behaviour with respect to the physical properties of the medium. This requires a combination of numerical analysis and spectral analysis tools. The outcome will be both mathematical and practical, as this will fundamentally change the state of the art of solvers, and the results will be incorporated in open-source software.

There is currently a large international research effort dedicated to the efficient numerical solution of frequency-domain (depending on the frequency [lowercase omega]) or time-harmonic PDEs, driven by the fact that in many applications (including EM scattering), the frequency-domain formulation is a viable alternative to the time domain, provided suitably efficient methods are available for solving the large linear systems that arise. Solving this equation is mathematically difficult especially for high-frequency problems.

The growth of the number of degrees of freedom N with [lowercase omega] puts practical 3-d problems out of range of even state-of-the-art direct solvers, and so iterative methods such as (F)GMRES must be used. However, the fact that the systems are indefinite, without a "good" preconditioner, the number of iterations grows rapidly with [lowercase omega]. In this context, "good" means that one wants the number of iterations to ideally be independent of [lowercase omega], and for the preconditioner to be, roughly speaking, as parallelisable as possible. We therefore wish to achieve both parallel scalability together with the robustness with respect to the wave number. Domain decomposition (DD) methods are an attractive choice for preconditioners, since they are inherently parallel and known to be scalable and robust for self-adjoint coercive scalar elliptic PDEs.

For self-adjoint coercive scalar elliptic PDEs there is a fairly well-developed theory for DD methods that allows very general decompositions and coarse grids, but the analysis of DD methods (and other solvers such as multigrid) for indefinite wave problems is largely an open problem. Coarse grids allow global transfer of information in the preconditioner, and increase robustness with respect to the number of the subdomains by achieving parallel scalability. The design of practical coarse spaces for frequency-domain wave problems, however, is still largely open (partly due to the lack of a theoretical framework that allows coarse grids). One approach to obtain practical coarse spaces is to use oscillatory basis functions. However, these basis functions are often eigenfunctions on non-self-adjoint operators and hence difficult to characterize from a mathematical point of view (even when their application to given configurations seems to be successful from a numerical point of view).

The proposed plan of work includes:
-mathematical analysis of spectral non-self-adjoint problems, in particular, such that arise in connection with Dirichlet-to-Neumann operators;
-design of a general theory for a spectral two-level preconditioner;
-numerical assessment and exploitation of the parallel properties on heterogenous benchmark test cases from geophysical and electromagnetic applications.