Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices

In this paper we present an O(nk) procedure, Algorithm MR3, for computing k eigenvectors of an n x 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. (C) 2004 Elsevier Inc. All rights reserved.