Abstract: Computing the eigenvalues and orthogonal eigenvectors of an n × n symmetric tridiagonal
matrix is an important task that arises while solving any symmetric eigenproblem. All
practical software requires O(n
3
) 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.
Computing the eigenvalues and orthogonal eigenvectors of an n × n symmetric tridiagonal
matrix is an important task that arises while solving any symmetric eigenproblem. All
practical software requires O(n
3
) 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 advances comes by using multiple bidiagonal factorizations in order to compute different eigenvectors independently of each other. of each other.
Conventional wisdom is that there is usually a trade-off between speed and accuracy in numerical procedures, i.e., higher accuracy can be achieved only at the expense of greater computing time. 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. For
example, on a matrix of order 966 that occurs in the modeling of a biphenyl molecule
our method is about 10 times faster than LAPACK’s inverse iteration on a serial IBM
RS/6000 processor and nearly 100 times faster on a 128 processor IBM SP2 parallel machine.
Download: pdf
Citation
- A New O(N^2) Algorithm for the Symmetric Tridiagonal Eigenvalue/Eigenvector Problem (pdf, software)
I. Dhillon.
Ph.D. Thesis, May 1997.
(Also appears as UCB Tech. Report No. UCB//CSD-97-971)
Bibtex: