LAPACK Working Note 172: Benefits of IEEE-754 Features in Modern Symmetric Tridiagonal Eigensolvers
Osni A. Marques and E. Jason Riedy and Christof Voemel
EECS Department, University of California, Berkeley
Technical Report No. UCB/CSD-05-1414
, 2005
http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/CSD-05-1414.pdf
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 <i>T</i> - sigma I = LDL^T equals the number of eigenvalues of <i>T</i> that are smaller than sigma. In IEEE-754 arithmetic, the value infinity permits the computation to continue past a zero pivot, producing a correct Sturm count when <i>T</i> is unreduced. Demmel and Li showed in the 90s that using infinity rather than testing for zero pivots within the loop could improve performance significantly on certain architectures. <p> 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 <i>T</i>, see for example the MRRR algorithm. In these cases, the Sturm count has to be computed from LDL^T. The differential stationary and progressive qds algorithms are the methods of choice. <p> While it seems trivial to replace <i>T</i> 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), that renders the Sturm count incorrect. <p> We present alternative, safe formulations that are guaranteed to produce the correct result. <p> Benchmarking these algorithms on a variety of platforms shows that the original formulation without tests is always faster provided no exception occurs. The transforms see speed-ups of up to 2.6 times over the careful formulations. <p> 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 occurred, recompute the count by a safe, slower alternative. <p> The improved Sturm count algorithms improve the speed of bisection by up to 2 times 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.
BibTeX citation:
@techreport{Marques:CSD-05-1414, Author= {Marques, Osni A. and Riedy, E. Jason and Voemel, Christof}, Title= {LAPACK Working Note 172: Benefits of IEEE-754 Features in Modern Symmetric Tridiagonal Eigensolvers}, Year= {2005}, Month= {Sep}, Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/6514.html}, Number= {UCB/CSD-05-1414}, Abstract= {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 <i>T</i> - sigma I = LDL^T equals the number of eigenvalues of <i>T</i> that are smaller than sigma. In IEEE-754 arithmetic, the value infinity permits the computation to continue past a zero pivot, producing a correct Sturm count when <i>T</i> is unreduced. Demmel and Li showed in the 90s that using infinity rather than testing for zero pivots within the loop could improve performance significantly on certain architectures. <p> 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 <i>T</i>, see for example the MRRR algorithm. In these cases, the Sturm count has to be computed from LDL^T. The differential stationary and progressive qds algorithms are the methods of choice. <p> While it seems trivial to replace <i>T</i> 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), that renders the Sturm count incorrect. <p> We present alternative, safe formulations that are guaranteed to produce the correct result. <p> Benchmarking these algorithms on a variety of platforms shows that the original formulation without tests is always faster provided no exception occurs. The transforms see speed-ups of up to 2.6 times over the careful formulations. <p> 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 occurred, recompute the count by a safe, slower alternative. <p> The improved Sturm count algorithms improve the speed of bisection by up to 2 times 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.}, }
EndNote citation:
%0 Report %A Marques, Osni A. %A Riedy, E. Jason %A Voemel, Christof %T LAPACK Working Note 172: Benefits of IEEE-754 Features in Modern Symmetric Tridiagonal Eigensolvers %I EECS Department, University of California, Berkeley %D 2005 %@ UCB/CSD-05-1414 %U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2005/6514.html %F Marques:CSD-05-1414