Search from over 60,000 research works

Advanced Search

Sparse stretching for solving sparse-dense linear least-squares problems

[thumbnail of stretch.pdf]
Preview
stretch.pdf - Accepted Version (6MB) | Preview
Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email

Scott, J. orcid id iconORCID: https://orcid.org/0000-0003-2130-1091 and Tuma, M. (2019) Sparse stretching for solving sparse-dense linear least-squares problems. SIAM Journal on Scientific Computing, 41 (3). A1604-A1625. ISSN 1095-7197 doi: 10.1137/18M1181353

Abstract/Summary

Large-scale linear least-squares problems arise in a wide range of practical applications. In some cases, the system matrix contains a small number of dense rows. These make the problem significantly harder to solve because their presence limits the direct applicability of sparse matrix techniques. In particular, the normal matrix is (close to) dense, so that forming it is impractical. One way to help overcome the dense row problem is to employ matrix stretching. Stretching is a sparse matrix technique that improves sparsity by making the least-squares problem larger. We show that standard stretching can still result in the normal matrix for the stretched problem having an unacceptably large amount of fill. This motivates us to propose a new sparse stretching strategy that performs the stretching so as to limit the fill in the normal matrix and its Cholesky factor. Numerical examples from real problems are used to illustrate the potential gains.

Altmetric Badge

Item Type Article
URI https://reading-clone.eprints-hosting.org/id/eprint/82828
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

Downloads

Downloads per month over past year

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

Search Google Scholar