On using Cholesky-based factorizations and regularization for solving rank-deficient sparse linear least-squares problems

Scott, J. ORCID: https://orcid.org/0000-0003-2130-1091 (2017) On using Cholesky-based factorizations and regularization for solving rank-deficient sparse linear least-squares problems. SIAM Journal on Scientific Computing, 39 (4). C319-C339. ISSN 1095-7197 doi: 10.1137/16M1065380

Abstract/Summary

By examining the performance of modern parallel sparse direct solvers and exploiting our knowledge of the algorithms behind them, we perform numerical experiments to study how they can be used to efficiently solve rank-deficient sparse linear least-squares problems arising from practical applications. The Cholesky factorization of the normal equations breaks down when the least-squares problem is rank-deficient, while applying a symmetric indefinite solver to the augmented system can give an unacceptable level of fill in the factors. To try to resolve these difficulties, we consider a regularization procedure that modifies the diagonal of the unregularized matrix. This leads to matrices that are easier to factorize. We consider both the regularized normal equations and the regularized augmented system. We employ the computed factors of the regularized systems as preconditioners with an iterative solver to obtain the solution of the original (unregularized) problem. Furthermore, we look at using limited-memory incomplete Cholesky-based factorizations and how these can offer the potential to solve very large problems.

Item Type	Article
URI	https://reading-clone.eprints-hosting.org/id/eprint/70577
Item Type	Article
Refereed	Yes
Divisions	Science > School of Mathematical, Physical and Computational Sciences > Department of Mathematics and Statistics
Publisher	Society for Industrial and Applied Mathematics
Download/View statistics	View download statistics for this item