Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
Lanczos algorithm (en.wikipedia.org/wiki/Lanczos_algorithm) is generally well-suited to obtain the dominant eigenvector. –  Fabian Mar 6 '11 at 8:43

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.