James W. Demmel, Inderjit Dhillon and Huan Ren

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-94-805
March 1994

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/CSD-94-805.pdf

Bisection is an easily parallelizable method for finding the eigenvalues of real symmetric tridiagonal matrices, or more generally symmetric acyclic matrices. It requires a function Count( x) which counts the number of eigenvalues less than x. In exact arithmetic Count( x) is an increasing function of x, but this is not necessarily the case with roundoff. Our first result is that as long as the floating point arithmetic is monotonic, the computed function Count( x) implemented appropriately will also be monotonic; this extends an unpublished 1966 result of Kahan to the larger class of symmetric acyclic matrices. Second, we analyze the impact of nonmonotonicity of Count( x) on the serial and parallel implementations of bisection. We present simple and natural implementations which can fail because of nonmonotonicity; this includes the routine bisect in EISPACK. We also show how to implement bisection correctly despite nonmonotonicity; this is important because the fastest known parallel implementation of Count( x) is nonmonotonic even if the floating point is not.

BibTeX citation:

@techreport{Demmel:CSD-94-805,
    Author = {Demmel, James W. and Dhillon, Inderjit and Ren, Huan},
    Title = {On the Correctness of Parallel Bisection in Floating Point},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1994},
    Month = {Mar},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/5599.html},
    Number = {UCB/CSD-94-805},
    Abstract = {Bisection is an easily parallelizable method for finding the eigenvalues of real symmetric tridiagonal matrices, or more generally symmetric acyclic matrices. It requires a function Count(<i>x</i>) which counts the number of eigenvalues less than <i>x</i>. In exact arithmetic Count(<i>x</i>) is an increasing function of <i>x</i>, but this is not necessarily the case with roundoff. Our first result is that as long as the floating point arithmetic is monotonic, the computed function Count(<i>x</i>) implemented appropriately will also be monotonic; this extends an unpublished 1966 result of Kahan to the larger class of symmetric acyclic matrices. Second, we analyze the impact of nonmonotonicity of Count(<i>x</i>) on the serial and parallel implementations of bisection. We present simple and natural implementations which can fail because of nonmonotonicity; this includes the routine bisect in EISPACK. We also show how to implement bisection correctly despite nonmonotonicity; this is important because the fastest known parallel implementation of Count(<i>x</i>) is nonmonotonic even if the floating point is not.}
}

EndNote citation:

%0 Report
%A Demmel, James W.
%A Dhillon, Inderjit
%A Ren, Huan
%T On the Correctness of Parallel Bisection in Floating Point
%I EECS Department, University of California, Berkeley
%D 1994
%@ UCB/CSD-94-805
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/5599.html
%F Demmel:CSD-94-805