# On the Correctness of Parallel Bisection in Floating Point

### James W. Demmel, Inderjit Dhillon and Huan Ren

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-94-805

March 1994

### http://www.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://www.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://www.eecs.berkeley.edu/Pubs/TechRpts/1994/5599.html %F Demmel:CSD-94-805