Accurate eigenvalues and exact zero Jordan blocks of totally nonnegative matrices
type: Item
instance of: scholarly article
title: Accurate eigenvalues and exact zero Jordan blocks of totally nonnegative matrices
zbMATH Open document ID: 1434.65035
author: Plamen Koev
published in: Numerische Mathematik
publication date: 2019-02-21T00:00:00Z
review text: 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 met…
reviewed by: Georg Hebermehl
Mathematics Subject Classification ID: 65F15
Mathematics Subject Classification ID: 65F22
Mathematics Subject Classification ID: 65F35
Mathematics Subject Classification ID: 65Y04
Mathematics Subject Classification ID: 15A18
Mathematics Subject Classification ID: 15A20
zbMATH DE Number: 7027401
zbMATH Keywords: totally nonnegative matrices
zbMATH Keywords: eigenvalues
zbMATH Keywords: floating point arithmetics
zbMATH Keywords: machine precision
zbMATH Keywords: exact zero Jordan blocks
zbMATH Keywords: ill-conditioned matrices
zbMATH Keywords: Hilbert matrix
zbMATH Keywords: Pascal matrix
zbMATH Keywords: subtractive cancellation
zbMATH Keywords: nonnegative bidiagonal decomposition
zbMATH Keywords: singular value problem
describes a project that uses: Matlab
describes a project that uses: LAPACK
describes a project that uses: TNTool
MaRDI profile type: Publication
full work available at URL: s00211-019-01022-0
OpenAlex ID: W2910998582
cites work: LAPACK Users' Guide
cites work: Totally positive matrices
cites work: Some properties of totally positive matrices
cites work: Accurate Singular Value Decompositions of Structured Matrices
cites work: Accurate Singular Values of Bidiagonal Matrices
cites work: Bidiagonal Factorizations of Totally Nonnegative Matrices
cites work: Jordan Structures of Totally Nonnegative Matrices
cites work: Q3002117
cites work: Total positivity and Neville elimination
cites work: Q5624248
cites work: Accurate Eigenvalues and SVDs of Totally Nonnegative Matrices
cites work: Accurate Computations with Totally Nonnegative Matrices
cites work: A reduction theorem for totally positive matrices
Wikidata QID: Q128625275
DOI: 10.1007/S00211-019-01022-0
Recommended article: Accurate Eigenvalues and SVDs of Totally Nonnegative Matrices
Recommended article: Accurate Computations with Totally Nonnegative Matrices
Recommended article: Accurate eigenvalues of certain sign regular matrices
Recommended article: Accurate eigenvalues of some generalized sign regular matrices via relatively robust representations
Recommended article: Q6141648
Recommended article: An eigenvalue inequality for positive semidefinite k × k block matrices
Recommended article: Q3353185
Recommended article: Similarity to totally positive matrices and accurate computations
Recommended article: A finite-step construction of totally nonnegative matrices with specified eigenvalues
Recommended article: Improving formulas for the eigenvalues of finite block-Toeplitz tridiagonal matrices
description: scientific article; zbMATH DE number 7027401