Efficient algorithms for computing a strong rank-revealing QR factorization

• Published in: SIAM journal on scientific computing 1996-07, Vol.17 (4), p.848-869
• Main Authors: GU, M, EISENSTAT, S. C
• Format: Article
• Language: English
• Subjects: Algebra; Algorithms; Exact sciences and technology; Linear and multilinear algebra, matrix theory; Mathematics; Numerical analysis; Numerical analysis. Scientific computation; Numerical linear algebra; Sciences and techniques of general use
• ISSN: 1064-8275; 1095-7197
• DOI: 10.1137/0917055

Given an $m \times n$ matrix $M$ with $m \geqslant n$, it is shown that there exists a permutation $\Pi $ and an integer $k$ such that the QR factorization \[ M\Pi = Q\left( {\begin{array}{*{20}c} {A_k } & {B_k } \\ {} & {C_k } \\ \end{array} } \right) \] reveals the numerical rank of $M$: the $k \times k$ upper-triangular matrix $A_k $ is well conditioned, $\|C_k \|_2 $ is small, and $B_k $is linearly dependent on $A_k $ with coefficients bounded by a low-degree polynomial in n. Existing rank-revealing QR (RRQR) algorithms are related to such factorizations and two algorithms are presented for computing them. The new algorithms are nearly as efficient as QR with column pivoting for most problems and take $O(mn^2 )$ floating-point operations in the worst case.