On the existence and computation of rank-revealing LU factorizations (Q1587285)

Exploring the properties of Schur complements, an existence theory for LU factorizations, which is similar to that of rank-revealing QR factorizations, is given. Two algorithms are proposed. Both use Gaussian elimination with a block pivoting technique to select, from the coefficient matrix, a subset of columns each with guaranteed relatively large smallest singular value. Each of the proposed algorithms, for dense matrices, is faster than its orthogonal counterpart. Based on these two algorithms, an algorithm using only Gaussian elimination for computing rank-revealing LU factorizations is introduced. Results of computational experiments are given.