Domain decomposition preconditioning for high-frequency Helmholtz problems with absorption

DOI10.1090/MCOM/3190MaRDI QIDQ2981770zbMATH OpenOpenAlexFDO

Authors Eero Vainikko, I. G. Graham, E. A. Spence

Publication date 10 May 2017

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.02097

zbMATH Keywords

numerical experimentsHelmholtz equationdomain decomposition preconditioners

Mathematics Subject Classification ID

Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Preconditioners for iterative methods (65F08) Iterative numerical methods for linear systems (65F10) Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs (65N30)

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 $-Deltau-(k^2+mivarepsilon)u=f$, with absorption parameter $varepsiloninmathbbR$. Multigrid approximations of this equation with $varepsilonot=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 ($varepsilonot=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 $|varepsilon|sim{k}^2$, then classical overlapping additive Schwarz will perform optimally for the absorptive problem, provided the subdomain and coarse mesh diameters are carefully chosen. Extensive numerical experiments are given that support the theoretical 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 $mathcalO(n^{4/3})$ for solving finite element systems of size $n=mathcalO(k^3)$, where we have chosen the mesh diameter $hsim{k}^{-3/2}$ to avoid the pollution effect. Experiments on problems with $hsim{k}^{-1}$, i.e. a fixed number of grid points per wavelength, are also given.

Recommendations

• Recent results on domain decomposition preconditioning for the high-frequency Helmholtz equation using absorption
• Domain decomposition with local impedance conditions for the Helmholtz equation with absorption
• Domain decomposition preconditioners for high-order discretizations of the heterogeneous Helmholtz equation
• Domain decomposition preconditioning for the high-frequency time-harmonic Maxwell equations with absorption
• A robust multilevel preconditioner based on a domain decomposition method for the Helmholtz equation

Cites work

• scientific article; zbMATH DE number 5963475 (Why is no real title available?)
• scientific article; zbMATH DE number 4138299 (Why is no real title available?)
• scientific article; zbMATH DE number 2113718 (Why is no real title available?)
• A Comparison of Deflation and Coarse Grid Correction Applied to Porous Media Flow
• A Novel Multigrid Based Preconditioner For Heterogeneous Helmholtz Problems
• A Restricted Additive Schwarz Preconditioner for General Sparse Linear Systems
• A domain decomposition method for the Helmholtz equation and related optimal control problems
• A rapidly converging domain decomposition method for the Helmholtz equation
• A source transfer domain decomposition method for Helmholtz equations in unbounded domain
• A source transfer domain decomposition method for Helmholtz equations in unbounded domain, part II: extensions
• Advances in iterative methods and preconditioners for the Helmholtz equation
• An optimized Schwarz method with two-sided Robin transmission conditions for the Helmholtz equation
• Applying GMRES to the Helmholtz equation with shifted Laplacian preconditioning: What is the largest shift for which wavenumber-independent convergence is guaranteed?
• Balancing domain decomposition for problems with large jumps in coefficients
• Domain Decomposition Algorithms for Indefinite Elliptic Problems
• Domain decomposition for multiscale PDEs
• Elliptic boundary value problems on corner domains. Smoothness and asymptotics of solutions
• Finite Element Interpolation of Nonsmooth Functions Satisfying Boundary Conditions
• Iterative methods for linear systems. Theory and applications
• Local Fourier analysis of the complex shifted Laplacian preconditioner for Helmholtz problems.
• On a class of preconditioners for solving the Helmholtz equation
• On the convergence of shifted Laplace preconditioner combined with multilevel deflation.
• Optimal left and right additive Schwarz preconditioning for minimal residual methods with Euclidean and energy norms
• Optimized Schwarz Methods without Overlap for the Helmholtz Equation
• Optimized Schwarz methods for Maxwell's equations
• Overlapping Schwarz preconditioners for indefinite time harmonic Maxwell equations
• Overview of variational formulations for linear elliptic PDEs
• Recent results on domain decomposition preconditioning for the high-frequency Helmholtz equation using absorption
• Restricted overlapping balancing domain decomposition methods and restricted coarse problems for the Helmholtz problem
• Robust domain decomposition algorithms for multiscale PDEs
• Some Remarks on the Elman Estimate for GMRES
• Some observations on the l² convergence of the additive Schwarz preconditioned GMRES method
• Some observations on weighted GMRES
• Spectral Analysis of the Discrete Helmholtz Operator Preconditioned with a Shifted Laplacian
• Sweeping preconditioner for the Helmholtz equation: hierarchical matrix representation
• The method of polarized traces for the 2D Helmholtz equation
• Variational Iterative Methods for Nonsymmetric Systems of Linear Equations
• Weighted FOM and GMRES for solving nonsymmetric linear systems
• When is the error in the \(h\)-BEM for solving the Helmholtz equation bounded independently of \(k\)?
• Why it is difficult to solve Helmholtz problems with classical iterative methods

Cited in

(55)

• Scalable multi-level deflation preconditioning for highly indefinite time-harmonic waves
• Finite element method and its analysis for a nonlinear Helmholtz equation with high wave numbers
• Analysis of the SORAS domain decomposition preconditioner for non-self-adjoint or indefinite problems
• Comparing domain decomposition preconditioners for non-conforming Helmholtz discretizations
• Domain decomposition with local impedance conditions for the Helmholtz equation with absorption
• Parallel controllability methods for the Helmholtz equation
• A two-level domain-decomposition preconditioner for the time-harmonic Maxwell's equations
• An example of explicit implementation strategy and preconditioning for the high order edge finite elements applied to the time-harmonic Maxwell's equations
• Can coercive formulations lead to fast and accurate solution of the Helmholtz equation?
• Analysis of a Helmholtz preconditioning problem motivated by uncertainty quantification
• A unified framework for double sweep methods for the Helmholtz equation
• Stability and finite element error analysis for the Helmholtz equation with variable coefficients
• Analysis of the shifted Helmholtz expansion preconditioner for the Helmholtz equation
• A hybrid two-level weighted Schwarz method for Helmholtz equations
• Substructured two-grid and multi-grid domain decomposition methods
• How large a shift is needed in the shifted Helmholtz preconditioner for its effective inversion by multigrid?
• Preconditioning the Helmholtz equation with the shifted Laplacian and Faber polynomials
• Two-level preconditioners for the Helmholtz equation
• A parallel-in-time implementation of the Numerov method for wave equations
• Robust Superlinear Krylov Convergence for Complex Noncoercive Compact-Equivalent Operator Preconditioners
• On the spectrum of deflated matrices with applications to the deflated shifted Laplace preconditioner for the Helmholtz equation
• Recent results on domain decomposition preconditioning for the high-frequency Helmholtz equation using absorption
• A non-overlapping domain decomposition method with high-order transmission conditions and cross-point treatment for Helmholtz problems
• Fast alternating bidirectional preconditioner for the 2D high-frequency Lippmann-Schwinger equation
• Multilevel optimized Schwarz methods
• Applying GMRES to the Helmholtz equation with shifted Laplacian preconditioning: What is the largest shift for which wavenumber-independent convergence is guaranteed?
• Bi-parametric operator preconditioning
• Analysis of Schwarz Methods for Convected Helmholtz-Like Equations
• PinT Preconditioner for Forward-Backward Evolutionary Equations
• Two-level restricted additive Schwarz preconditioner based on multiscale spectral generalized FEM for heterogeneous Helmholtz problems
• Restrictions on the use of sweeping type preconditioners for Helmholtz problems
• A non-overlapping domain decomposition method with perfectly matched layer transmission conditions for the Helmholtz equation
• Convergence theory for two-level hybrid Schwarz preconditioners for high-frequency Helmholtz problems
• GenEO coarse spaces for heterogeneous indefinite elliptic problems
• Parallel domain decomposition solvers for the time harmonic Maxwell equations
• Several ways to achieve robustness when solving wave propagation problems
• A comparison of coarse spaces for Helmholtz problems in the high frequency regime
• An adaptive multigrid solver for DPG methods with applications in linear acoustics and electromagnetics
• A fast block -circulant preconditoner for all-at-once systems from wave equations
• Absolute-value based preconditioner for complex-shifted Laplacian systems
• A non-overlapping Schwarz domain decomposition method with high-order finite elements for flow acoustics
• Domain decomposition preconditioning for the high-frequency time-harmonic Maxwell equations with absorption
• A Sign-Definite Preconditioned High-Order FEM, Part I: Formulation and Simulation for Bounded Homogeneous Media Wave Propagation
• On the Dirichlet-to-Neumann coarse space for solving the Helmholtz problem using domain decomposition
• A coercive heterogeneous media Helmholtz model: formulation, wavenumber-explicit analysis, and preconditioned high-order FEM
• Two-level hybrid Schwarz preconditioners for the Helmholtz equation with high wave number
• A robust and adaptive GenEO-type domain decomposition preconditioner for \(\mathbf{H(curl})\) problems in three-dimensional general topologies
• Scalable DPG multigrid solver for Helmholtz problems: a study on convergence
• Scalable convergence using two-level deflation preconditioning for the Helmholtz equation
• A hybrid two-level weighted Schwarz method for time-harmonic Maxwell equations
• A two-grid method with dispersion matching for finite-element Helmholtz problems
• On a sharp estimate of overlapping Schwarz methods in \(\boldsymbol{H}(\mathbf{curl}; \Omega)\) and \(\boldsymbol{H}(\mathrm{div}; \Omega)\)
• Matrix-free parallel scalable multilevel deflation preconditioning for heterogeneous time-harmonic wave problems
• Domain decomposition preconditioners for high-order discretizations of the heterogeneous Helmholtz equation
• High-order FEM domain decomposition models for high-frequency wave propagation in heterogeneous media

This page was built for publication: Domain decomposition preconditioning for high-frequency Helmholtz problems with absorption

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2981770)