Nested Domain Decomposition with Polarized Traces for the 2D Helmholtz Equation
From MaRDI portal
Publication:4569314
DOI10.1137/15M104582XzbMATH Open1394.65136arXiv1510.01831OpenAlexW2962789715WikidataQ129641303 ScholiaQ129641303MaRDI QIDQ4569314FDOQ4569314
Authors: Leonardo Zepeda-Núñez, Laurent Demanet 
Publication date: 28 June 2018
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
Abstract: We present a solver for the 2D high-frequency Helmholtz equation in heterogeneous, constant density, acoustic media, with online parallel complexity that scales empirically as , where is the number of volume unknowns, and is the number of processors, as long as . This sublinear scaling is achieved by domain decomposition, not distributed linear algebra, and improves on the scaling reported earlier in [L. Zepeda-N'u~nez and L. Demanet, J. Comput. Phys., 308 (2016), pp. 347-388 ]. The solver relies on a two-level nested domain decomposition: a layered partition on the outer level, and a further decomposition of each layer in cells at the inner level. The Helmholtz equation is reduced to a surface integral equation (SIE) posed at the interfaces between layers, efficiently solved via a nested version of the polarized traces preconditioner [L. Zepeda-N'u~nez and L. Demanet, J. Comput. Phys., 308 (2016), pp. 347-388.]. The favorable complexity is achieved via an efficient application of the integral operators involved in the SIE.
Full work available at URL: https://arxiv.org/abs/1510.01831
Recommendations
- The method of polarized traces for the 2D Helmholtz equation
- L-sweeps: a scalable, parallel preconditioner for the high-frequency Helmholtz equation
- A fast directional algorithm for high frequency acoustic scattering in two dimensions
- A fast propagation method for the Helmholtz equation
- A parallel sweeping preconditioner for heterogeneous 3D Helmholtz equations
- Distributed solution of the Helmholtz transmission problems via relaxed local multi-trace formulation and adaptive cross approximation
- Parallel iterative solution for the Helmholtz equation with exact non-reflecting boundary conditions
- scientific article; zbMATH DE number 1218951
Parallel numerical computation (65Y05) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Preconditioners for iterative methods (65F08) Finite difference methods applied to problems in fluid mechanics (76M20) Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Finite difference methods for boundary value problems involving PDEs (65N06) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22) Applications to the sciences (65Z05) Hydro- and aero-acoustics (76Q05)
Cites Work
- Algorithm 832
- A fully asynchronous multifrontal solver using distributed dynamic scheduling
- Perfectly matched layers for time-harmonic second order elliptic problems
- Existence of \(\mathcal H\)-matrix approximants to the inverse FE-matrix of elliptic operators with \(L^\infty\)-coefficients
- Nested Dissection of a Regular Finite Element Mesh
- Hierarchical matrices. A means to efficiently solve elliptic boundary value problems
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- THE PARTITION OF UNITY METHOD
- Title not available (Why is that?)
- Title not available (Why is that?)
- A perfectly matched layer for the absorption of electromagnetic waves
- Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems
- Title not available (Why is that?)
- Linear integral equations.
- A generalized finite element method for solving the Helmholtz equation in two dimensions with minimal pollution
- Title not available (Why is that?)
- Title not available (Why is that?)
- The discontinuous enrichment method
- Absorbing boundary conditions for domain decomposition
- Why it is difficult to solve Helmholtz problems with classical iterative methods
- Plane wave discontinuous Galerkin methods: Analysis of theh-version
- Optimized Schwarz Methods
- 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
- Plane wave discontinuous Galerkin methods for the 2D Helmholtz equation: analysis of the \(p\)-version
- Applying GMRES to the Helmholtz equation with shifted Laplacian preconditioning: What is the largest shift for which wavenumber-independent convergence is guaranteed?
- On accuracy conditions for the numerical computation of waves
- Sweeping preconditioner for the Helmholtz equation: moving perfectly matched layers
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- 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
- Title not available (Why is that?)
- Wave-ray multigrid method for standing wave equations
- Domain decomposition method for harmonic wave propagation: A general presentation
- Multi-trace boundary integral formulation for acoustic scattering by composite structures
- 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
- Double sweep preconditioner for optimized Schwarz methods applied to the Helmholtz problem
- A quasi-optimal non-overlapping domain decomposition algorithm for the Helmholtz equation
- Optimized Schwarz Methods without Overlap for the Helmholtz Equation
- 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
- Matrix probing and its conditioning
- Parallel Double Sweep Preconditioner for the Optimized Schwarz Algorithm Applied to High Frequency Helmholtz and Maxwell Equations
- A parallel sweeping preconditioner for heterogeneous 3D Helmholtz equations
- Title not available (Why is that?)
- An analysis of the BEM-FEM non-overlapping domain decomposition method for a scattering problem
- 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
- 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
- On the relation between optimized Schwarz methods and source transfer
- A source transfer domain decomposition method for Helmholtz equations in unbounded domain
- A fast method for the solution of the Helmholtz equation
- A fast propagation method for the Helmholtz equation
- A sweeping preconditioner for Yee's finite difference approximation of time-harmonic Maxwell's equations
- 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.
- Optimal interface conditions for an arbitrary decomposition into subdomains
- A source transfer domain decomposition method for Helmholtz equations in unbounded domain, part II: extensions
- The method of polarized traces for the 2D Helmholtz equation
- A spectrally accurate direct solution technique for frequency-domain scattering problems with variable media
- Fast, adaptive, high-order accurate discretization of the Lippmann-Schwinger equation in two dimensions
- Multigrid-based `shifted-Laplacian' preconditioning for the time-harmonic elastic wave equation
- Comments on the GMRES Convergence for Preconditioned Systems
- Optimized Schwarz methods with overlap for the Helmholtz equation
- Optimized Schwarz method with two-sided transmission conditions in an unsymmetric domain decomposition
- Title not available (Why is that?)
Cited In (11)
- Corner treatments for high-order local absorbing boundary conditions in high-frequency acoustic scattering
- Schwarz methods by domain truncation
- Multigrid-based `shifted-Laplacian' preconditioning for the time-harmonic elastic wave equation
- L-sweeps: a scalable, parallel preconditioner for the high-frequency Helmholtz equation
- The method of polarized traces for the 2D Helmholtz equation
- Fast alternating bidirectional preconditioner for the 2D high-frequency Lippmann-Schwinger equation
- WaveHoltz: iterative solution of the Helmholtz equation via the wave equation
- Acceleration of an Iterative Method for the Evaluation of High-Frequency Multiple Scattering Effects
- Adaptive finite element method for the sound wave problems in two kinds of media
- A domain decomposition preconditioning for an inverse volume scattering problem
- A class of iterative solvers for the Helmholtz equation: factorizations, sweeping preconditioners, source transfer, single layer potentials, polarized traces, and optimized Schwarz methods
Uses Software
This page was built for publication: Nested Domain Decomposition with 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 Q4569314)
