Premium
Matrix stretching for sparse least squares problems
Author(s) -
Adlers Mikael,
Björck Åke
Publication year - 2000
Publication title -
numerical linear algebra with applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.02
H-Index - 53
eISSN - 1099-1506
pISSN - 1070-5325
DOI - 10.1002/(sici)1099-1506(200003)7:2<51::aid-nla187>3.0.co;2-o
Subject(s) - row , mathematics , cholesky decomposition , dimension (graph theory) , matrix (chemical analysis) , least squares function approximation , linear least squares , binary number , factorization , qr decomposition , set (abstract data type) , combinatorics , row and column spaces , sparse matrix , simple (philosophy) , algorithm , eigenvalues and eigenvectors , computer science , statistics , arithmetic , singular value decomposition , materials science , estimator , composite material , gaussian , philosophy , database , epistemology , quantum mechanics , programming language , physics
For linear least squares problems min x ‖ Ax − b ‖ 2 , where A is sparse except for a few dense rows, a straightforward application of Cholesky or QR factorization will lead to catastrophic fill in the factor R . We consider handling such problems by a matrix stretching technique, where the dense rows are split into several more sparse rows. We develop both a recursive binary splitting algorithm and a more general splitting method. We show that for both schemes the stretched problem has the same set of solutions as the original least squares problem. Further, the condition number of the stretched problem differs from that of the original by only a modest factor, and hence the approach is numerically stable. Experimental results from applying the recursive binary scheme to a set of modified matrices from the Harwell‐Boeing collection are given. We conclude that when A has a small number of dense rows relative to its dimension, there is a significant gain in sparsity of the factor R . A crude estimate of the optimal number of splits is obtained by analysing a simple model problem. Copyright © 2000 John Wiley & Sons, Ltd.