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 block algorithm for approximating an RRQR factorization, employing a windowed version of the commonly used Golub pivoting strategy, aided by incremental c...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on mathematical software 1998-06, Vol.24 (2), p.226-253
Main Authors: Bischof, Christian H., Quintana-Ortí, G.
Format: Article
Language:English
Subjects:
Algorithms
Computations on matrices
Computing methodologies
Industrial efficiency
Linear algebra algorithms
Mathematical analysis
Mathematical software
Mathematics of computing
Matrices
Numerical analysis
Symbolic and algebraic algorithms
Symbolic and algebraic manipulation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0098-3500
1557-7295
DOI:10.1145/290200.287637