Nonnegative Diagonals and High Performance on Low-Profile Matrices from Householder QR
James Weldon Demmel, Mark Frederick Hoemmen, Yozo Hida, Jason Riedy · SIAM Journal on Scientific Computing · 2009
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 nonnegative diagonal. This note describes a new Householder generation routine to produce a nonnegative 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 nonzero entries mostly near the diagonal (e.g., band matrices), now require far fewer operations. For example, $QR$ factorization of matrices with profile width b that are stored densely in an $n\times n$ matrix improves from $O(n^3)$ to $O(n^2+nb^2)$. These routines are in LAPACK 3.2.