The method of polarized traces for the 2D Helmholtz equation
From MaRDI portal
(Redirected from Publication:729469)
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)
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.
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
Cites work
- scientific article; zbMATH DE number 4204909 (Why is no real title available?)
- scientific article; zbMATH DE number 1023095 (Why is no real title available?)
- scientific article; zbMATH DE number 1446717 (Why is no real title available?)
- A Novel Multigrid Based Preconditioner For Heterogeneous Helmholtz Problems
- A Review on the Inverse of Symmetric Tridiagonal and Block Tridiagonal Matrices
- A coarse space for heterogeneous Helmholtz problems based on the Dirichlet-to-Neumann operator
- A dispersion minimizing finite difference scheme and preconditioned solver for the 3D Helmholtz equation
- A distributed-memory package for dense hierarchically semi-separable matrix computations using randomization
- A domain decomposition method for the Helmholtz equation and related optimal control problems
- A fast butterfly algorithm for the computation of Fourier integral operators
- A fast direct algorithm for the solution of the Laplace equation on regions with fractal boundaries
- A fast direct solver for scattering problems involving elongated structures
- A fast method for the solution of the Helmholtz equation
- A fully asynchronous multifrontal solver using distributed dynamic scheduling
- A least-squares method for the Helmholtz equation
- A multigrid method enhanced by Krylov subspace iteration for discrete Helmholtz equations
- A new level-dependent coarse grid correction scheme for indefinite Helmholtz problems.
- A parallel butterfly algorithm
- A parallel multigrid-based preconditioner for the 3D heterogeneous high-frequency Helmholtz equation
- A parallel sweeping preconditioner for heterogeneous 3D Helmholtz equations
- A perfectly matched layer for the absorption of electromagnetic waves
- A randomized algorithm for the decomposition of matrices
- 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
- A sweeping preconditioner for Yee's finite difference approximation of time-harmonic Maxwell's equations
- A sweeping preconditioner for time-harmonic Maxwell's equations with finite elements
- AILU for Helmholtz problems: a new preconditioner based on an analytic factorization
- Advances in iterative methods and preconditioners for the Helmholtz equation
- Ailu for Helmholtz problems: a new preconditioner based on the analytic parabolic factorization
- Algebraic multilevel preconditioner for the Helmholtz equation in heterogeneous media
- Algorithm 832
- An \(\mathcal O(N\log N)\) fast direct solver for partial hierarchically semi-separable matrices. With application to radial basis function interpolation
- An algorithm for the rapid evaluation of special function transforms
- An improved two-grid preconditioner for the solution of three-dimensional Helmholtz problems in heterogeneous media.
- Application of an Ultra Weak Variational Formulation of Elliptic PDEs to the Two-Dimensional Helmholtz Problem
- Applying GMRES to the Helmholtz equation with shifted Laplacian preconditioning: What is the largest shift for which wavenumber-independent convergence is guaranteed?
- Complexity Bounds for Regular Finite Difference and Finite Element Grids
- Compressed absorbing boundary conditions via matrix probing
- Double sweep preconditioner for optimized Schwarz methods applied to the Helmholtz problem
- Efficient scalable algorithms for solving dense linear systems with hierarchically semiseparable structures
- Electromagnetic integral equations requiring small numbers of Krylov-subspace iterations
- Exact constructions of square-root Helmholtz operator symbols: the focusing quadratic profile.
- Fast Huygens sweeping methods for Helmholtz equations in inhomogeneous media in the high frequency regime
- Fast construction of hierarchical matrix representation from matrix-vector multiplication
- Fast wave computation via Fourier integral operators
- Generalization of the phase-screen approximation for the scattering of acoustic waves.
- Hierarchical matrices. A means to efficiently solve elliptic boundary value problems
- Inversion of Jacobi's tridiagonal matrix
- Is the Helmholtz equation really sign-indefinite?
- Linear integral equations.
- Local Fourier analysis of the complex shifted Laplacian preconditioner for Helmholtz problems.
- Minimizing communication in numerical linear algebra
- Modeling of Seismic Data in the Downward Continuation Approach
- Multiple traces boundary integral formulation for Helmholtz transmission problems
- Nested Dissection of a Regular Finite Element Mesh
- Numerical-asymptotic boundary integral methods in high-frequency acoustic scattering
- On the convergence of shifted Laplace preconditioner combined with multilevel deflation.
- Optimal interface conditions for an arbitrary decomposition into subdomains
- Parallel iterative methods for sparse linear systems
- Parallel solution of block tridiagonal linear systems
- Plane wave approximation of homogeneous Helmholtz solutions
- Plane wave discontinuous Galerkin methods: Analysis of theh-version
- Rapid solution of integral equations of classical potential theory
- Separation-of-variables as a preconditioner for an iterative Helmholtz solver
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- Sweeping preconditioner for the Helmholtz equation: hierarchical matrix representation
- Sweeping preconditioner for the Helmholtz equation: moving perfectly matched layers
- Sweeping preconditioners for elastic wave propagation with spectral element methods
- THE PARTITION OF UNITY METHOD
- The Interplay of Ranks of Submatrices
- The Multifrontal Solution of Indefinite Sparse Symmetric Linear
- The discontinuous enrichment method
- Using plane waves as base functions for solving time harmonic equations with the ultra weak variational formulation
- Wave propagation using bases for bandlimited functions
- Wave-ray multigrid method for standing wave equations
- Why it is difficult to solve Helmholtz problems with classical iterative methods
Cited in
(49)- 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
- Domain decomposition with local impedance conditions for the Helmholtz equation with absorption
- Domain decomposition preconditioning for high-frequency Helmholtz problems with absorption
- Schwarz methods by domain truncation
- A multiscale continuous Galerkin method for stochastic simulation and robust design of photonic crystals
- Multitrace/singletrace formulations and domain decomposition methods for the solution of Helmholtz transmission problems for bounded composite scatterers
- Optimized Schwarz methods with overlap for the Helmholtz equation
- Learning dominant wave directions for plane wave methods for high-frequency Helmholtz equations
- Preconditioning the Helmholtz equation with the shifted Laplacian and Faber polynomials
- Adaptive finite element method for the sound wave problems in two kinds of media
- Radial basis function-generated finite differences with Bessel weights for the 2D Helmholtz equation
- A pure source transfer domain decomposition method for Helmholtz equations in unbounded domain
- Solving the wide-band inverse scattering problem via equivariant neural networks
- Nested Domain Decomposition with Polarized Traces for the 2D Helmholtz Equation
- L-sweeps: a scalable, parallel preconditioner for the high-frequency Helmholtz equation
- Sparsify and sweep: an efficient preconditioner for the Lippmann-Schwinger equation
- Nonlinear Riemann type problems associated to Hermitian Helmholtz equations
- Fast alternating bidirectional preconditioner for the 2D high-frequency Lippmann-Schwinger equation
- A hybrid approach to solve the high-frequency Helmholtz equation with source singularity in smooth heterogeneous media
- Recent results on domain decomposition preconditioning for the high-frequency Helmholtz equation using absorption
- Multidirectional sweeping preconditioners with non-overlapping checkerboard domain decomposition for Helmholtz problems
- Recursive sweeping preconditioner for the three-dimensional Helmholtz equation
- A unified framework for double sweep methods for the Helmholtz equation
- WaveHoltz: iterative solution of the Helmholtz equation via the wave equation
- A non-overlapping domain decomposition method with high-order transmission conditions and cross-point treatment for Helmholtz problems
- An improved sweeping domain decomposition preconditioner for the Helmholtz equation
- How to choose the shift in the shifted Laplace preconditioner for the Helmholtz equation combined with deflation
- Fast, adaptive, high-order accurate discretization of the Lippmann-Schwinger equation in two dimensions
- Additive sweeping preconditioner for the Helmholtz equation
- Natural domain decomposition algorithms for the solution of time-harmonic elastic waves
- A non-overlapping domain decomposition method with perfectly matched layer transmission conditions for the Helmholtz equation
- An Additive Overlapping Domain Decomposition Method for the Helmholtz Equation
- A domain decomposition preconditioning for an inverse volume scattering problem
- A Fast Butterfly-Compressed Hadamard–Babich Integrator for High-Frequency Helmholtz Equations in Inhomogeneous Media with Arbitrary Sources
- A class of iterative solvers for the Helmholtz equation: factorizations, sweeping preconditioners, source transfer, single layer potentials, polarized traces, and optimized Schwarz methods
- A Geometric Multigrid Preconditioner for the Solution of the Helmholtz Equation in Three-Dimensional Heterogeneous Media on Massively Parallel Computers
- Solving the three-dimensional high-frequency Helmholtz equation using contour integration and polynomial preconditioning
- On nilpotent subdomain iterations
- OSDS: a sweeping preconditioner for the Helmholtz equation
- A parallel domain decomposition method for the Helmholtz equation in layered media
- An adaptive multigrid solver for DPG methods with applications in linear acoustics and electromagnetics
- Wide-band butterfly network: stable and efficient inversion via multi-frequency neural networks
- A diagonal sweeping domain decomposition method with source transfer for the Helmholtz equation
- Sweeping preconditioners for stratified media in the presence of reflections
- Sweeping preconditioners for the iterative solution of quasiperiodic Helmholtz transmission problems in layered media
- Convergence of parallel overlapping domain decomposition methods for the Helmholtz equation
- Restrictions on the use of sweeping type preconditioners for Helmholtz problems
- Trace transfer-based diagonal sweeping domain decomposition method for the Helmholtz equation: algorithms and convergence analysis
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)
