zbMATH — the first resource for mathematics

Matrix stretching for sparse least squares problems. (English) Zbl 0982.65046
Summary: 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 signification gain in sparsity of the factor \(R\). A crude estimate of the optimal number of splits is obtained by analysing a simple model problem.

65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F50 Computational methods for sparse matrices
Full Text: DOI
[1] Numerical Methods for Least Squares Problems. SIAM: Philadelphia, PA, 1996. · doi:10.1137/1.9781611971484
[2] Coleman, Journal of the Association of Computing Machinery 33 pp 517– (1986) · Zbl 0635.65036 · doi:10.1145/5925.5932
[3] Heath, SIAM Journal on Scientific and Statistical Computing 3 pp 223– (1982) · Zbl 0483.65027 · doi:10.1137/0903014
[4] Björck, SIAM Journal on Scientific and Statistical Computing 5 pp 394– (1984) · Zbl 0562.65018 · doi:10.1137/0905029
[5] Dealing with dense rows in the solution of sparse linear least squares problems. Technical report, Advanced Computing Research Institute, Cornell University, Ithaca, NY, 1996.
[6] and A robust method for handling dense rows in a sparse QR or RRQR factorization. Technical Report, Boeing Information and Support Services, Seattle, WA, October 31, 1996.
[7] Matrix stretching for linear equations, Technical Report SAND90-8723, Sandia National Laboratories, November 1990.
[8] Alvarado, BIT 37 pp 473– (1997) · Zbl 0883.65036 · doi:10.1007/BF02510237
[9] Vanderbei, Linear Algebra and Applications 152 pp 107– (1991) · Zbl 0727.65034 · doi:10.1016/0024-3795(91)90269-3
[10] Sparse orthogonal estimation with dense rows. Report ECE-96-7, The University of Wisconsin, Madison, October 1996.
[11] and User’s guide for Harwell-Boeing sparse matrix test problems collection, Technical Report RAL-92-086, Computing and Information Systems Department, Rutherford Appleton Laboratory, Didcot, UK, 1992.
[12] Matstoms, ACM Transactions on Mathematical Software 20 pp 136– (1994) · Zbl 0888.65022 · doi:10.1145/174603.174408
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.