Abstract: Bisection is a parallelizable method for nding the eigenvalues of real symmetric
tridiagonal matrices, or more generally symmetric acyclic matrices.
Ideally, one would like an implementation that was simultaneously parallel, load balanced, devoid
of communication, capable of running on networks of heterogenous workstations, and of course
correct. But this is surprisingly dicult to achieve.
The reason is that bisection requires a function Count(x) which counts the number of eigenvalues
less than x. In exact arithmetic Count(x) is a monotonic increasing function of x, and the
logic of the algorithm depends on this. However, monotonicity can fail, and incorrect eigenvalues
may be computed, because of roundo or as a result of using networks of heterogeneous parallel processors.
We illustrate this problem, which even arises in some serial algorithms like the EISPACK
routine bisect, and show several ways to x it. One of these ways has been incorporated into the
ScaLAPACK library.
Download: pdf
Citation
- On the Correctness of Some Bisection-like Parallel Algorithms in Floating Point Arithmetic (pdf, software)
J. Demmel, I. Dhillon, H. Ren.
Electronic Transactions of Numerical Analysis (ETNA), December 1995.
Bibtex: