The AMS website will be down for maintenance on May 23 between 6:00am - 8:00am EDT. For questions please contact AMS Customer Service at or (800) 321-4267 (U.S. & Canada), (401) 455-4000 (Worldwide).


Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Domain decomposition preconditioning for high-frequency Helmholtz problems with absorption

Authors: I. G. Graham, E. A. Spence and E. Vainikko
Journal: Math. Comp. 86 (2017), 2089-2127
MSC (2010): Primary 35J05, 65N55; Secondary 65F08, 65F10, 65N30, 78A45
Published electronically: February 8, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper we give new results on domain decomposition preconditioners for GMRES when computing piecewise linear finite-element approximations of the Helmholtz equation $ -\Delta u - (k^2+ \textup {i} \varepsilon )u = f$, with absorption parameter $ \varepsilon \in \mathbb{R}$. Multigrid approximations of this equation with $ \varepsilon \not = 0$ are commonly used as preconditioners for the pure Helmholtz case ( $ \varepsilon = 0$). However a rigorous theory for such (so-called ``shifted Laplace'') preconditioners, either for the pure Helmholtz equation, or even the absorptive equation ( $ \varepsilon \not =0$), is still missing. We present a new theory for the absorptive equation that provides rates of convergence for (left- or right-) preconditioned GMRES, via estimates of the norm and field of values of the preconditioned matrix. This theory uses a $ k$- and $ \varepsilon $-explicit coercivity result for the underlying sesquilinear form and shows, for example, that if $ \vert\varepsilon \vert\sim k^2$, then classical overlapping Additive Schwarz will perform optimally for the damped problem, provided the subdomain and coarse mesh diameters are carefully chosen. Extensive numerical experiments are given that support the theoretical results. While the theory applies to a certain weighted variant of GMRES, the experiments for both weighted and classical GMRES give comparable results. The theory for the absorptive case gives insight into how its domain decomposition approximations perform as preconditioners for the pure Helmholtz case $ \varepsilon = 0$. At the end of the paper we propose a (scalable) multilevel preconditioner for the pure Helmholtz problem that has an empirical computation time complexity of about $ \mathcal {O}(n^{4/3})$ for solving finite-element systems of size $ n=\mathcal {O}(k^3)$, where we have chosen the mesh diameter $ h \sim k^{-3/2}$ to avoid the pollution effect. Experiments on problems with $ h\sim k^{-1}$, i.e., a fixed number of grid points per wavelength, are also given.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 35J05, 65N55, 65F08, 65F10, 65N30, 78A45

Retrieve articles in all journals with MSC (2010): 35J05, 65N55, 65F08, 65F10, 65N30, 78A45

Additional Information

I. G. Graham
Affiliation: Department of Mathematical Sciences, University of Bath, Bath BA2 7AY, United Kingdom

E. A. Spence
Affiliation: Department of Mathematical Sciences, University of Bath, Bath BA2 7AY, United Kingdom

E. Vainikko
Affiliation: Institute of Computer Science, University of Tartu, 50409, Estonia

Keywords: Helmholtz equation, high frequency, absorption, iterative solvers, preconditioning, domain decomposition, GMRES
Received by editor(s): July 7, 2015
Received by editor(s) in revised form: March 23, 2016
Published electronically: February 8, 2017
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society