Orthogonal Eigenvectors and Relative Gaps

From MaRDI portal





The authors present and analyze a new method, Algorithm Getvec, for computing eigenvectors of symmetric tridiagonal matrices factored as \(LDL^T\), with \(D\) diagonal and \(L\) unit bidiagonal. If an eigenpair is well behaved in a certain sense with respect to the factorization, the algorithm is shown to compute an approximate eigenvector which is accurate to working precision. As a consequence, all the eigenvectors computed by the algorithm come out numerically orthogonal to each other without making use of any reorthogonalization process. The properties that must be satisfied in order for Algorithm Getvec to compute an accurate approximation to eigenvector \(v\) (corresponding to eigenvalue \(\lambda\) of \(LDL^T\)) are that (i) both \(\lambda\) and \(v\) must be determined to high relative accuracy by the parameters in \(L\) and \(D\) and (ii) the relative gap between \(\lambda\) and its nearest neighbor \(\mu\) in the spectrum should exceed tol; \(| \lambda - \mu | > tol | \lambda | \). The key is first applying a \(qd\)-type algorithm to the factored matrix \(LDL^T\) and then a fine-tuned version of inverse iteration especially adapted to this situation. Since the computational cost is \(O(n)\) per eigenvector for an \(n \times n\) matrix, the proposed algorithm is the central step of a more ambitious algorithm which, at best (that is, when all eigenvectors are well-conditioned), would compute all eigenvectors of an \(n \times n\) symmetric tridiagonal at \(O(n^2)\) cost, a great improvement over existing algorithms. The authors compare Algorithm Getvec with others algorithms for different examples at the end of the paper.




Cited in
(38)








This page was built for publication: Orthogonal Eigenvectors and Relative Gaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4650963)