A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity
From MaRDI portal
Abstract: The paper introduces a novel, hierarchical preconditioner based on nested dissection and hierarchical matrix compression. The preconditioner is intended for continuous and discontinuous Galerkin formulations of elliptic problems. We exploit the property that Schur complements arising in such problems can be well approximated by hierarchical matrices. An approximate factorization can be computed matrix-free and in a (quasi-)linear number of operations. The nested dissection is specifically designed to aid the factorization process using hierarchical matrices. We demonstrate the viability of the preconditioner on a range of 2D problems, including the Helmholtz equation and the elastic wave equation. Throughout all tests, including wave phenomena with high wavenumbers, the generalized minimal residual method (GMRES) with the proposed preconditioner converges in a very low number of iterations. We demonstrate that this is due to the hierarchical nature of our approach which makes the high wavenumber limit manageable.
Recommendations
- scientific article; zbMATH DE number 819141
- An efficient hierarchical preconditioner for quadratic discretizations of finite element problems.
- An efficient two-level preconditioner for multi-frequency wave propagation problems
- Wavelet-based preconditioners for boundary integral equations
- Hierarchical preconditioners for high-order FEM
- A wavelet multigrid preconditioner for Dirichlet boundary value problems in general domains
- Sweeping preconditioner for the Helmholtz equation: hierarchical matrix representation
- Hierarchical interpolative factorization preconditioner for parabolic equations
- Preconditioning waveform relaxation iterations for differential systems
Cites work
- A class of iterative solvers for the Helmholtz equation: factorizations, sweeping preconditioners, source transfer, single layer potentials, polarized traces, and optimized Schwarz methods
- A direct solver with O(N) complexity for integral equations on one-dimensional domains
- A Fast ULV Decomposition Solver for Hierarchically Semiseparable Representations
- A fast direct solver for a class of elliptic partial differential equations
- A fast randomized algorithm for computing a hierarchically semiseparable representation of a matrix
- A non-uniform basis order for the discontinuous Galerkin method of the 3D dissipative wave equation with perfectly matched layer
- A Novel Multigrid Based Preconditioner For Heterogeneous Helmholtz Problems
- Advances in iterative methods and preconditioners for the Helmholtz equation
- AILU: a preconditioner based on the analytic factorization of the elliptic operator
- An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
- AN INCOMPLETE LU PRECONDITIONER FOR PROBLEMS IN ACOUSTICS
- Approximate Separability of the Green's Function of the Helmholtz Equation in the High Frequency Limit
- Compatible algorithms for coupled flow and transport
- Direct methods for sparse matrices
- Domain Decomposition Preconditioning for Surface Integral Equations in Solving Challenging Electromagnetic Scattering Problems
- Efficient inversion of the Galerkin matrix of general second-order elliptic operators with nonsmooth coefficients
- Efficient numerical methods for non-local operators. \(\mathcal H^2\)-matrix compression, algorithms and analysis.
- Efficient preconditioning of \(hp\)-FEM matrices by hierarchical low-rank approximations
- Efficient structured multifrontal factorization for general large sparse matrices
- Existence of H-matrix approximants to the inverse FE-matrix of elliptic operators with L^-coefficients
- Fast algorithms for hierarchically semiseparable matrices
- Fast construction of hierarchical matrix representation from matrix-vector multiplication
- Fast Direct Solvers for Elliptic PDEs
- Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
- Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
- Hierarchical algorithms on hierarchical architectures
- Hm-toolbox: MATLAB software for HODLR and HSS matrices
- scientific article; zbMATH DE number 1953444 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- scientific article; zbMATH DE number 5179816 (Why is no real title available?)
- Improving multifrontal methods by means of block low-rank representations
- Low-Rank Updates and a Divide-And-Conquer Method for Linear Matrix Equations
- Randomized sparse direct solvers
- Robust and accurate stopping criteria for adaptive randomized sampling in matrix-free hierarchically semiseparable construction
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- Sweeping preconditioner for the Helmholtz equation: hierarchical matrix representation
- Why Finite Element Discretizations Can Be Factored by Triangular Hierarchical Matrices
- Why it is difficult to solve Helmholtz problems with classical iterative methods
Cited in
(7)- An efficient two-level preconditioner for multi-frequency wave propagation problems
- A hierarchical wavefront method for LU-SGS
- Matrix probing: a randomized preconditioner for the wave-equation Hessian
- scientific article; zbMATH DE number 5236221 (Why is no real title available?)
- Schwarz methods by domain truncation
- LFA-tuned matrix-free multigrid method for the elastic Helmholtz equation
- Mixed precision HODLR matrices
This page was built for publication: A Hierarchical Preconditioner for Wave Problems in Quasilinear Complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5028410)
