James W. Demmel and Inderjit Dhillon and Huan Ren

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-94-805

, 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(<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.

---

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},
    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