Non-Negative Diagonals and High Performance on Low-Profile Matrices from Householder QR

摘要: The Householder reflections used in LAPACK’s QR factorization leave positive and negative real entries along R’s diagonal. This is sufficient for most applications of QR factorizations, but a few require that R have a non-negative diagonal. This note provides a new Householder generation routine to produce a non-negative diagonal. Additionally, we find that scanning for trailing zeros in the generated reflections leads to large performance improvements when applying reflections with many trailing zeros. Factoring low-profile matrices, those with non-zero entries mostly near the diagonal (eg band matrices), now requires far fewer operations. For example, QR factorization of matrices with profile width b that are stored densely in an n× n matrix improves from O (n3) to O (n2+ nb2).