Computation of exact inertia and inclusions of eigenvalues (singular values) of tridiagonal (bidiagonal) matrices (Q869919)

The careful by the microprocessor industry followed Standard for floating point arithmetic was developed under the auspices of the Institute for Electrical and Electronic Engineers in the late 1970s and early 1980s as IEEE p754, published in 1985 as ANSI IEEE Std 754-1985, and led by William Kahan of the University of Berkeley. The author of the present paper improves an algorithm which has been developed by \textit{W. Kahan} [Accurate Eigenvalues of a symmetric tridiagonal matrix. Technical Report CS 41, Computer Science Department, Stanford University (1966)] during his interplay at the time between linear algebra and binary floating point arithmetic. Using the features of the Standard the inertia, i.e., the integer triplet, consisting of the number of positive, negative and zero eigenvalues, are computed for a real symmetric shifted tridiagonal matrix in unprecedented accuracy. The computation of exact inertia is the basic step in bisection and multisection algorithms for real symmetric tridiagonal matrices giving guaranted intervals for the eigenvalues. Using the Golub-Kahan form also exact intervals for singular values of bidiagonal matrices can be determined. In contrast to existing theorems based on traditional error analysis the author uses only arithmetic axioms given already in the report by Kahan refered above and outlined in this paper providing monotone arithmetic. The floating point computation of the diagonal matrix \(D\) of the LDL\(^T\) factorization of the tridiagonal matrix is done by a special shift strategy using so-called dead shifts. The accuracy of the algorithms is demonstrated by standard matrix examples for eigenvalue and singular value computations using three sets of computer architectures (32-bit and 64-bit processors, several rounding modes) in double precision and double extended precision arithmetic. It is assumed that the variables of the original matrices are exactly machine representable.