Computing rank-revealing QR factorizations of dense matrices
Authors:
Open Access
- 1 June 1998
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Mathematical Software
- Vol. 24 (2) , 226-253
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.Keywords
This publication has 25 references indexed in Scilit:
- On Rank-Revealing FactorisationsSIAM Journal on Matrix Analysis and Applications, 1994
- Low‐rank revealing QR factorizationsNumerical Linear Algebra with Applications, 1994
- On updating signal subspacesIEEE Transactions on Signal Processing, 1992
- Algorithm 686: FORTRAN subroutines for updating the QR decompositionACM Transactions on Mathematical Software, 1990
- An iterative method for computing multivariate C1 piecewise polynomial interpolantsComputer Aided Geometric Design, 1987
- Rank revealing QR factorizationsLinear Algebra and its Applications, 1987
- Efficient Algorithms for Computing the Condition Number of a Tridiagonal MatrixSIAM Journal on Scientific and Statistical Computing, 1986
- Rank DegeneracySIAM Journal on Scientific and Statistical Computing, 1984
- A Stable Variant of the Secant Method for Solving Nonlinear EquationsSIAM Journal on Numerical Analysis, 1976
- THE RELATIONS OF THE NEWER MULTIVARIATE STATISTICAL METHODS TO FACTOR ANALYSISBritish Journal of Statistical Psychology, 1957