The method of polarized traces for the 2D Helmholtz equation
From MaRDI portal
Publication:729469
DOI10.1016/J.JCP.2015.11.040zbMATH Open1351.76197arXiv1410.5910OpenAlexW1798342062MaRDI QIDQ729469FDOQ729469
Laurent Demanet, Leonardo Zepeda-Núñez
Publication date: 20 December 2016
Published in: Journal of Computational Physics (Search for Journal in Brave)
Abstract: We present a solver for the 2D high-frequency Helmholtz equation in heterogeneous acoustic media, with online parallel complexity that scales optimally as , where is the number of volume unknowns, and is the number of processors, as long as grows at most like a small fractional power of . The solver decomposes the domain into layers, and uses transmission conditions in boundary integral form to explicitly define "polarized traces", i.e., up- and down-going waves sampled at interfaces. Local direct solvers are used in each layer to precompute traces of local Green's functions in an embarrassingly parallel way (the offline part), and incomplete Green's formulas are used to propagate interface data in a sweeping fashion, as a preconditioner inside a GMRES loop (the online part). Adaptive low-rank partitioning of the integral kernels is used to speed up their application to interface data. The method uses second-order finite differences. The complexity scalings are empirical but motivated by an analysis of ranks of off-diagonal blocks of oscillatory integrals. They continue to hold in the context of standard geophysical community models such as BP and Marmousi 2, where convergence occurs in 5 to 10 GMRES iterations.
Full work available at URL: https://arxiv.org/abs/1410.5910
Recommendations
- Nested Domain Decomposition with Polarized Traces for the 2D Helmholtz Equation
- A parallel domain decomposition method for the Helmholtz equation in layered media
- A fast propagation method for the Helmholtz equation
- A Geometric Multigrid Preconditioner for the Solution of the Helmholtz Equation in Three-Dimensional Heterogeneous Media on Massively Parallel Computers
- A parallel sweeping preconditioner for heterogeneous 3D Helmholtz equations
Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Finite difference methods applied to problems in fluid mechanics (76M20) Finite difference methods for boundary value problems involving PDEs (65N06) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22) Hydro- and aero-acoustics (76Q05)
Cites Work
- Algorithm 832
- A fully asynchronous multifrontal solver using distributed dynamic scheduling
- An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation
- Nested Dissection of a Regular Finite Element Mesh
- Hierarchical matrices. A means to efficiently solve elliptic boundary value problems
- Inversion of Jacobi's tridiagonal matrix
- Parallel iterative methods for sparse linear systems
- A Review on the Inverse of Symmetric Tridiagonal and Block Tridiagonal Matrices
- THE PARTITION OF UNITY METHOD
- Title not available (Why is that?)
- A perfectly matched layer for the absorption of electromagnetic waves
- Fast wave computation via Fourier integral operators
- Wave propagation using bases for bandlimited functions
- Linear integral equations.
- Application of an Ultra Weak Variational Formulation of Elliptic PDEs to the Two-Dimensional Helmholtz Problem
- The discontinuous enrichment method
- Why it is Difficult to Solve Helmholtz Problems with Classical Iterative Methods
- Minimizing Communication in Numerical Linear Algebra
- Plane wave discontinuous Galerkin methods: Analysis of theh-version
- Plane wave approximation of homogeneous Helmholtz solutions
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- Is the Helmholtz Equation Really Sign-Indefinite?
- A least-squares method 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?
- Sweeping Preconditioner for the Helmholtz Equation: Moving Perfectly Matched Layers
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- Rapid solution of integral equations of classical potential theory
- Using Plane Waves as Base Functions for Solving Time Harmonic Equations with the Ultra Weak Variational Formulation
- Numerical-asymptotic boundary integral methods in high-frequency acoustic scattering
- Advances in iterative methods and preconditioners for the Helmholtz equation
- Sweeping preconditioner for the Helmholtz equation: Hierarchical matrix representation
- A domain decomposition method for the Helmholtz equation and related optimal control problems
- Wave-ray multigrid method for standing wave equations
- A multigrid method enhanced by Krylov subspace iteration for discrete Helmholtz equations
- Algebraic Multilevel Preconditioner for the Helmholtz Equation in Heterogeneous Media
- Title not available (Why is that?)
- A rapidly converging domain decomposition method for the Helmholtz equation
- Fast Huygens sweeping methods for Helmholtz equations in inhomogeneous media in the high frequency regime
- A fast butterfly algorithm for the computation of Fourier integral operators
- Double sweep preconditioner for optimized Schwarz methods applied to the Helmholtz problem
- Title not available (Why is that?)
- A Novel Multigrid Based Preconditioner For Heterogeneous Helmholtz Problems
- Multiple traces boundary integral formulation for Helmholtz transmission problems
- A fast direct solver for scattering problems involving elongated structures
- Separation-of-variables as a preconditioner for an iterative Helmholtz solver
- A dispersion minimizing finite difference scheme and preconditioned solver for the 3D Helmholtz equation
- A parallel sweeping preconditioner for heterogeneous 3D Helmholtz equations
- Compressed Absorbing Boundary Conditions via Matrix Probing
- Complexity Bounds for Regular Finite Difference and Finite Element Grids
- AILU FOR HELMHOLTZ PROBLEMS: A NEW PRECONDITIONER BASED ON THE ANALYTIC PARABOLIC FACTORIZATION
- A randomized algorithm for the decomposition of matrices
- A sweeping preconditioner for time-harmonic Maxwell's equations with finite elements
- The Interplay of Ranks of Submatrices
- Modeling of Seismic Data in the Downward Continuation Approach
- Electromagnetic integral equations requiring small numbers of Krylov-subspace iterations
- A parallel multigrid-based preconditioner for the 3D heterogeneous high-frequency Helmholtz equation
- An algorithm for the rapid evaluation of special function transforms
- A coarse space for heterogeneous Helmholtz problems based on the Dirichlet-to-Neumann operator
- Local Fourier analysis of the complex shifted Laplacian preconditioner for Helmholtz problems
- On the convergence of shifted Laplace preconditioner combined with multilevel deflation
- A Distributed-Memory Package for Dense Hierarchically Semi-Separable Matrix Computations Using Randomization
- Efficient Scalable Algorithms for Solving Dense Linear Systems with Hierarchically Semiseparable Structures
- A source transfer domain decomposition method for Helmholtz equations in unbounded domain
- A fast method for the solution of the Helmholtz equation
- Fast construction of hierarchical matrix representation from matrix-vector multiplication
- A fast direct algorithm for the solution of the Laplace equation on regions with fractal boundaries
- Generalization of the phase-screen approximation for the scattering of acoustic waves.
- A sweeping preconditioner for Yee's finite difference approximation of time-harmonic Maxwell's equations
- Parallel solution of block tridiagonal linear systems
- Exact constructions of square-root Helmholtz operator symbols: the focusing quadratic profile.
- Sweeping preconditioners for elastic wave propagation with spectral element methods
- 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
- AILU for Helmholtz problems: a new preconditioner based on an analytic factorization
- A Source Transfer Domain Decomposition Method for Helmholtz Equations in Unbounded Domain Part II: Extensions
- A Parallel Butterfly Algorithm
Cited In (49)
- On Nilpotent Subdomain Iterations
- WaveHoltz: Iterative Solution of the Helmholtz Equation via the Wave Equation
- Sweeping preconditioners for stratified media in the presence of reflections
- Restrictions on the Use of Sweeping Type Preconditioners for Helmholtz Problems
- An improved sweeping domain decomposition preconditioner for the Helmholtz equation
- Fast, adaptive, high-order accurate discretization of the Lippmann-Schwinger equation in two dimensions
- A unified framework for double sweep methods for the Helmholtz equation
- Solving the wide-band inverse scattering problem via equivariant neural networks
- Additive sweeping preconditioner for the Helmholtz equation
- Schwarz methods by domain truncation
- Preconditioning the Helmholtz equation with the shifted Laplacian and Faber polynomials
- Sparsify and Sweep: An Efficient Preconditioner for the Lippmann--Schwinger Equation
- 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
- Solving the Three-Dimensional High-frequency Helmholtz Equation Using Contour Integration and Polynomial Preconditioning
- Domain decomposition preconditioning for high-frequency Helmholtz problems with absorption
- Radial basis function-generated finite differences with Bessel weights for the 2D Helmholtz equation
- L-sweeps: a scalable, parallel preconditioner for the high-frequency Helmholtz equation
- A hybrid approach to solve the high-frequency Helmholtz equation with source singularity in smooth heterogeneous media
- Natural Domain Decomposition Algorithms for the Solution of Time-Harmonic Elastic Waves
- Sweeping preconditioners for the iterative solution of quasiperiodic Helmholtz transmission problems in layered media
- Fast alternating bidirectional preconditioner for the 2D high-frequency Lippmann-Schwinger equation
- A Geometric Multigrid Preconditioner for the Solution of the Helmholtz Equation in Three-Dimensional Heterogeneous Media on Massively Parallel Computers
- A multiscale continuous Galerkin method for stochastic simulation and robust design of photonic crystals
- A non-overlapping domain decomposition method with perfectly matched layer transmission conditions for the Helmholtz equation
- A Class of Iterative Solvers for the Helmholtz Equation: Factorizations, Sweeping Preconditioners, Source Transfer, Single Layer Potentials, Polarized Traces, and Optimized Schwarz Methods
- Recursive sweeping preconditioner for the three-dimensional Helmholtz equation
- Trace transfer-based diagonal sweeping domain decomposition method for the Helmholtz equation: algorithms and convergence analysis
- OSDS: a sweeping preconditioner for the Helmholtz equation
- An adaptive multigrid solver for DPG methods with applications in linear acoustics and electromagnetics
- Domain Decomposition with Local Impedance Conditions for the Helmholtz Equation with Absorption
- Double Source Transfer Domain Decomposition Method For Helmholtz Problems
- A Sign-Definite Preconditioned High-Order FEM, Part I: Formulation and Simulation for Bounded Homogeneous Media Wave Propagation
- Nested Domain Decomposition with Polarized Traces for the 2D Helmholtz Equation
- Nonlinear Riemann type problems associated to Hermitian Helmholtz equations
- An Additive Overlapping Domain Decomposition Method for the Helmholtz Equation
- Convergence of parallel overlapping domain decomposition methods for the Helmholtz equation
- Optimized Schwarz methods with overlap for the Helmholtz equation
- Wide-Band Butterfly Network: Stable and Efficient Inversion Via Multi-Frequency Neural Networks
- A pure source transfer domain decomposition method for Helmholtz equations in unbounded domain
- Multitrace/singletrace formulations and domain decomposition methods for the solution of Helmholtz transmission problems for bounded composite scatterers
- A Fast Butterfly-Compressed Hadamard–Babich Integrator for High-Frequency Helmholtz Equations in Inhomogeneous Media with Arbitrary Sources
- How to Choose the Shift in the Shifted Laplace Preconditioner for the Helmholtz Equation Combined with Deflation
- A Diagonal Sweeping Domain Decomposition Method with Source Transfer for the Helmholtz Equation
- Adaptive finite element method for the sound wave problems in two kinds of media
- Recent Results on Domain Decomposition Preconditioning for the High-Frequency Helmholtz Equation Using Absorption
- A Parallel Domain Decomposition Method for the Helmholtz Equation in Layered Media
- Learning dominant wave directions for plane wave methods for high-frequency Helmholtz equations
- A domain decomposition preconditioning for an inverse volume scattering problem
Uses Software
This page was built for publication: The method of polarized traces for the 2D Helmholtz equation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q729469)
