A class of iterative solvers for the Helmholtz equation: factorizations, sweeping preconditioners, source transfer, single layer potentials, polarized traces, and optimized Schwarz methods
From MaRDI portal
Publication:4621282
DOI10.1137/16M109781XzbMATH Open1417.65216arXiv1610.02270OpenAlexW2963292939WikidataQ114074326 ScholiaQ114074326MaRDI QIDQ4621282FDOQ4621282
Publication date: 11 February 2019
Published in: SIAM Review (Search for Journal in Brave)
Abstract: Solving time-harmonic wave propagation problems by iterative methods is a difficult task, and over the last two decades, an important research effort has gone into developing preconditioners for the simplest representative of such wave propagation problems, the Helmholtz equation. A specific class of these new preconditioners are considered here. They were developed by researchers with various backgrounds using formulations and notations that are very different, and all are among the most promising preconditioners for the Helmholtz equation. The goal of the present manuscript is to show that this class of preconditioners are based on a common mathematical principle, and they can all be formulated in the context of domain decomposition methods called optimized Schwarz methods. This common formulation allows us to explain in detail how and why all these methods work. The domain decomposition formulation also allows us to avoid technicalities in the implementation description we give of these recent methods. The equivalence of these methods with optimized Schwarz methods translates at the discrete level into equivalence with approximate block LU decomposition preconditioners, and we give in each case the algebraic version, including a detailed description of the approximations used. While we chose to use the Helmholtz equation for which these methods were developed, our notation is completely general and the algorithms we give are written for an arbitrary second order elliptic operator. The algebraic versions are even more general, assuming only a connectivity pattern in the discretization matrix.
Full work available at URL: https://arxiv.org/abs/1610.02270
Recommendations
- Advances in iterative methods and preconditioners for the Helmholtz equation
- Iterative Solution of the Helmholtz Equation by a Second-Order Method
- Sweeping preconditioner for the Helmholtz equation: hierarchical matrix representation
- A new time-based iterative solver for linear standing-wave problems
- Additive sweeping preconditioner for the Helmholtz equation
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) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22)
Cites Work
- A parallel multigrid-based preconditioner for the 3D heterogeneous high-frequency Helmholtz equation
- Recent work on sharp estimates in second-order elliptic unique continuation problems
- Well-Posedness of One-Way Wave Equations and Absorbing Boundary Conditions
- A coarse space for heterogeneous Helmholtz problems based on the Dirichlet-to-Neumann operator
- Improved transmission conditions for a one-dimensional domain decomposition method applied to the solution of the Helmholtz equation
- Best Robin Parameters for Optimized Schwarz Methods at Cross Points
- Condition Number Estimates for the Nonoverlapping Optimized Schwarz Method and the 2-Lagrange Multiplier Method for General Domains and Cross Points
- Local Fourier analysis of the complex shifted Laplacian preconditioner for Helmholtz problems
- On the convergence of shifted Laplace preconditioner combined with multilevel deflation
- Efficient Scalable Algorithms for Solving Dense Linear Systems with Hierarchically Semiseparable Structures
- On the Relation Between Optimized Schwarz Methods and Source Transfer
- A source transfer domain decomposition method for Helmholtz equations in unbounded domain
- Optimized double sweep Schwarz method by complete radiation boundary conditions
- Optimized Schwarz Method with Complete Radiation Transmission Conditions for the Helmholtz Equation in Waveguides
- On a Parallel Robin‐Type Nonoverlapping Domain Decomposition Method
- Title not available (Why is that?)
- Acoustic inverse scattering via Helmholtz operator factorization and optimization
- Title not available (Why is that?)
- Factorization of linear elliptic boundary value problems in non-cylindrical domains
- Analysis of a fast method for solving the high frequency Helmholtz equation in one dimension
- On a multilevel Krylov method for the Helmholtz equation preconditioned by shifted Laplacian
- Near-optimal perfectly matched layers for indefinite Helmholtz problems
- An improved two-grid preconditioner for the solution of three-dimensional Helmholtz problems in heterogeneous media
- A new level-dependent coarse grid correction scheme for indefinite Helmholtz problems
- Optimal Interface Conditions for an Arbitrary Decomposition into Subdomains
- A Source Transfer Domain Decomposition Method for Helmholtz Equations in Unbounded Domain Part II: Extensions
- A Multigrid Method for the Helmholtz Equation with Optimized Coarse Grid Corrections
- The method of polarized traces for the 2D Helmholtz equation
- Numerical experiments on a domain decomposition algorithm for nonlinear elliptic boundary value problems
- Wideband nested cross approximation for Helmholtz problems
- An improved sweeping domain decomposition preconditioner for the Helmholtz equation
- A double-sweeping preconditioner for the Helmholtz equation
- Additive sweeping preconditioner for the Helmholtz equation
- Approximate Separability of the Green's Function of the Helmholtz Equation in the High Frequency Limit
- Artificial damping techniques for scalar waves in the frequency domain
- Sparsifying Preconditioner for the Lippmann--Schwinger Equation
- How Large a Shift is Needed in the Shifted Helmholtz Preconditioner for its Effective Inversion by Multigrid?
- A New Coarse Grid Correction for RAS/AS
- Discontinuous Coarse Spaces for DD-Methods with Discontinuous Iterates
- On Nilpotent Subdomain Iterations
- SHEM: An Optimal Coarse Space for RAS and Its Multiscale Approximation
- A robust domain decomposition method for the Helmholtz equation with high wave number
- Fundamental solutions to some elliptic equations with discontinuous senior coefficients and an inequality for these solutions
- Optimized Schwarz methods with overlap for the Helmholtz equation
- Nested Domain Decomposition with Polarized Traces for the 2D Helmholtz Equation
- Recursive sweeping preconditioner for the three-dimensional Helmholtz equation
- Recent Results on Domain Decomposition Preconditioning for the High-Frequency Helmholtz Equation Using Absorption
- A convergence analysis for a sweeping preconditioner for block tridiagonal systems of linear equations
- Fast alternating bidirectional preconditioner for the 2D high-frequency Lippmann-Schwinger equation
- Title not available (Why is that?)
- Analysis of Schwarz Methods for a Hybridizable Discontinuous Galerkin Discretization
- Optimized Additive Schwarz with Harmonic Extension as a Discretization of the Continuous Parallel Schwarz Method
- Sparsify and Sweep: An Efficient Preconditioner for the Lippmann--Schwinger Equation
- Restrictions on the Use of Sweeping Type Preconditioners for Helmholtz Problems
- An overview of SuperLU
- Algorithm 832
- A fully asynchronous multifrontal solver using distributed dynamic scheduling
- Direct Methods for Sparse Linear Systems
- Title not available (Why is that?)
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- Existence of \(\mathcal H\)-matrix approximants to the inverse FE-matrix of elliptic operators with \(L^\infty\)-coefficients
- A sparse \({\mathcal H}\)-matrix arithmetic. II: Application to multi-dimensional problems
- Nested Dissection of a Regular Finite Element Mesh
- Hierarchical matrices. A means to efficiently solve elliptic boundary value problems
- Acoustic and electromagnetic equations. Integral representations for harmonic problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- Unified Analysis of Discontinuous Galerkin Methods for Elliptic Problems
- A Restricted Additive Schwarz Preconditioner for General Sparse Linear Systems
- Title not available (Why is that?)
- A perfectly matched layer for the absorption of electromagnetic waves
- Numerical solution of elliptic differential equations by reduction to the interface.
- The analysis of matched layers
- Absorbing Boundary Conditions for the Numerical Simulation of Waves
- Radiation boundary conditions for acoustic and elastic wave calculations
- Title not available (Why is that?)
- Title not available (Why is that?)
- Finite element solution of the Helmholtz equation with high wave number. I: The \(h\)-version of the FEM
- Hierarchical Matrices: Algorithms and Analysis
- Title not available (Why is that?)
- Title not available (Why is that?)
- Absorbing boundary conditions for domain decomposition
- Why restricted additive Schwarz converges faster than additive Schwarz
- Why it is Difficult to Solve Helmholtz Problems with Classical Iterative Methods
- Optimized Multiplicative, Additive, and Restricted Additive Schwarz Preconditioning
- Title not available (Why is that?)
- Optimized Schwarz Methods
- Preasymptotic error analysis of CIP-FEM and FEM for Helmholtz equation with high wave number. II: \(hp\) version
- Optimized Schwarz methods for circular domain decompositions with overlap
- Optimized Schwarz methods with nonoverlapping circular domain decomposition
- Spectral Analysis of the Discrete Helmholtz Operator Preconditioned with a Shifted Laplacian
- Schwarz methods over the course of time
- Is the Pollution Effect of the FEM Avoidable for the Helmholtz Equation Considering High Wave Numbers?
- An Introduction to Domain Decomposition Methods
- Title not available (Why is that?)
- Domain Decomposition Algorithms for Indefinite Elliptic Problems
- Applying GMRES to the Helmholtz equation with shifted Laplacian preconditioning: What is the largest shift for which wavenumber-independent convergence is guaranteed?
- Sweeping Preconditioner for the Helmholtz Equation: Moving Perfectly Matched Layers
- AN INCOMPLETE LU PRECONDITIONER FOR PROBLEMS IN ACOUSTICS
- FACTORIZATION OF THE CONVECTION-DIFFUSION OPERATOR AND THE SCHWARZ ALGORITHM
- AILU: a preconditioner based on the analytic factorization of the elliptic operator
- Optimal left and right additive Schwarz preconditioning for minimal residual methods with Euclidean and energy norms
- Preconditioned iterative methods on sparse subspaces
- CONTINUED-FRACTION ABSORBING BOUNDARY CONDITIONS FOR THE WAVE EQUATION
- Numerical-asymptotic boundary integral methods in high-frequency acoustic scattering
- Title not available (Why is that?)
- Artificial Boundary Method
- Advances in iterative methods and preconditioners for the Helmholtz equation
- Sweeping preconditioner for the Helmholtz equation: Hierarchical matrix representation
- A formulation of asymptotic and exact boundary conditions using local operators
- Convergence rate of some domain decomposition methods for overlapping and nonoverlapping subdomains
- Wave-ray multigrid method for standing wave equations
- Domain decomposition method for harmonic wave propagation: A general presentation
- A fast direct solver for boundary integral equations in two dimensions
- On a class of preconditioners for solving the Helmholtz equation
- Domain decomposition method for Maxwell's equations: scattering off periodic structures
- Algebraic Multilevel Preconditioner for the Helmholtz Equation in Heterogeneous Media
- Second-Order Absorbing Boundary Conditions for the Wave Equation: A Solution for the Corner Problem
- A rapidly converging domain decomposition method for the Helmholtz equation
- A robust multilevel method for hybridizable discontinuous Galerkin method for the Helmholtz equation
- FETI-DPH: A DUAL-PRIMAL DOMAIN DECOMPOSITION METHOD FOR ACOUSTIC SCATTERING
- An optimized Schwarz method with two-sided Robin transmission conditions for the Helmholtz equation
- Some techniques for computing wave propagation in optical waveguides.
- Double sweep preconditioner for optimized Schwarz methods applied to the Helmholtz problem
- A quasi-optimal non-overlapping domain decomposition algorithm for the Helmholtz equation
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Optimized Schwarz Methods without Overlap for the Helmholtz Equation
- Title not available (Why is that?)
- Title not available (Why is that?)
- A Fast Direct Solver for Structured Linear Systems by Recursive Skeletonization
- A Fast Solver for HSS Representations via Sparse Matrices
- A Novel Multigrid Based Preconditioner For Heterogeneous Helmholtz Problems
- A fast direct solver for scattering problems involving elongated structures
- Gaussian Spectral Rules for the Three-Point Second Differences: I. A Two-Point Positive Definite Problem in a Semi-Infinite Domain
- Two-level domain decomposition methods with Lagrange multipliers for the fast iterative solution of acoustic scattering problems
- A multigrid-based preconditioned Krylov subspace method for the Helmholtz equation with PML
- A parallel sweeping preconditioner for heterogeneous 3D Helmholtz equations
- An \(O(N)\) algorithm for constructing the solution operator to 2D elliptic boundary value problems in the absence of body loads
- Title not available (Why is that?)
- Efficient Structured Multifrontal Factorization for General Large Sparse Matrices
- Complexity Bounds for Regular Finite Difference and Finite Element Grids
- Non-overlapping domain decomposition method for a nodal finite element method
- The least squares AMG solver for the one-dimensional Helmholtz operator
- Title not available (Why is that?)
- Alternative integral equations for the iterative solution of acoustic scattering problems
- On Large-Scale Diagonalization Techniques for the Anderson Model of Localization
- Smoothed aggregation for Helmholtz problems
- Hierarchical matrix techniques for low- and high-frequency Helmholtz problems
- Robust and highly scalable parallel solution of the Helmholtz equation with large wave numbers
- Convergence analysis of a balancing domain decomposition method for solving a class of indefinite linear systems
Cited In (only showing first 100 items - show all)
- An overlapping decomposition framework for wave propagation in heterogeneous and unbounded media: formulation, analysis, algorithm, and simulation
- At the interface between semiclassical analysis and numerical analysis of wave scattering problems. Abstracts from the workshop held September 25 -- October 1, 2022
- A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity
- WaveHoltz: Iterative Solution of the Helmholtz Equation via the Wave Equation
- Sweeping preconditioners for stratified media in the presence of reflections
- Multigrid-Augmented Deep Learning Preconditioners for the Helmholtz Equation
- Corner treatments for high-order local absorbing boundary conditions in high-frequency acoustic scattering
- Exponentially convergent non overlapping domain decomposition methods for the Helmholtz equation
- An iterative solver for a coupled system of Helmholtz equations
- Applying GMRES to the Helmholtz equation with strong trapping: how does the number of iterations depend on the frequency?
- Contraction operator transformation for the complex heterogeneous Helmholtz equation
- A fast high order algorithm for multiple scattering from large sound-hard three dimensional configurations
- Construction and Numerical Assessment of Local Absorbing Boundary Conditions for Heterogeneous Time-Harmonic Acoustic Problems
- Improving formulas for the eigenvalues of finite block-Toeplitz tridiagonal matrices
- Analysis of a Helmholtz preconditioning problem motivated by uncertainty quantification
- A unified framework for double sweep methods for the Helmholtz equation
- Non-local variant of the optimised Schwarz method for arbitrary non-overlapping subdomain partitions
- Convergence analysis of the continuous and discrete non-overlapping double sweep domain decomposition method based on PMLs for the Helmholtz equation
- Solution of three-dimensional multiple scattering problems by the method of difference potentials
- Title not available (Why is that?)
- Multidirectional sweeping preconditioners with non-overlapping checkerboard domain decomposition for Helmholtz problems
- A non-overlapping domain decomposition method with high-order transmission conditions and cross-point treatment for Helmholtz problems
- Towards accuracy and scalability: combining isogeometric analysis with deflation to obtain scalable convergence for the Helmholtz equation
- L-sweeps: a scalable, parallel preconditioner for the high-frequency Helmholtz equation
- Natural Domain Decomposition Algorithms for the Solution of Time-Harmonic Elastic Waves
- NonLocal Optimized Schwarz Method for the Helmholtz Equation with Physical Boundaries
- Sweeping preconditioners for the iterative solution of quasiperiodic Helmholtz transmission problems in layered media
- Sixth-Order Compact Finite Difference Method for 2D Helmholtz Equations with Singular Sources and Reduced Pollution Effect
- A global variant of the COCR method for the complex symmetric Sylvester matrix equation \(AX+XB=C\)
- Scalable Convergence Using Two-Level Deflation Preconditioning for the Helmholtz Equation
- An adaptive finite element method for high-frequency scattering problems with smoothly varying coefficients
- Convergence of restricted additive Schwarz with impedance transmission conditions for discretised Helmholtz problems
- A non-overlapping domain decomposition method with perfectly matched layer transmission conditions for the Helmholtz equation
- Eigenvalues of the Truncated Helmholtz Solution Operator under Strong Trapping
- A Superlinear Convergence Estimate for the Parareal Schwarz Waveform Relaxation Algorithm
- Trace transfer-based diagonal sweeping domain decomposition method for the Helmholtz equation: algorithms and convergence analysis
- Preconditioners for Krylov subspace methods: An overview
- An adaptive multigrid solver for DPG methods with applications in linear acoustics and electromagnetics
- A comparison of coarse spaces for Helmholtz problems in the high frequency regime
- Dirac assisted tree method for 1D heterogeneous Helmholtz equations with arbitrary variable wave numbers
- Domain Decomposition with Local Impedance Conditions for the Helmholtz Equation with Absorption
- Double Source Transfer Domain Decomposition Method For Helmholtz Problems
- Multi-Resolution Localized Orthogonal Decomposition for Helmholtz Problems
- A non-overlapping Schwarz domain decomposition method with high-order finite elements for flow acoustics
- On a multilevel Levenberg–Marquardt method for the training of artificial neural networks and its application to the solution of partial differential equations
- Optimized Schwarz methods with elliptical domain decompositions
- On the characteristic polynomial, eigenvalues for block tridiagonal matrices
- An Additive Overlapping Domain Decomposition Method for the Helmholtz Equation
- Convergence of parallel overlapping domain decomposition methods for the Helmholtz equation
- A ROM-accelerated parallel-in-time preconditioner for solving all-at-once systems in unsteady convection-diffusion PDEs
- A pure source transfer domain decomposition method for Helmholtz equations in unbounded domain
- Asymptotic analysis for overlap in waveform relaxation methods for RC type circuits
- Non-Overlapping Schwarz Waveform-Relaxation for Nonlinear Advection-Diffusion Equations
- Acoustic transmission problems: Wavenumber-explicit bounds and resonance-free regions
- A coercive heterogeneous media Helmholtz model: formulation, wavenumber-explicit analysis, and preconditioned high-order FEM
- El-WaveHoltz: a time-domain iterative solver for time-harmonic elastic waves
- New Optimized Robin--Robin Domain Decomposition Methods using Krylov Solvers for the Stokes--Darcy System
- A hybridizable discontinuous Galerkin method with characteristic variables for Helmholtz problems
- Analysis of parallel Schwarz algorithms for time-harmonic problems using block Toeplitz matrices
- Conditioning analysis for discrete Helmholtz problems
- How to best choose the outer coarse mesh in the domain decomposition method of Bank and Jimack
- A Diagonal Sweeping Domain Decomposition Method with Source Transfer for the Helmholtz Equation
- High-order FEM domain decomposition models for high-frequency wave propagation in heterogeneous media
- A Parallel Domain Decomposition Method for the Helmholtz Equation in Layered Media
- Optimized Ventcel-Schwarz methods for the Cahn-Hilliard equation discretized by the stabilized linear Crank-Nicolson scheme
- A combined scheme of the local spectral element method and the generalized plane wave discontinuous Galerkin method for the anisotropic Helmholtz equation
- Scalable multi-level deflation preconditioning for highly indefinite time-harmonic waves
- Title not available (Why is that?)
- A Time-Domain Preconditioner for the Helmholtz Equation
- Optimal Complex Relaxation Parameters in Multigrid for Complex-Shifted Linear Systems
- Restrictions on the Use of Sweeping Type Preconditioners for Helmholtz Problems
- Optimized Schwarz Methods for the Cahn–Hilliard Equation
- Out-of-distributional risk bounds for neural operators with applications to the Helmholtz equation
- Does the Helmholtz Boundary Element Method Suffer from the Pollution Effect?
- Schwarz methods by domain truncation
- Transmission operators for the non-overlapping Schwarz method for solving Helmholtz problems in rectangular cavities
- A matrix-free parallel two-level deflation preconditioner for two-dimensional heterogeneous Helmholtz problems
- Pseudodifferential models for ultrasound waves with fractional attenuation
- A unified theory of non-overlapping Robin-Schwarz methods: continuous and discrete, including cross points
- SlabLU: a two-level sparse direct solver for elliptic PDEs
- Analysis of Schwarz Methods for Convected Helmholtz-Like Equations
- An Iterative Solver for the HPS Discretization Applied to Three Dimensional Helmholtz Problems
- Application of Adapted-Bubbles to the Helmholtz Equation with Large Wavenumbers in 2D
- Wavenumber Explicit Convergence of a Multiscale Generalized Finite Element Method for Heterogeneous Helmholtz Problems
- A matrix-free parallel solution method for the three-dimensional heterogeneous Helmholtz equation
- Domain truncation, absorbing boundary conditions, Schur complements, and Padé approximation
- Iterative Pure Source Transfer Domain Decomposition Methods for Helmholtz Equations in Heterogeneous Media
- Sharp bounds on Helmholtz impedance-to-impedance maps and application to overlapping domain decomposition
- Multigrid-augmented deep learning preconditioners for the Helmholtz equation using compact implicit layers
- A numerical algorithm based on probing to find optimized transmission conditions
- Inexact subdomain solves using deflated GMRES for Helmholtz problems
- Several ways to achieve robustness when solving wave propagation problems
- Nonoverlapping domain decomposition methods for time harmonic wave problems
- Optimized Schwarz methods with data-sparse transmission conditions
- Deep Domain Decomposition Methods: Helmholtz Equation
- A semi matrix-free twogrid preconditioner for the Helmholtz equation with near optimal shifts
- Scalable DPG multigrid solver for Helmholtz problems: a study on convergence
- Modified CRI iteration methods for complex symmetric indefinite linear systems
- Matrix-free parallel scalable multilevel deflation preconditioning for heterogeneous time-harmonic wave problems
- Computation and Applications of Mathieu Functions: A Historical Perspective
Uses Software
This page was built for publication: A class of iterative solvers for the Helmholtz equation: factorizations, sweeping preconditioners, source transfer, single layer potentials, polarized traces, and optimized Schwarz methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4621282)
