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

### James Demmel, Mark Frederick Hoemmen, Yozo Hida and Jason Riedy

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/EECS-2008-76

May 30, 2008

### http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-76.pdf

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 (
*e.g.* 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(n ^{3})* to

*O(n*.

^{2}+ n b^{2})BibTeX citation:

@techreport{Demmel:EECS-2008-76, Author = {Demmel, James and Hoemmen, Mark Frederick and Hida, Yozo and Riedy, Jason}, Title = {Non-Negative Diagonals and High Performance on Low-Profile Matrices from Householder QR}, Institution = {EECS Department, University of California, Berkeley}, Year = {2008}, Month = {May}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-76.html}, Number = {UCB/EECS-2008-76}, Abstract = {The Householder reflections used in LAPACK's <i>QR</i> factorization leave positive and negative real entries along <i>R</i>'s diagonal. This is sufficient for most applications of <i>QR</i> factorizations, but a few require that <i>R</i> 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 (<i>e.g.</i> band matrices), now requires far fewer operations. For example, <i>QR</i> factorization of matrices with profile width <i>b</i> that are stored densely in an <i>n × n</i> matrix improves from <i>O(n<sup>3</sup>)</i> to <i>O(n<sup>2</sup> + n b<sup>2</sup>)</i>.} }

EndNote citation:

%0 Report %A Demmel, James %A Hoemmen, Mark Frederick %A Hida, Yozo %A Riedy, Jason %T Non-Negative Diagonals and High Performance on Low-Profile Matrices from Householder QR %I EECS Department, University of California, Berkeley %D 2008 %8 May 30 %@ UCB/EECS-2008-76 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-76.html %F Demmel:EECS-2008-76