On the correctness of some bisection-like parallel eigenvalue algorithms in floating point arithmetic (Q1920177)

The authors consider variants of the well-known bisection method to enclose eigenvalues of real symmetric tridiagonal matrices and of real symmetric acyclic matrices. Most of the algorithms are tailored for parallel computers including networks of heterogeneous parallel processors. They are discussed in view of floating point arithmetic. Section 1 introduces into the material, Section 2 describes acyclic matrices via acyclic graphs and defines a monotonic implementation of floating point arithmetic. In addition it makes various assumptions on the floating point arithmetic, on the input matrix, on the way to split an interval and on the machine based evaluation \(FloatCount(x)\) of the underlying function \(Count\) which counts the numbers of eigenvalues that are less than some given real number \(x\). Section 3 outlines all the results of the paper in four tables. Section 4 investigates the correctness of bracketing algorithms and exhibits some existing ``natural'' implementations of bracketing algorithms which are incorrect. Here, a bracketing algorithm is any algorithm with the following properties: 1. It divides an interval with at least one eigenvalue into smaller subintervals of any size. 2. It recomputes the numbers of eigenvalues in the subintervals. 3. It terminates when the intervals are narrow enough. A bracketing algorithm is named correct if it has the subsequent properties: 1. It terminates. 2. It computes every desired eigenvalue exactly once. 3. The computed eigenvalues are correct to within the user specified error tolerance. 4. The computed eigenvalues are in sorted order. Otherwise the algorithm is called incorrect. Section 5 is devoted to a roundoff error analysis for the computed eigenvalues involving over/ underflow and division by zero. Among others EISPACK's bisect routine, LAPACK's dstebz routine and the authors' routine FlCnt\_IEEE are discussed. In Section 6 the monotonicity of the function \(FloatCount\) is proved for symmetric acyclic matrices provided that the floating point arithmetic is monotonic. Section 7 contains the proofs of various theorems stated in Section 4, Section 8 discusses some practical implementation issues concerning the SignBit-function, the division by zero and the over/underflow. Section 9 ends with some conclusions.