Computing rank-revealing QR factorizations of dense matrices

ABSTRACT

We develop algorithms and implementations for computing rank-revealing QR (RRQR) factorizations of dense matrices. First, we develop an efficient block algorithm for approximating an RRQR factorization, employing a windowed version of the commonly used Golub pivoting strategy, aided by incremental condition estimation. Second, we develop efficiently implementable variants of guaranteed reliable RRQR algorithms for triangular matrices originally suggested by Chandrasekaran and Ipsen and by Pan and Tang. We suggest algorithmic improvements with respect to condition estimation, termination criteria, and Givens updating. By combining the block algorithm with one of the triangular postprocessing steps, we arrive at an efficient and reliable algorithm for computing an RRQR factorization of a dense matrix. Experimental results on IBM RS/6000 SGI R8000 platforms show that this approach performs up to three times faster that the less reliable QR factorization with column pivoting as it is currently implemented in LAPACK, and comes within 15% of the performance of the LAPACK block algorithm for computing a QR factorization without any column exchanges. Thus, we expect this routine to be useful in may circumstances where numerical rank deficiency cannot be ruled out, but currently has been ignored because of the computational cost of dealing with it.

REFERENCES

• 1: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 2: E. Anderson , Z. Bai , C. Bischof , J. Demmel , J. Dongarra , J. Du Croz , A. Greenbaum , S. Hammarling , A. McKenney , S. Ostrouchov , D. Sorensen, LAPACK's user's guide, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1992
• 3: J. R. Bischof, A block QR factorization algorithm using restricted pivoting, Proceedings of the 1989 ACM/IEEE conference on Supercomputing, p.248-256, November 12-17, 1989, Reno, Nevada, United States [doi>10.1145/76263.76290]
• 4: 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]
• 5: Christian H. Bischof, A parallel QR factorization algorithm with controlled local pivoting, SIAM Journal on Scientific and Statistical Computing, v.12 n.1, p.36-57, Jan. 1991 [doi>10.1137/0912002]
• 6: Christian H. Bischof , Per Christian Hansen, Structure-preserving and rank-revealing QR-factorizations, SIAM Journal on Scientific and Statistical Computing, v.12 n.6, p.1332-1350, Nov. 1991 [doi>10.1137/0912073]
• 7: BISCHOF, C. H. AND HANSEN, P. C. 1992. A block algorithm for computing rank-revealing QR factorizations. Num. Alg. 2, 3-4, 371-392.
• 8: BISCHOF, C. H. AND SHROFF, G. M. 1992. On updating signal subspaces. IEEE Trans. Signal Process. 40, 1, 96-105.
• 9: Christian H. Bischof , Ping T Tang, LAPACK Working Note 33: Robust Incremental Condition Estimation, University of Tennessee, Knoxville, TN, 1991
• 10: CHAN, T. F. 1987. Rank revealing QR factorizations. Lin. Alg. Appl. 88/89, 67-82.
• 11: Tony F. Chan , Per Christian Hansen, Some applications of the rank revealing QR factorization, SIAM Journal on Scientific and Statistical Computing, v.13 n.3, p.727-741, May 1992 [doi>10.1137/0913043]
• 12: CHAN, T. F. AND HANSEN, P. C. 1994. Low-rank revealing QR factorizations. Num. Lin. Alg. Appl. 1, 1, 33-44.
• 13: 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]
• 14: DE HOOG, F. R. AND MATTHEIJ, R. M. M. 1989. Subset selection for matrices. Tech. Rep. RANA 89-07. Dept. of Mathematics and Computing Science, Eindhoven University of Technology, Eindhoven, Netherlands.
• 15: DONGARRA, J. J., MOLER, C. B., BUNCH, J. R., AND STEWART, G.W. 1979. LINPACK Users' Guide. SIAM, Philadelphia, PA.
• 16: Lars Eldén , Robert Schreiber, An aplicaiton of systolic arrays to linear discrete Ill posed problems, SIAM Journal on Scientific and Statistical Computing, v.7 n.3, p.892-903, July 1986 [doi>10.1137/0907060]
• 17: FOSTER, L.V. 1986. Rank and null space calculations using matrix decomposition without column interchanges. Lin. Alg. Appl. 74, 47-71.
• 18: GOLUB, G. g. 1965. Numerical methods for solving linear least squares problems. Numer. Math. 7, 206-216.
• 19: GOLUB, G. g. AND VAN LOAN, C. F. 1983. Matrix Computations. Johns Hopkins University Press, Baltimore, MD.
• 20: Gene H. Golub , Charles F. Van Loan, Matrix computations (3rd ed.), Johns Hopkins University Press, Baltimore, MD, 1996
• 21: G. H. Golub , P. Manneback , Ph. L. Toint, A comparison between some direct and iterative methods for certian large scale godetic least squares problems, SIAM Journal on Scientific and Statistical Computing, v.7 n.3, p.799-816, July 1986 [doi>10.1137/0907053]
• 22: Gene H. Golub , Virginia C. Klema , Gilbert W. Stewart, Rank degeneracy and least squares problems, Stanford University, Stanford, CA, 1976
• 23: GRAGG, W. B. AND STEWART, a.W. 1976. A stable variant of the secant method for solving nonlinear equations. SIAM J. Numer. Anal. 13, 6, 889-903.
• 24: GRANDINE, T.A. 1987. An iterative method for computing multivariate C1 piecewise polynomial interpolants. Comput. Aided Geom. Des. 4, 307-319.
• 25: GRANDINE, T.A. 1989. Rank deficient interpolation and optimal design: An example. Tech. Rep. SCA-TR-113. Engineering and Scientific Services Division, Boeing Computer Services. au, M. AND EISENSTAT, S. 1992. A stable and efficient algorithm for the rank-one modification of the symmetric eigenproblem. Tech. Rep. YALEU/DCS/RR-916. Department of Computer Science, Yale University, New Haven, CT.
• 26: Per Christian Hansen, Truncated singular value decomposition solutions to discrete ill-posed problems with ill-determined numerical rank, SIAM Journal on Scientific and Statistical Computing, v.11 n.3, p.503-518, May 1990 [doi>10.1137/0911028]
• 27: Per Christian Hansen , Takashi Sekii , Hiromoto Shibahashi, The modified truncated SVD method for regularization in general form, SIAM Journal on Scientific and Statistical Computing, v.13 n.5, p.1142-1150, Sept. 1992 [doi>10.1137/0913066]
• 28: Nicholas J Higham, Efficient algorithms for computing the condition number of a tridagonal matrix, SIAM Journal on Scientific and Statistical Computing, v.7 n.1, p.150-165, Jan. 1986 [doi>10.1137/0907011]
• 29: HONG, Y. P. AND PAN, C.-T. 1992. The rank revealing QR decomposition and SVD. Math. Comput. 58, 213-232.
• 30: HOTELLING, g. 1957. The relation of the newer multivariate statistical methods to factor analysis. Br. J. Stat. Psychol. 10, 66-79.
• 31: HSIEH, S. F., LIU, K. J. R., AND YAO, K. 1991. Comparisons of truncated QR and SVD methods for AR spectral estimations. In SVD and Signal Processing H (Amsterdam), R. J. Vaccaro, Ed. Elsevier Sci. Pub. B. V., Amsterdam, The Netherlands, 403-418.
• 32: MORI~, J. 1978. The Levenberg-Marquardt algorithm: Implementation and theory. In Proceedings of the Dundee Conference on Numerical Analysis (Berlin), G. A. Watson, Ed. Springer-Verlag, Berlin, Germany.
• 33: PAN, C.-T. AND TANG, P. T. P. 1992. Bounds on singular values revealed by QR factorization. Tech. Rep. MCS-P332-1092. Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL.
• 34: QUINTANA-ORTI, G. 1996. Guaranteeing termination of Chandrasekaran & Ipsen's algorithm for computing rank-revealing QR factorizations. Preprint MCS-P564-0196. Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL.
• 35: 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]
• 36: L. Reichel , W. B. Gragg, Algorithm 686: FORTRAN subroutines for updating the QR decomposition, ACM Transactions on Mathematical Software (TOMS), v.16 n.4, p.369-377, Dec. 1990 [doi>10.1145/98267.98291]
• 37: Robert Schreiber , Charles van Loan, A storage-efficient WY representation for products of householder transformations, SIAM Journal on Scientific and Statistical Computing, v.10 n.1, p.53-57, January 1989 [doi>10.1137/0910005]
• 38: STEWART, a.W. 1984. Rank degeneracy. SIAM J. Sci. Stat. Comput. 5, 403-413.
• 39: G. W. Stewart, An updating algorithm for subspace tracking, University of Maryland at College Park, College Park, MD, 1990
• 40: G. W. Stewart, Determining rank in the presence of error, University of Maryland at College Park, College Park, MD, 1992
• 41: WALDI~N, B. 1991. Using a fast signal processor to solve the inverse kinematic problem with special emphasis on the singularity problem. Ph.D. Dissertation. Department of Mathematics, Link~ping University.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing

General Terms:
Algorithms, Performance

Keywords:
QR factorization, block algorithm, least-squares systems, numerical rank, rank-revealing orthogonal factorization