19.num/JWD.dhillon.ren
.ls 2
.na
.LP
Parallel Accelerated Bisection on the CM-5

Inderjit Dhillon and Huan Ren 

(Professor J. W. Demmel)

(ARPA) DAAL03-91-C-0047 and
(NSF) ASC-90-05933 

Bisection is a classical method for finding eigenvalues of a symmetric
tridiagonal matrix. It is based on Sturm sequences, which can count the
number of eigenvalues in any interval. This permits us to refine
intervals containing eigenvalues until they are as narrow as we like. There is a great deal of parallelism available in this algorithm, and
in previous work we developed both statically and dynamically
load-balanced versions that attained near-linear speedup on our CM-5. Recent work has focused on the use of parallel-prefix to evaluate the
Sturm sequence even more rapidly. Recent work of R. Mathias has shown
that there can be a significant loss of accuracy in parallel-prefix in
certain rare cases, including the possibility of "nonmonotonicity,"
or intervals apparently containing a negative number of eigenvalues. Our work has focused on identifying these cases cheaply, recovering
cheaply, and maintaining correctness despite nonmonotonicity.