×

Fast condition estimation for a class of structured eigenvalue problems. (English) Zbl 1223.65026

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.

MSC:

65F15 Numerical computation of eigenvalues and eigenvectors of matrices
65F35 Numerical computation of matrix norms, conditioning, scaling
15A12 Conditioning of matrices

Software:

MultRoot; HQR3
PDFBibTeX XMLCite
Full Text: DOI Link