Аннотация
Bisection is one of the most common methods used to
compute the eigenvalues of symmetric tridiagonal
matrices. Bisection relies on the Sturm count: For a
given shift sigma, the number of negative pivots in
the factorization $T - I = LDL^T$ equals the
number of eigenvalues of T that are smaller than
sigma. In IEEE-754 arithmetic, the value $ınfty$
permits the computation to continue past a zero
pivot, producing a correct Sturm count when $T$ is
unreduced. Demmel and Li showed IEEE
Trans. Comput., 43 (1994), pp. 983–992 that using
$ınfty$ rather than testing for zero pivots
within the loop could significantly improve
performance on certain architectures. When
eigenvalues are to be computed to high relative
accuracy, it is often preferable to work with
$LDL^T$ factorizations instead of the original
tridiagonal $T$. One important example is the MRRR
algorithm. When bisection is applied to the factored
matrix, the Sturm count is computed from $LDL^T$
which makes differential stationary and progressive
qds algorithms the methods of choice. While it seems
trivial to replace $T$ by $LDL^T$, in reality these
algorithms are more complicated: In IEEE-754
arithmetic, a zero pivot produces an overflow
followed by an invalid exception (NaN, or "Not a
Number") that renders the Sturm count incorrect. We
present alternative, safe formulations that are
guaranteed to produce the correct
result. Benchmarking these algorithms on a variety
of platforms shows that the original formulation
without tests is always faster provided that no
exception occurs. The transforms see speed-ups of up
to 2.6x over the careful formulations. Tests
on industrial matrices show that encountering
exceptions in practice is rare. This leads to the
following design: First, compute the Sturm count by
the fast but unsafe algorithm. Then, if an exception
occurs, recompute the count by a safe, slower
alternative. The new Sturm count algorithms improve
the speed of bisection by up to 2x on our
test matrices. Furthermore, unlike the traditional
tiny-pivot substitution, proper use of IEEE-754
features provides a careful formulation that imposes
no input range restrictions.
Линки и ресурсы
тэги
сообщество