Sparse Hierarchical Preconditioners Using Piecewise Smooth Approximations of Eigenvectors
From MaRDI portal
(Redirected from Publication:5147979)
Abstract: When solving linear systems arising from PDE discretizations, iterative methods (such as Conjugate Gradient, GMRES, or MINRES) are often the only practical choice. To converge in a small number of iterations, however, they have to be coupled with an efficient preconditioner. The efficiency of the preconditioner depends largely on its accuracy on the eigenvectors corresponding to small eigenvalues, and unfortunately, black-box methods typically cannot guarantee sufficient accuracy on these eigenvectors. Thus, constructing the preconditioner becomes a problem-dependent task. However, for a large class of problems, including many elliptic equations, the eigenvectors corresponding to small eigenvalues are smooth functions of the PDE grid. In this paper, we describe a hierarchical approximate factorization approach which focuses on improving accuracy on the smooth eigenvectors. The improved accuracy is achieved by preserving the action of the factorized matrix on piecewise polynomial functions of the grid. Based on the factorization, we propose a family of sparse preconditioners with or construction complexities. Our methods exhibit the optimal solution times in benchmarks run on large elliptic problems of different types, arising for example in flow or mechanical simulations. In the case of the linear elasticity equation the preconditioners are exact on the near-kernel rigid body modes.
Recommendations
- Preconditioners for hierarchical matrices based on their extended sparse form
- Approximate eigenvectors as preconditioner
- Parallel preconditioning of a sparse eigensolver
- Approximate inverse preconditioning in the parallel solution of sparse eigenproblems
- On the spectral equivalence of hierarchical matrix preconditioners for elliptic problems
- A fast hierarchically preconditioned eigensolver based on multiresolution matrix decomposition
- Sparse Preconditioned Iterative Methods for Dense Linear Systems
- Approximate eigen-decomposition preconditioners for solving numerical PDE problems
- scientific article; zbMATH DE number 176177
- scientific article; zbMATH DE number 1873440
Cites work
- ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices
- A class of first order factorization methods
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- A fast nested dissection solver for Cartesian 3D elliptic problems using hierarchical matrices
- A recursive skeletonization factorization based on strong admissibility
- A review of algebraic multigrid
- A robust hierarchical solver for ill-conditioned systems with applications to ice sheet modeling
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems
- An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
- An Approximate Factorization Procedure for Solving Self-Adjoint Elliptic Difference Equations
- An improved incomplete Cholesky factorization
- Approximation of solution operators of elliptic partial differential equations by \({\mathcal H}\)- and \({\mathcal H}^2\)-matrices
- Block Sparse Cholesky Algorithms on Advanced Uniprocessor Computers
- Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
- Distributed-memory hierarchical interpolative factorization
- Domain decomposition based \({\mathcal H}\)-LU preconditioning
- Effective and robust preconditioning of general SPD matrices via structured incomplete factorization
- Efficient inversion of the Galerkin matrix of general second-order elliptic operators with nonsmooth coefficients
- Elimination of rigid body modes from discretized boundary integral equations
- Existence of H-matrix approximants to the inverse FE-matrix of elliptic operators with L^-coefficients
- Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
- Generalized Nested Dissection
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- Hierarchical interpolative factorization for elliptic operators: differential equations
- Hierarchical matrix approximation with blockwise constraints
- Highly Parallel Sparse Cholesky Factorization
- scientific article; zbMATH DE number 3958638 (Why is no real title available?)
- scientific article; zbMATH DE number 4078693 (Why is no real title available?)
- ILUT: A dual threshold incomplete LU factorization
- Iterative Methods by Space Decomposition and Subspace Correction
- LAPACK Users' Guide
- Matrix computations.
- Methods of conjugate gradients for solving linear systems
- Multi-Level Adaptive Solutions to Boundary-Value Problems
- Nested Dissection of a Regular Finite Element Mesh
- On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic PDEs
- On the spectral equivalence of hierarchical matrix preconditioners for elliptic problems
- PaStiX: A high-performance parallel direct solver for sparse symmetric positive definite systems
- Rang revealing QR factorizations
- Recursively preconditioned hierarchical interpolative factorization for elliptic partial differential equations
- Robust Approximate Cholesky Factorization of Rank-Structured Symmetric Positive Definite Matrices
- Solution of Sparse Indefinite Systems of Linear Equations
- The incomplete Cholesky-conjugate gradient method for the iterative solution of systems of linear equations
- The inverse fast multipole method: using a fast approximate direct dolver as a preconditioner for dense linear systems
Cited in
(3)
This page was built for publication: Sparse Hierarchical Preconditioners Using Piecewise Smooth Approximations of Eigenvectors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5147979)
