Abstract: In this paper we present an O(nk) procedure, Algorithm MR3, for computing k eigenvectors of an n × n symmetric tridiagonal matrix T . A salient feature of the algorithm is that a number of different LDLt products (L unit lower triangular, D diagonal) are computed. In exact arithmetic each LDLt is a factorization of a translate of T . We call the various LDLt products representations (of T ) and, roughly speaking, there is a representation for each cluster of close eigenvalues. The unfolding of the algorithm, for each matrix, is well described by a representation tree. We present the tree and use it to show that if each representation satisfies three prescribed conditions then the computed eigenvectors are orthogonal to working accuracy and have small residual norms with respect to the original matrix T .
- Multiple Representations to Compute Orthogonal Eigenvectors of Symmetric Tridiagonal Matrices (pdf, software)
I. Dhillon, B. Parlett.
Linear Algebra and its Applications 387, pp. 1-28, August 2004.