# LAPACK Working Note 163: How the MRRR Algorithm Can Fail on Tight Eigenvalue Clusters

### Beresford N. Parlett and Christof Voemel

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-04-1367

March 2005

### http://www.eecs.berkeley.edu/Pubs/TechRpts/2004/CSD-04-1367.pdf

During the last ten years, 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. It has been incorporated into LAPACK version 3.0 as routine STEGR.

We have discovered that the MRRR algorithm can fail in extreme cases. Sometimes, eigenvalues agree to working accuracy and MRRR cannot compute orthogonal eigenvectors for them. In this paper, we describe and analyze these failures and various remedies. (Revised version)

BibTeX citation:

@techreport{Parlett:CSD-04-1367, Author = {Parlett, Beresford N. and Voemel, Christof}, Title = {LAPACK Working Note 163: How the MRRR Algorithm Can Fail on Tight Eigenvalue Clusters}, Institution = {EECS Department, University of California, Berkeley}, Year = {2005}, Month = {Mar}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2005/6206.html}, Number = {UCB/CSD-04-1367}, Abstract = {During the last ten years, 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. It has been incorporated into LAPACK version 3.0 as routine STEGR. <p> We have discovered that the MRRR algorithm can fail in extreme cases. Sometimes, eigenvalues agree to working accuracy and MRRR cannot compute orthogonal eigenvectors for them. In this paper, we describe and analyze these failures and various remedies. (Revised version)} }

EndNote citation:

%0 Report %A Parlett, Beresford N. %A Voemel, Christof %T LAPACK Working Note 163: How the MRRR Algorithm Can Fail on Tight Eigenvalue Clusters %I EECS Department, University of California, Berkeley %D 2005 %@ UCB/CSD-04-1367 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2005/6206.html %F Parlett:CSD-04-1367