Laub, A. J.; Xia, J. Fast condition estimation for a class of structured eigenvalue problems. (English) Zbl 1223.65026 SIAM J. Matrix Anal. Appl. 30, No. 4, 1658-1676 (2009). Summary: We present a fast condition estimation algorithm for the eigenvalues of a class of structured matrices. These matrices are low rank modifications to Hermitian, skew-Hermitian, and unitary matrices. Fast structured operations for these matrices are presented, including Schur decomposition, eigenvalue block swapping, matrix equation solving, compact structure reconstruction, etc. Compact semiseparable representations of matrices are used in these operations. We use these operations in a new, improved version of the statistical condition estimation method for eigenvalue problems. The estimation algorithm costs \(\text{O}(n^2)\) flops for all eigenvalues, instead of \(\text{O}(n^3)\) as in traditional algorithms, where \(n\) is the order of the matrix. The algorithm provides reliable condition estimates for both eigenvalues and eigenvalue clusters. The proposed structured matrix operations are also useful for additional eigenvalue problems and other applications. Numerical examples are used to illustrate the reliability and efficiency of the algorithm. Cited in 6 Documents MSC: 65F15 Numerical computation of eigenvalues and eigenvectors of matrices 65F35 Numerical computation of matrix norms, conditioning, scaling 15A12 Conditioning of matrices Keywords:statistical condition estimation; low rank modification; sequentially semiseparable structure; structured Schur decomposition; diagonal block swapping; structured Sylvester equation; eigenvalues; Hermitian; skew-Hermitian; unitary; algorithm; numerical examples Software:MultRoot; HQR3 PDFBibTeX XMLCite \textit{A. J. Laub} and \textit{J. Xia}, SIAM J. Matrix Anal. Appl. 30, No. 4, 1658--1676 (2009; Zbl 1223.65026) Full Text: DOI Link