A computational study of using black-box QR solvers for large-scale sparse-dense linear least squares problems

Scott, J. ORCID: https://orcid.org/0000-0003-2130-1091 and Tůma, M. (2022) A computational study of using black-box QR solvers for large-scale sparse-dense linear least squares problems. ACM Transactions on Mathematical Software, 48 (1). pp. 1-24. ISSN 1557-7295 doi: 10.1145/3494527

Abstract/Summary

Large-scale overdetermined linear least squares problems arise in many practical applications. One popular solution method is based on the backward stable QR factorization of the system matrix A . This article focuses on sparse-dense least squares problems in which A is sparse except from a small number of rows that are considered dense. For large-scale problems, the direct application of a QR solver either fails because of insufficient memory or is unacceptably slow. We study several solution approaches based on using a sparse QR solver without modification, focussing on the case that the sparse part of A is rank deficient. We discuss partial matrix stretching and regularization and propose extending the augmented system formulation with iterative refinement for sparse problems to sparse-dense problems, optionally incorporating multi-precision arithmetic. In summary, our computational study shows that, before applying a black-box QR factorization, a check should be made for rows that are classified as dense and, if such rows are identified, then A should be split into sparse and dense blocks; a number of ways to use a black-box QR factorization to exploit this splitting are possible, with no single method found to be the best in all cases.

Additional Information	** From Crossref journal articles via Jisc Publications Router ** Journal IDs: pissn 0098-3500; eissn 1557-7295 ** History: issued 31-03-2022; published 31-03-2022
Item Type	Article
URI	https://reading-clone.eprints-hosting.org/id/eprint/103835
Identification Number/DOI	10.1145/3494527
Divisions	Science > School of Mathematical, Physical and Computational Sciences > Department of Mathematics and Statistics
Uncontrolled Keywords	Applied Mathematics, Software
Additional Information	** From Crossref journal articles via Jisc Publications Router ** Journal IDs: pissn 0098-3500; eissn 1557-7295 ** History: issued 31-03-2022; published 31-03-2022
Publisher	Association for Computing Machinery (ACM)
Download/View statistics	View download statistics for this item