# Tridiagonal Matrix

What is the most efficient way to calucate the dominant eigenvector of a real symmetric tridiagonal matrix, and what's the corresponding time complexity bound? Could someone give me a reference for this special structure? Thank you in advance.

-
It's been a while since I looked in Golub & van Loan's book, but have you tried that? –  Yemon Choi Mar 6 '11 at 6:51
Lanczos algorithm (en.wikipedia.org/wiki/Lanczos_algorithm) is generally well-suited to obtain the dominant eigenvector. –  Fabian Mar 6 '11 at 8:43

The following paper proposes an $O(nk)$ algorithm called $MR^3$ (Multiple Relatively Robust Representations) to compute $k$ orthogonal eigenvectors of an $n \times n$ symmetric tridiagonal matrix. An implementation of this method is also available in LAPACK.

1. I. S. Dhillon and B. N. Parlett. Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices. (LAA 387, 2004).

(The paper also includes details of an algorithm called "GetVec" for computing an eigenvector corresponding to an isolated eigenvalue).

Additionally, searching for the MRRR algorithm will turn up other relevant results for you

-