Hierarchical Orthogonal Factorization: Sparse Square Matrices
From MaRDI portal
Publication:5028554
DOI10.1137/20M1373475zbMATH Open1482.65069arXiv2010.06807OpenAlexW3093305795WikidataQ114074142 ScholiaQ114074142MaRDI QIDQ5028554FDOQ5028554
Abeynaya Gnanasekaran, Eric Darve
Publication date: 10 February 2022
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
Abstract: In this work, we develop a new fast algorithm, spaQR -- sparsified QR, for solving large, sparse linear systems. The key to our approach is using low-rank approximations to sparsify the separators in a Nested Dissection based Householder QR factorization. First, a modified version of Nested Dissection is used to identify interiors/separators and reorder the matrix. Then, classical Householder QR is used to factorize the interiors, going from the leaves to the root to the elimination tree. After every level of interior factorization, we sparsify the remaining separators by using low-rank approximations. This operation reduces the size of the separators without introducing any fill-in in the matrix. However, it introduces a small approximation error which can be controlled by the user. The resulting approximate factorization is stored as a sequence of sparse orthogonal and sparse upper-triangular factors. Hence, it can be applied efficiently to solve linear systems. Additionally, we further improve the algorithm by using a block diagonal scaling. Then, we show a systematic analysis of the approximation error and effectiveness of the algorithm in solving linear systems. Finally, we perform numerical tests on benchmark unsymmetric problems to evaluate the performance of the algorithm. The factorization time scales as and the solve time scales as .
Full work available at URL: https://arxiv.org/abs/2010.06807
Computational methods for sparse matrices (65F50) Complexity and performance of numerical algorithms (65Y20) Preconditioners for iterative methods (65F08) Orthogonalization in numerical linear algebra (65F25)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- The university of Florida sparse matrix collection
- ILUT: A dual threshold incomplete LU factorization
- 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
- Hierarchical interpolative factorization for elliptic operators: integral equations
- Nested Dissection of a Regular Finite Element Mesh
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- Methods of conjugate gradients for solving linear systems
- Construction and arithmetics of \(\mathcal H\)-matrices
- Algorithm 915, SuiteSparseQR
- Solution of Sparse Indefinite Systems of Linear Equations
- Experimental study of ILU preconditioners for indefinite matrices
- The Role of Elimination Trees in Sparse Factorization
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- An Incomplete Factorization Technique for Positive Definite Linear Systems
- An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
- A fast direct solver for elliptic problems on general meshes in 2D
- A fast algorithm for particle simulations
- On the QR decomposition of \({\mathcal {H}}\)-matrices
- Efficient Structured Multifrontal Factorization for General Large Sparse Matrices
- An Adaptive High Order Direct Solution Technique for Elliptic Boundary Value Problems
- Preconditioning techniques for nonsymmetric and indefinite linear systems
- A sparse \({\mathcal H}\)-matrix arithmetic: General complexity estimates
- Two Fast Algorithms for Sparse Matrices: Multiplication and Permuted Transposition
- On the Complexity of Sparse $QR$ and $LU$ Factorization of Finite-Element Matrices
- An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
- Fast Hierarchical Solvers For Sparse Matrices Using Extended Sparsification and Low-Rank Approximation
- A Direct Solver with $O(N)$ Complexity for Variable Coefficient Elliptic PDEs Discretized via a High-Order Composite Spectral Collocation Method
- Incomplete Methods for Solving $A^T Ax = b$
- Fine-grained multithreading for the multifrontal \(QR\) factorization of sparse matrices
- Hypergraph-Based Unsymmetric Nested Dissection Ordering for Sparse LU Factorization
- Recursively preconditioned hierarchical interpolative factorization for elliptic partial differential equations
- Effective and Robust Preconditioning of General SPD Matrices via Structured Incomplete Factorization
- Hierarchical interpolative factorization preconditioner for parabolic equations
- Reordering Strategy for Blocking Optimization in Sparse Linear Solvers
- Sparse Hierarchical Preconditioners Using Piecewise Smooth Approximations of Eigenvectors
Cited In (4)
- Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems
- An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
- Separators and structure prediction in sparse orthogonal factorization
- Hierarchical orthogonal factorization: sparse least squares problems
Uses Software
This page was built for publication: Hierarchical Orthogonal Factorization: Sparse Square Matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5028554)
