19.num/JWD.rutter.e
.ls 2
.na
.LP
.EQ
delim $$
gfont Roman
.EN
A Divide-and-Conquer Algorithm for the Symmetric Tridiagonal Eigenproblem

Jeff Rutter 

(Prof. J. W. Demmel)

(NSF) ASC-90-05933

One of the two fastest serial algorithms for the symmetric tridiagonal
eigenproblem is the divide-and-conquer algorithm. It was initially 
developed by Cuppen in 1981, but only recently stabilized in a portable 
way by Ren Cang Li (in this chapter) and Ming Gu. The initial implementation 
of this algorithm computed all the eigenvalues and eigenvectors, and 
was rather inefficient for computing eigenvalues only, using O($n sup 3$) 
flops instead of the O($n sup 2$) used by bisection. We are producing a 
version that does O($n sup 2$) flops to compute the eigenvalues only, 
and promises to be more efficient than the competition (bisection 
plus inverse iteration) for eigenvectors as well.