Hierarchical orthogonal factorization: sparse least squares problems
From MaRDI portal
Computational methods for sparse matrices (65F50) Complexity and performance of numerical algorithms (65Y20) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Orthogonalization in numerical linear algebra (65F25) Numerical methods for low-rank matrix approximation; matrix compression (65F55)
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
- 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?)
- A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs
- A Robust Preconditioner with Low Memory Requirements for Large Sparse Least Squares Problems
- A fast algorithm for particle simulations
- A fast direct solver for elliptic problems on general meshes in 2D
- An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
- An Incomplete Factorization Technique for Positive Definite Linear Systems
- An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
- 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
- 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
- MIQR: A Multilevel Incomplete QR Preconditioner for Large Sparse Least‐Squares Problems
- Methods of conjugate gradients for solving linear systems
- 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 Multifrontal Method for Large Structured Linear Systems of Equations
- Superfast and stable structured solvers for Toeplitz least squares via randomized sampling
- The University of Florida sparse matrix collection
Cited in
(7)- Multifrontal Computation with the Orthogonal Factors of Sparse Matrices
- Sparse linear least-squares problems
- [HDDA] sparse subspace constrained partial least squares
- TR-STF: a fast and accurate tensor ring decomposition algorithm via defined scaled tri-factorization
- An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
- Separators and structure prediction in sparse orthogonal factorization
- Hierarchical orthogonal factorization: sparse square matrices
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)
