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

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2008-76

May 30, 2008

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

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 &#215; n</i> matrix improves from <i>O(n³)</i> to <i>O(n² + n b²)</i>.

---

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},
    Year= {2008},
    Month= {May},
    Url= {http://www2.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 &#215; 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://www2.eecs.berkeley.edu/Pubs/TechRpts/2008/EECS-2008-76.html
%F Demmel:EECS-2008-76