An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
From MaRDI portal
Abstract: We propose a new algorithm for the fast solution of large, sparse, symmetric positive-definite linear systems, spaND -- sparsified Nested Dissection. It is based on nested dissection, sparsification and low-rank compression. After eliminating all interiors at a given level of the elimination tree, the algorithm sparsifies all separators corresponding to the interiors. This operation reduces the size of the separators by eliminating some degrees of freedom but without introducing any fill-in. This is done at the expense of a small and controllable approximation error. The result is an approximate factorization that can be used as an efficient preconditioner. We then perform several numerical experiments to evaluate this algorithm. We demonstrate that a version using orthogonal factorization and block-diagonal scaling takes fewer CG iterations to converge than previous similar algorithms on various kinds of problems. Furthermore, this algorithm is provably guaranteed to never break down and the matrix stays symmetric positive-definite throughout the process. We evaluate the algorithm on some large problems and show it exhibits near-linear scaling. The factorization time is roughly O(N) and the number of iterations grows slowly with N.
Recommendations
- Hierarchical orthogonal factorization: sparse least squares problems
- Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems
- Low-Rank Factorizations in Data Sparse Hierarchical Algorithms for Preconditioning Symmetric Positive Definite Matrices
- ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices
- An algebraic approach for \({\mathcal{H}}\)-matrix preconditioners
- Recursively preconditioned hierarchical interpolative factorization for elliptic partial differential equations
- Interconnected hierarchical structures for fast direct elliptic solution
- New efficient and robust HSS Cholesky factorization of SPD matrices
- Hierarchical orthogonal factorization: sparse square matrices
- Robust Approximate Cholesky Factorization of Rank-Structured Symmetric Positive Definite Matrices
Cites work
- H^2-matrix approximation of integral operators by interpolation
- ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices
- A Fast ULV Decomposition Solver for Hierarchically Semiseparable Representations
- A fast algorithm for particle simulations
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- A fast direct solver for elliptic problems on general meshes in 2D
- A relaxation method for solving elliptic difference equations
- 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
- An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
- Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems
- BILUM: Block Versions of Multielimination and Multilevel ILU Preconditioner for General Sparse Linear Systems
- Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
- Domain decomposition based \({\mathcal H}\)-LU preconditioning
- Effective and robust preconditioning of general SPD matrices via structured incomplete factorization
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Efficient inversion of the Galerkin matrix of general second-order elliptic operators with nonsmooth coefficients
- 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 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
- scientific article; zbMATH DE number 3958638 (Why is no real title available?)
- scientific article; zbMATH DE number 467276 (Why is no real title available?)
- scientific article; zbMATH DE number 1953444 (Why is no real title available?)
- scientific article; zbMATH DE number 6159604 (Why is no real title available?)
- ILUT: A dual threshold incomplete LU factorization
- Improving multifrontal methods by means of block low-rank representations
- LAPACK Users' Guide
- Methods of conjugate gradients for solving linear systems
- Nested Dissection of a Regular Finite Element Mesh
- On the Compression of Low Rank Matrices
- On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic PDEs
- PaStiX: A high-performance parallel direct solver for sparse symmetric positive definite systems
- Randomized algorithms for the low-rank approximation of matrices
- Randomized sparse direct solvers
- 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
- Some Fast Algorithms for Sequentially Semiseparable Representations
- Strong rank revealing LU factorizations
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- The black-box fast multipole method
- The University of Florida sparse matrix collection
Cited in
(21)- A fast direct solver for nonlocal operators in wavelet coordinates
- Hierarchical orthogonal factorization: sparse least squares problems
- Hierarchical interpolative factorization preconditioner for parabolic equations
- Nested Dissection for Sparse Nullspace Bases
- A polynomial-time algorithm for computing low CP-rank decompositions
- An adaptive fast solver for a general class of positive definite matrices via energy decomposition
- Efficient Construction of an HSS Preconditioner for Symmetric Positive Definite $\mathcal{H}^2$ Matrices
- RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems
- Hierarchical orthogonal factorization: sparse square matrices
- FROSch preconditioners for land ice simulations of Greenland and Antarctica
- Sparse Hierarchical Preconditioners Using Piecewise Smooth Approximations of Eigenvectors
- Robust and Effective eSIF Preconditioning for General Dense SPD Matrices
- Two-level Nyström-Schur preconditioner for sparse symmetric positive definite matrices
- Matrix sparsification and nested dissection over arbitrary fields
- Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
- An Incomplete Cholesky Preconditioner Based on Orthogonal Approximations
- Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems
- Recursive sparse LU decomposition based on nested dissection and low rank approximations
- Sparse linear least-squares problems
- Engineering edge orientation algorithms
- A manifold learning approach to nonlinear model order reduction of quasi-static problems in solid mechanics: proof of concept and parameter study
Describes a project that uses
Uses Software
This page was built for publication: An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5113365)
