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://www2.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(n3) to O(n2 + n b2).


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://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