Glued Matrices and the MRRR Algorithm | Center for Big Data Analytics

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 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.

Download: pdf

Citation

Glued Matrices and the MRRR Algorithm (pdf, software)
I. Dhillon, B. Parlett, C. Vömel.
SIAM Journal on Scientific Computing 27(2), pp. 496-510, October 2005.

Bibtex:
@article{dhillon2005gluedmatr, author = "Inderjit S. Dhillon AND Beresford N. Parlett AND Christof Vömel", title = "Glued Matrices and the MRRR Algorithm", journal = "SIAM Journal on Scientific Computing", page = "496–510", volume = "27", issue = "2", year = "2005", month = "oct", 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 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." }