Computing rank-revealing QR factorizations of dense matrices

We develop algorithms and implementations for computing rank-revealing QR ( RRQR) factorizations of dense matrices. First, we develop an efficient bloc k algorithm for approximating an RRQR factorization, employing a windowed v ersion of the commonly used Golub pivoting strategy, aided by incremental c ondition estimation. Second, we develop efficiently implementable variants of guaranteed reliable RRQR algorithms for triangular matrices originally s uggested by Chandrasekaran and Ipsen and by Pan and Tang. We suggest algori thmic improvements with respect to condition estimation, termination criter ia, and Givens updating. By combining the block algorithm with one of the t riangular postprocessing steps, we arrive at an efficient and reliable algo rithm for computing an RRQR factorization of a dense matrix. Experimental r esults on IBM RS/6000 and SGI R8000 platforms show that this approach perfo rms up to three times faster than the less reliable QR factorization with c olumn pivoting as it is currently implemented in LAPACK, and comes within 1 5% of the performance of the LAPACK block algorithm for computing a QR fact orization without any column exchanges. Thus, we expect this routine to be useful in many circumstances where numerical rank deficiency cannot be rule d out, but currently has been ignored because of the computational cost of dealing with it.