An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
From MaRDI portal
Publication:5113365
DOI10.1137/19M123806XzbMATH Open1441.65048arXiv1901.02971MaRDI QIDQ5113365FDOQ5113365
Authors: Léopold Cambier, Chao Chen, E. G. Boman, Sivasankaran Rajamanickam, R. S. Tuminaro, Eric Darve 
Publication date: 4 June 2020
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1901.02971
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
Computational methods for sparse matrices (65F50) Complexity and performance of numerical algorithms (65Y20) Preconditioners for iterative methods (65F08) Iterative numerical methods for linear systems (65F10)
Cites Work
- LAPACK Users' Guide
- The university of Florida sparse matrix collection
- PaStiX: A high-performance parallel direct solver for sparse symmetric positive definite systems
- ILUT: A dual threshold incomplete LU factorization
- Rang revealing QR factorizations
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- Existence of \(\mathcal H\)-matrix approximants to the inverse FE-matrix of elliptic operators with \(L^\infty\)-coefficients
- Data-sparse approximation by adaptive \({\mathcal H}^2\)-matrices
- Fast algorithms for hierarchically semiseparable matrices
- Title not available (Why is that?)
- Generalized Nested Dissection
- Title not available (Why is that?)
- A Fast $ULV$ Decomposition Solver for Hierarchically Semiseparable Representations
- Nested Dissection of a Regular Finite Element Mesh
- A fast algorithm for particle simulations
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- Methods of conjugate gradients for solving linear systems
- Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems
- Title not available (Why is that?)
- Domain decomposition based \({\mathcal H}\)-LU preconditioning
- Solution of Sparse Indefinite Systems of Linear Equations
- Title not available (Why is that?)
- A review of algebraic multigrid
- Some Fast Algorithms for Sequentially Semiseparable Representations
- Randomized algorithms for the low-rank approximation of matrices
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- The black-box fast multipole method
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- A fast direct solver for elliptic problems on general meshes in 2D
- On the Compression of Low Rank Matrices
- \(\mathcal H^2\)-matrix approximation of integral operators by interpolation
- Efficient structured multifrontal factorization for general large sparse matrices
- Randomized sparse direct solvers
- A relaxation method for solving elliptic difference equations
- BILUM: Block Versions of Multielimination and Multilevel ILU Preconditioner for General Sparse Linear Systems
- On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic PDEs
- Efficient inversion of the Galerkin matrix of general second-order elliptic operators with nonsmooth coefficients
- Hierarchical Interpolative Factorization for Elliptic Operators: Differential Equations
- An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
- Robust Approximate Cholesky Factorization of Rank-Structured Symmetric Positive Definite Matrices
- Improving Multifrontal Methods by Means of Block Low-Rank Representations
- Fast Hierarchical Solvers For Sparse Matrices Using Extended Sparsification and Low-Rank Approximation
- Strong rank revealing LU factorizations
- Recursively preconditioned hierarchical interpolative factorization for elliptic partial differential equations
- A robust hierarchical solver for ill-conditioned systems with applications to ice sheet modeling
- Effective and Robust Preconditioning of General SPD Matrices via Structured Incomplete Factorization
- ``Compress and Eliminate” Solver for Symmetric Positive Definite Sparse Matrices
Cited In (14)
- Robust and Effective eSIF Preconditioning for General Dense SPD Matrices
- Nested Dissection for Sparse Nullspace Bases
- An Incomplete Cholesky Preconditioner Based on Orthogonal Approximations
- Efficient Construction of an HSS Preconditioner for Symmetric Positive Definite $\mathcal{H}^2$ Matrices
- Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems
- Hierarchical interpolative factorization preconditioner for parabolic equations
- RCHOL: Randomized Cholesky Factorization for Solving SDD Linear Systems
- Hierarchical Orthogonal Factorization: Sparse Square Matrices
- Sparse Hierarchical Preconditioners Using Piecewise Smooth Approximations of Eigenvectors
- FROSch Preconditioners for Land Ice Simulations of Greenland and Antarctica
- A polynomial-time algorithm for computing low CP-rank decompositions
- Matrix sparsification and nested dissection over arbitrary fields
- A fast direct solver for nonlocal operators in wavelet coordinates
- Hierarchical orthogonal factorization: sparse least squares problems
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)
