Accurate eigenvalues and exact zero Jordan blocks of totally nonnegative matrices (Q1728086)

The author presents an algorithm for a high relative accuracy computation of all eigenvalues of totally nonnegative (TN) matrices in $O(n^{3})$ time including an exact computation of the Jordan blocks corresponding to zero eigenvalues in up to $O(n^{4})$ time. \par Noteworthy is that many well-known ill conditioned matrices, such as Hilbert and Pascal matrices, belong to the class of TN matrices, and that classical eigenvalue solver generally fail to determine the tiny eigenvalues of ill conditioned matrices with high relative accuracy, caused by the well-known loss of leading significant digits during subtraction. The author explicitly refers to [\textit{E. Anderson} et al., LAPACK user's guide. This work is dedicated to Jim Wilkinson. 3rd ed. Philadelphia, PA: SIAM (1999; Zbl 0934.65030)]. \par The algorithm is based on the fact that a TN matrix can be decomposed in terms of nonnegative bidiagonal matrices using an elementary elimination transform. All eigenvalues and the size of the zero Jordan blocks are determined by the entries of the decomposition in high relative accuracy. \par A nonnegative bidiagonal matrix can be decomposed into a product of so-called elementary bidiagonal matrices (EBMs), that is, a TV matrix is a product of EBMs. ``The EBMs differ from the identity matrix in three entries only -- one offdiagonal and its two immediately adjacent diagonal neighbors''. Using the EBMs, the TN eigenvalue problem is reduced to a bidiagonal singular value problem. The corresponding algorithm has been already presented by the author in [SIAM J. Matrix Appl. 27, No. 1, 1--23 (2005; Zbl 1095.65031)] for nonsingular TN matrices. This result is extended to the singular case in this paper. By a generalization of the method for nonsingular matrices is shown, that the bidiagonal decomposition can be computed without subtractions (see subtractive cancellation) even when some of the factors are singular. \par The bidiagonal singular value problem is solved using the method of \textit{J. Demmel} and \textit{W. Kahan}[SIAM J. Sci. Stat. Comput. 11, No. 5, 873--912 (1990, Zbl 0705.65027)]. \par Additionally, the method for the computation of the rank of a TN matrix, required for the determination of the number of zero Jordan blocks, and the process for the determination of the zero Jordan structures are included in the main algorithm. \par The individual steps of the procedure are shown in detail. \par The theoretical ideas are verified by numerical experiments. The author concludes with the formulation of some open problems.