Hierarchical orthogonal factorization: sparse square matrices
From MaRDI portal
Publication:5028554
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 .
Recommendations
- Hierarchical orthogonal factorization: sparse least squares problems
- An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
- Multifrontal Computation with the Orthogonal Factors of Sparse Matrices
- Algorithm 915: SuiteSparseQR: multifrontal multithreaded rank-revealing sparse QR factorization
- A Data Structure for Sparse $QR$ and $LU$ Factorizations
Cites work
- scientific article; zbMATH DE number 1226271 (Why is no real title available?)
- scientific article; zbMATH DE number 1069612 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- A direct solver with \(O(N)\) complexity for variable coefficient elliptic PDEs discretized via a high-order composite spectral collocation method
- A fast algorithm for particle simulations
- A fast direct solver for elliptic problems on general meshes in 2D
- A sparse \({\mathcal H}\)-matrix arithmetic: General complexity estimates
- A sparse matrix arithmetic based on \({\mathfrak H}\)-matrices. I: Introduction to \({\mathfrak H}\)-matrices
- Algorithm 915: SuiteSparseQR: multifrontal multithreaded rank-revealing sparse QR factorization
- An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
- An Incomplete Factorization Technique for Positive Definite Linear Systems
- An adaptive high order direct solution technique for elliptic boundary value problems
- An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
- Construction and arithmetics of \(\mathcal H\)-matrices
- Effective and robust preconditioning of general SPD matrices via structured incomplete factorization
- Efficient structured multifrontal factorization for general large sparse matrices
- Experimental study of ILU preconditioners for indefinite matrices
- Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
- Fine-grained multithreading for the multifrontal \(QR\) factorization of sparse matrices
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- Hierarchical interpolative factorization for elliptic operators: integral equations
- Hierarchical interpolative factorization preconditioner for parabolic equations
- Hypergraph-based unsymmetric nested dissection ordering for sparse LU factorization
- ILUT: A dual threshold incomplete LU factorization
- Incomplete Methods for Solving $A^T Ax = b$
- Methods of conjugate gradients for solving linear systems
- Nested Dissection of a Regular Finite Element Mesh
- On the Complexity of Sparse $QR$ and $LU$ Factorization of Finite-Element Matrices
- On the QR decomposition of \({\mathcal {H}}\)-matrices
- Preconditioning techniques for nonsymmetric and indefinite linear systems
- Recursively preconditioned hierarchical interpolative factorization for elliptic partial differential equations
- Reordering strategy for blocking optimization in sparse linear solvers
- Solution of Sparse Indefinite Systems of Linear Equations
- Sparse Hierarchical Preconditioners Using Piecewise Smooth Approximations of Eigenvectors
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- The Role of Elimination Trees in Sparse Factorization
- The University of Florida sparse matrix collection
- Two Fast Algorithms for Sparse Matrices: Multiplication and Permuted Transposition
Cited in
(6)- Separators and structure prediction in sparse orthogonal factorization
- Fast structured LU factorization for nonsymmetric matrices
- Second‐order accurate hierarchical approximate factorizations for solving sparse linear systems
- A block Householder-based algorithm for the QR decomposition of hierarchical matrices
- An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
- Hierarchical orthogonal factorization: sparse least squares problems
Describes a project that uses
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)
