Hierarchical orthogonal factorization: sparse least squares problems
From MaRDI portal
Numerical solutions to overdetermined systems, pseudoinverses (65F20) Orthogonalization in numerical linear algebra (65F25) Computational methods for sparse matrices (65F50) Numerical methods for low-rank matrix approximation; matrix compression (65F55) Complexity and performance of numerical algorithms (65Y20)
Abstract: In this work, we develop a fast hierarchical solver for solving large, sparse least squares problems. We build upon the algorithm, spaQR (sparsified QR), that was developed by the authors to solve large sparse linear systems. Our algorithm is built on top of a Nested Dissection based multifrontal QR approach. We use low-rank approximations on the frontal matrices to sparsify the vertex separators at every level in the elimination tree. Using a two-step sparsification scheme, we reduce the number of columns and maintain the ratio of rows to columns in each front without introducing any additional fill-in. With this improvised scheme, we show that the runtime of the algorithm scales as and uses memory to store the factorization. This is achieved at the expense of a small and controllable approximation error. The end result is an approximate factorization of the matrix stored as a sequence of sparse orthogonal and upper-triangular factors and hence easy to apply/solve with a vector. Finally, we compare the performance of the spaQR algorithm in solving sparse least squares problems with direct multifrontal QR and CGLS iterative method with a standard diagonal preconditioner.
Recommendations
- Hierarchical orthogonal factorization: sparse square matrices
- Multifrontal Computation with the Orthogonal Factors of Sparse Matrices
- MIQR: A Multilevel Incomplete QR Preconditioner for Large Sparse Least‐Squares Problems
- A coarse-grained parallel QR-factorization algorithm for sparse least squares problems
- Parallel Sparse Orthogonal Factorization on Distributed-Memory Multiprocessors
Cites work
- 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 Robust Preconditioner with Low Memory Requirements for Large Sparse Least Squares Problems
- An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
- An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
- An Incomplete Factorization Technique for Positive Definite Linear Systems
- Convergence of inner-iteration GMRES methods for rank-deficient least squares problems
- 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
- Hierarchical interpolative factorization for elliptic operators: differential equations
- Hierarchical interpolative factorization for elliptic operators: integral equations
- Hierarchical interpolative factorization preconditioner for parabolic equations
- Hierarchical orthogonal factorization: sparse square matrices
- scientific article; zbMATH DE number 1069612 (Why is no real title available?)
- scientific article; zbMATH DE number 852536 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Implementing a smooth exact penalty function for equality-constrained nonlinear optimization
- Incomplete Methods for Solving A^T Ax = b
- Inner-Iteration Krylov Subspace Methods for Least Squares Problems
- LSMR: An Iterative Algorithm for Sparse Least-Squares Problems
- LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
- Methods of conjugate gradients for solving linear systems
- MIQR: A Multilevel Incomplete QR Preconditioner for Large Sparse Least‐Squares Problems
- Nested Dissection of a Regular Finite Element Mesh
- Numerical methods for solving linear least squares problems
- On the QR decomposition of \({\mathcal {H}}\)-matrices
- Preconditioning of linear least squares by robust incomplete factorization for implicitly held normal equations
- Preconditioning techniques for nonsymmetric and indefinite linear systems
- Recursively preconditioned hierarchical interpolative factorization for elliptic partial differential equations
- Stability analysis of the method of seminormal equations for linear least squares problems
- Superfast and stable structured solvers for Toeplitz least squares via randomized sampling
- Superfast Multifrontal Method for Large Structured Linear Systems of Equations
- The University of Florida sparse matrix collection
Cited in
(7)- Separators and structure prediction in sparse orthogonal factorization
- Multifrontal Computation with the Orthogonal Factors of Sparse Matrices
- Hierarchical orthogonal factorization: sparse square matrices
- [HDDA] sparse subspace constrained partial least squares
- An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
- TR-STF: a fast and accurate tensor ring decomposition algorithm via defined scaled tri-factorization
- Sparse linear least-squares problems
This page was built for publication: Hierarchical orthogonal factorization: sparse least squares problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2147465)
