LAPACK Working Note 162: The Design and Implementation of the MRRR Algorithm

Inderjit Dhillon, Beresford N. Parlett and Christof Voemel

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-04-1346
2004

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/CSD-04-1346.pdf

In the 90s, Dhillon and Parlett devised a new algorithm (Multiple Relatively Robust Representations, MRRR) for computing numerically orthogonal eigenvectors of a symmetric tridiagonal matrix T with O( n^2) cost. While previous publications related to MRRR have as focus the theoretical aspects, a documentation of software issues has been missing. In this paper, we discuss the design and implementation of the new MRRR version STEGR that is going to be included in a future release of LAPACK. By giving an algorithmic description of MRRR and identifying governing parameters, we hope to make STEGR more easily accessible and suitable for future performance tuning. Furthermore, this should help users understand design choices and tradeoffs when using the code.


BibTeX citation:

@techreport{Dhillon:CSD-04-1346,
    Author = {Dhillon, Inderjit and Parlett, Beresford N. and Voemel, Christof},
    Title = {LAPACK Working Note 162: The Design and Implementation of the MRRR Algorithm},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2004},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5918.html},
    Number = {UCB/CSD-04-1346},
    Abstract = {In the 90s, Dhillon and Parlett devised a new algorithm (Multiple Relatively Robust Representations, MRRR) for computing numerically orthogonal eigenvectors of a symmetric tridiagonal matrix <i>T</i> with <i>O</i>(<i>n</i>^2) cost. While previous publications related to MRRR have as focus the theoretical aspects, a documentation of software issues has been missing. In this paper, we discuss the design and implementation of the new MRRR version STEGR that is going to be included in a future release of LAPACK. By giving an algorithmic description of MRRR and identifying governing parameters, we hope to make STEGR more easily accessible and suitable for future performance tuning. Furthermore, this should help users understand design choices and tradeoffs when using the code.}
}

EndNote citation:

%0 Report
%A Dhillon, Inderjit
%A Parlett, Beresford N.
%A Voemel, Christof
%T LAPACK Working Note 162: The Design and Implementation of the MRRR Algorithm
%I EECS Department, University of California, Berkeley
%D 2004
%@ UCB/CSD-04-1346
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2004/5918.html
%F Dhillon:CSD-04-1346