Accessibility navigation


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

[img]
Preview
Text (Open Access) - Published Version
· Available under License Creative Commons Attribution No Derivatives.
· Please see our End User Agreement before downloading.

451kB

It is advisable to refer to the publisher's version if you intend to cite from this work. See Guidance on citing.

To link to this item 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.

Item Type:Article
Divisions:Science > School of Mathematical, Physical and Computational Sciences > Department of Mathematics and Statistics
ID Code:103835
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)

Downloads

Downloads per month over past year

University Staff: Request a correction | Centaur Editors: Update this record

Page navigation