Deviation Maximization for Rank-Revealing QR Factorizations

In this paper we introduce a new column selection strategy, named here ``Deviation Maximization", and apply it to compute rank-revealing QR factorizations as an alternative to the well known block version of the QR factorization with the column pivoting method, called QP3 and currently implemented in LAPACK's exttt{xgeqp3} routine. We show that the resulting algorithm, named QRDM, has similar rank-revealing properties of QP3 and better execution times. We present numerical test results on a wide data set of numerically singular matrices, which has become a reference in the recent literature.