Orthogonal Eigenvectors and Relative Gaps | Center for Big Data Analytics

Abstract: This paper presents and analyzes a new algorithm for computing eigenvectors of symmetric tridiagonal matrices factored as LDLt, 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 key is first running a qd-type algorithm on the factored matrix LDLt and then applying a fine-tuned version of inverse iteration especially adapted to this situation. Since the computational cost is O(n) per eigenvector for an n × n matrix, the proposed algorithm is the central step of a more ambitious algorithm which, at best (i.e., when all eigenvectors are well-conditioned), would compute all eigenvectors of an n × n symmetric tridiagonal at O(n2) cost, a great improvement over existing algorithms.

Download: pdf

Citation

Orthogonal Eigenvectors and Relative Gaps (pdf, software)
I. Dhillon, B. Parlett.
SIAM Journal of Matrix Analysis and Applications (SIMAX) , pp. 858-899, March 2004.

Bibtex:
@article{dhillon2004orthogonal, author = "Inderjit S. Dhillon AND Beresford N. Parlett", title = "Orthogonal Eigenvectors and Relative Gaps", journal = "SIAM Journal of Matrix Analysis and Applications (SIMAX)", page = "858–899", year = "2004", month = "mar", abstract = "This paper presents and analyzes a new algorithm for computing eigenvectors of symmetric tridiagonal matrices factored as LDLt, 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 key is first running a qd-type algorithm on the factored matrix LDLt and then applying a fine-tuned version of inverse iteration especially adapted to this situation. Since the computational cost is O(n) per eigenvector for an n × n matrix, the proposed algorithm is the central step of a more ambitious algorithm which, at best (i.e., when all eigenvectors are well-conditioned), would compute all eigenvectors of an n × n symmetric tridiagonal at O(n2) cost, a great improvement over existing algorithms." }