Algorithm 853: An efficient algorithm for solving rank-deficient least squares problems

ABSTRACT

Existing routines, such as xGELSY or xGELSD in LAPACK, for solving rank-deficient least squares problems require O(mn²) operations to solve min ‖b − Ax‖ where A is an m by n matrix. We present a modification of the LAPACK routine xGELSY that requires O(mnk) operations where k is the effective numerical rank of the matrix A. For low rank matrices the modification is an order of magnitude faster than the LAPACK code.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , L. S. Blackford , J. Demmel , Jack J. Dongarra , J. Du Croz , S. Hammarling , A. Greenbaum , A. McKenney , D. Sorensen, LAPACK Users' guide (third ed.), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 2: Christian H. Bischof, Incremental condition estimation, SIAM Journal on Matrix Analysis and Applications, v.11 n.2, p.312-322, Apr. 1990 [doi>10.1137/0611021]
• 3: C. H. Bischof , G. Quintana-Ortí, Algorithm 782: codes for rank-revealing QR factorizations of dense matrices, ACM Transactions on Mathematical Software (TOMS), v.24 n.2, p.254-257, June 1998 [doi>10.1145/290200.287638]
• 4: Businger, P. and Golub, G. H. 1965. Linear least squares solutions by Householder transformations. Numer. Math. 7, 269--276.
• 5: Ming Gu , Stanley C. Eisenstat, Efficient algorithms for computing a strong rank-revealing QR factorization, SIAM Journal on Scientific Computing, v.17 n.4, p.848-869, July 1996 [doi>10.1137/0917055]
• 6: Enting, I. G. 2002. Inverse Problems in Atmospheric Constituent Transport. Cambridge University Press, Cambridge.
• 7: Leslie V. Foster, Solving Rank-Deficient and Ill-posed Problems Using UTV and QR Factorizations, SIAM Journal on Matrix Analysis and Applications, v.25 n.2, p.582-600, 2003 [doi>10.1137/S089547980037785X]
• 8: Golub, G. and VanLoan, C. F. 1996. Matrix Computations. John Hopkins, Baltimore, Md.
• 9: Per Christian Hansen, Rank-deficient and discrete ill-posed problems: numerical aspects of linear inversion, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 10: Gregorio Quintana-Ortí , Xiaobai Sun , Christian H. Bischof, A BLAS-3 Version of the QR Factorization with Column Pivoting, SIAM Journal on Scientific Computing, v.19 n.5, p.1486-1494, Sept. 1998 [doi>10.1137/S1064827595296732]
• 11: Stewart, G. W. 1998. Matrix Algorithms vol. 1: Basic Decompositions. SIAM, Philadelphia.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: FORTRAN 77

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra

General Terms:
Algorithms, Performance

Keywords:
Least squares, QR factorization, rank-deficient