19.num/JWD.WK.li2
.ls 2
.na
.LP
Solving Secular Equations for the Symmetric Tridiagonal Eigenproblem

Ren Cang Li 

(Professors W. Kahan and J. W. Demmel)

(ARPA) DM28E04120

The divide-and-conquer algorithm for the symmetric tridiagonal
eigenproblem is one of the two fastest algorithms for the problem. It
was introduced by Cuppen in 1981. Despite numerous attempts, no
numerically reliable implementation has been constructed until now. One
difficulty has been in solving the so-called secular equation with
sufficient accuracy to stably merge the solutions of the subproblems
produced by the divide-and-conquer paradigm. We construct effective
ways to solve secular equations by interpolating the secular functions
rationally. This eliminates instabilities in the previous best
algorithm by Sorensen and Tang. Our algorithm gives a significant
speedup over the traditional QR iteration for sufficiently large
matrices. This work is part of the LAPACK project, which is producing
high-performance numerical linear algebra software for high-performance
machines. A parallel implementation of this algorithm is being
constructed by J. Rutter (see elsewhere in this chapter).