A New O(n2) Algorithm for the Symmetric Tridiagonal Eigenvalue/Eigenvector Problem
Abstract
Computing the eigenvalues and orthogonal eigenvectors of an n x n symmetric tridiagonal matrix is an important task that arises while solving any symmetric eigenproblem. All practical software requires O(n3) time to compute all the eigenvectors and ensure their orthogonality when eigenvalues are close. In the first part of this thesis we review earlier work and show how some existing implementations of inverse iteration can fail in surprising ways. The main contribution of this thesis is a new O(n^2), easily parallelizable algorithm for solving the tridiagonal eigenproblem. Three main advances lead to our new algorithm. A tridiagonal matrix is traditionally represented by its diagonal and off-diagonal elements. Our most important advance is in recognizing that its bidiagonal factors are "better" for computational purposes. The use of bidiagonals enables us to invoke a relative criterion to judge when eigenvalues are "close". The second advance comes by using multiple bidiagonal factorizations in order to compute different eigenvectors independently of each other. Thirdly, we use carefully chose dqds-like transformations as inner loops to compute eigenpairs that are highly accurate and "faithful" to the various bidiagonal representations. Orthogonality of the eigenvectors is a consequence of this accuracy. Only O(n) work per eigenpair is needed by our new algorithm. An interesting aspect of our work is that increased accuracy in the eigenvalues and eigenvectors obviates the need for explicit orthogonalization and leads to greater speed. We present timing and accuracy results comparing a computer implementation of our new algorithm with four existing EISPACK and LAPACK software routines. Our test-bed contains a variety of tridiagonal matrices, some coming from quantum chemistry applications. The numerical results demonstrate the superiority of our new algorithm.
Document Details
- Document Type
- Technical Report
- Publication Date
- Oct 01, 1997
- Accession Number
- ADA637073
Entities
People
- Inderjit S. Dhillon
Organizations
- University of California, Berkeley