Notes on TQR algorithms

Historically, the algorithm for completely solving the symmetric tridiagonal eigenvalue problem is the TQR algorithm. Rational variants of TQR were used when only the complete spectrum of eigenvalues was desired since they have the advantage of avoiding square roots. Several historical variants of TQR use fewer operations than the one used in LAPACK; however, these variants have known accuracy problems. In this paper a new variant of TQR is developed which is similar to parts of the variant proposed by Sack (1972). This variant has fewer operations than the one in LAPACK, which results in faster timings, and it avoids the accuracy problems of the other historical variants. In addition, it is shown how the eigenvectors can be recovered from the rational algorithms.