L. Schork and J. Gondzio
Abstract
A Gaussian elimination algorithm is presented that reveals the numerical
rank of a matrix by yielding small entries in the Schur complement.
The algorithm uses the maximum volume concept to find a square nonsingular
submatrix of maximum dimension. The bounds on the revealed singular values
are similar to the best known bounds for rank revealing LU factorization,
but in contrast to existing methods the algorithm does not make use
of the normal matrix. An implementation for dense matrices is described
whose computational cost is roughly twice the cost of an LU factorization
with complete pivoting. Because of its exibility in choosing pivot elements,
the algorithm is amenable to implementation with blocked memory access
and for sparse matrices.
Key words: Rank revealing LU, maximum volume.