On the correctness of some bisection-like parallel eigenvalue algorithms in floating point arithmetic
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.
- scientific article; zbMATH DE number 1330402
- scientific article; zbMATH DE number 1419237
- Computation of exact inertia and inclusions of eigenvalues (singular values) of tridiagonal (bidiagonal) matrices
- Benefits of IEEE‐754 Features in Modern Symmetric Tridiagonal Eigensolvers
- Parallel implementation of bisection for the calculation of eigenvalues of tridiagonal symmetric matrices
- ScaLAPACK: A portable linear algebra library for distributed memory computers -- design issues and performance
- Mixed precision bisection
- The geometric mean algorithm
- Benefits of IEEE‐754 Features in Modern Symmetric Tridiagonal Eigensolvers
- The singular value decomposition: anatomy of optimizing an algorithm for extreme scale
- scientific article; zbMATH DE number 1419237 (Why is no real title available?)
- Restructuring the tridiagonal and bidiagonal QR algorithms for performance
- Computation of exact inertia and inclusions of eigenvalues (singular values) of tridiagonal (bidiagonal) matrices
This page was built for publication: On the correctness of some bisection-like parallel eigenvalue algorithms in floating point arithmetic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1920177)
