On the existence and computation of rank-revealing LU factorizations Original Research Article

By exploring properties of Schur complements, this paper presents bounds on the existence of rank-revealing LU factorizations that are comparable with those of rank-revealing QR factorizations. The new bounds provide substantial improvement over previously derived bounds. This paper also proposes two algorithms using Gaussian elimination with a “block pivoting” strategy to select a subset of columns from a given matrix which has a guaranteed relatively large smallest singular value. Each of these two algorithms is faster than its orthogonal counterpart for dense matrices. If implemented appropriately, these algorithms are faster than the corresponding rank-revealing QR methods, even when the orthogonal matrices are not explicitly updated. Based on these two algorithms, an algorithm using only Gaussian elimination for computing rank-revealing LU factorizations is introduced.