On the Failure of Rank-Revealing QR Factorization Software -- A Case Study

ABSTRACT

This article reports an unexpected and rather erratic behavior of the LAPACK software implementation of the QR factorization with Businger-Golub column pivoting. It is shown that, due to finite precision arithmetic, the software implementation of the factorization can catastrophically fail to produce a properly structured triangular factor, thus leading to a potentially severe underestimate of a matrix's numerical rank. The 30-year old problem, dating back to LINPACK, has (undetectedly) badly affected many computational routines and software packages, as well as the study of rank-revealing QR factorizations. We combine computer experiments and numerical analysis to isolate, analyze, and fix the problem. Our modification of the current LAPACK xGEQP3 routine is already included in the LAPACK 3.1.0 release. The modified routine is numerically more robust and with a negligible overhead. We also provide a new, equally efficient, and provably numerically safe partial-column norm-updating strategy.

REFERENCES

• 1: Christian H. Bischof , G. Quintana-Ortí, Computing rank-revealing QR factorizations of dense matrices, ACM Transactions on Mathematical Software (TOMS), v.24 n.2, p.226-253, June 1998 [doi>10.1145/290200.287637]
• 2: Businger, P. A. and Golub, G. H. 1965. Linear least squares solutions by Householder transformations. Numerische Mathematik 7, 269--276.
• 3: Shivkumar Chandrasekaran , Ilse C. F. Ipsen, On Rank-Revealing Factorisations, SIAM Journal on Matrix Analysis and Applications, v.15 n.2, p.592-622, April 1994 [doi>10.1137/S0895479891223781]
• 4: Cox, A. J. and Higham, N. J. 1998. Stability of Householder QR factorization for weighted least squares problems. In Proceedings of the 17th Dundee Biennial Conference Numerical Analy sis, D. F. Griffiths et al., eds. Pitman Research Notes in Mathematics, vol. 380. Addison Wesley Longman, Harlow, Essex, UK, 57--73.
• 5: Drmač, Z. 1994. Computing the singular and the generalized singular values. Ph.D. thesis, Lehrgebiet Mathematische Physik, Fernuniversität Hagen.
• 6: Drmač, Z. 1999. A posteriori computation of the singular vectors in a preconditioned Jacobi SVD algorithm. IMA J. Numer. Anal. 19, 191--213.
• 7: Zlatko Drmac , Matjaz Omladic , Kresimir Veselic, On the Perturbation of the Cholesky Factorization, SIAM Journal on Matrix Analysis and Applications, v.15 n.4, p.1319-1332, Oct. 1994 [doi>10.1137/S0895479893244717]
• 8: Zlatko Drmač , Krešimir Veselić, New Fast and Accurate Jacobi SVD Algorithm. I, SIAM Journal on Matrix Analysis and Applications, v.29 n.4, p.1322-1342, November 2007 [doi>10.1137/050639193]
• 9: Zlatko Drmač , Krešimir Veselić, New Fast and Accurate Jacobi SVD Algorithm. II, SIAM Journal on Matrix Analysis and Applications, v.29 n.4, p.1343-1362, November 2007 [doi>10.1137/05063920X]
• 10: Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1996
• 11: Kahan, W. 1966. Numerical linear algebra. Canadian Math. Bull. 9, 6, 757--801.
• 12: Powell, M. J. D. and Reid, J. K. 1969. On applying Householder transformations to linear least squares problems. In Proceedings of the Information Processing 68, Proc. International Federation of Information Processing Congress Conference on Information Proceesing, Edinburgh, UK. North Holland, Amsterdam, 122--126.
• 13: 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]
• 14: Stewart, G. W. 1977. Perturbation bounds for the QR decomposition of a matrix. SIAM J. Numer. Anal. 14, 3, 509--518.
• 15: G. W. Stewart, On the perturbation of LU, Cholesky, and QR factorizations, SIAM Journal on Matrix Analysis and Applications, v.14 n.4, p.1141-1145, Oct. 1993 [doi>10.1137/0614078]
• 16: Ji-Guang Sun, Perturbation bounds for the Cholesky and QR factorizations, BIT, v.31 n.2, p.341-352, 1991 [doi>10.1007/BF01931293]
• 17: K. Veselic , V. Hari, A note on one-sided Jacobi algorithm, Numerische Mathematik, v.56 n.6, p.627-633, Dec. 1989 [doi>10.1007/BF01396349]
• 18: Zha, H. 1997. Singular values of a classical matrix. Amer. Math. Month. 104, 172--173.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Error analysis

Additional Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Reliability and robustness

General Terms:
Algorithms, Reliability, Theory

Keywords:
QR factorization, Rank-revealing, pivoting