An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
From MaRDI portal
Publication:5113365
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
- 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?)
- A Fast $ULV$ Decomposition Solver for Hierarchically Semiseparable Representations
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- A fast algorithm for particle simulations
- 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
- BILUM: Block Versions of Multielimination and Multilevel ILU Preconditioner for General Sparse Linear Systems
- Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric 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 \(\mathcal H\)-matrix approximants to the inverse FE-matrix of elliptic operators with \(L^\infty\)-coefficients
- Fast algorithms for hierarchically semiseparable matrices
- Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- Generalized Nested Dissection
- Hierarchical interpolative factorization for elliptic operators: differential equations
- 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 University of Florida sparse matrix collection
- The black-box fast multipole method
- \(\mathcal H^2\)-matrix approximation of integral operators by interpolation
- ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices
Cited in
(17)- A polynomial-time algorithm for computing low CP-rank decompositions
- Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems
- Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
- Two-level Nyström-Schur preconditioner for sparse symmetric positive definite matrices
- FROSch preconditioners for land ice simulations of Greenland and Antarctica
- Hierarchical orthogonal factorization: sparse square matrices
- Nested Dissection for Sparse Nullspace Bases
- Robust and Effective eSIF Preconditioning for General Dense SPD Matrices
- Hierarchical interpolative factorization preconditioner for parabolic equations
- A fast direct solver for nonlocal operators in wavelet coordinates
- Sparse Hierarchical Preconditioners Using Piecewise Smooth Approximations of Eigenvectors
- An adaptive fast solver for a general class of positive definite matrices via energy decomposition
- Matrix sparsification and nested dissection over arbitrary fields
- Hierarchical orthogonal factorization: sparse least squares problems
- RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems
- An Incomplete Cholesky Preconditioner Based on Orthogonal Approximations
- Efficient Construction of an HSS Preconditioner for Symmetric Positive Definite $\mathcal{H}^2$ Matrices
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)
