Welcome to MathOverflow

Question

4

1

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.

edited Mar 6 2011 at 6:59

asked Mar 6 2011 at 6:45

tom
41●2

It's been a while since I looked in Golub & van Loan's book, but have you tried that? – Yemon Choi Mar 6 2011 at 6:51

1

Lanczos algorithm (en.wikipedia.org/wiki/Lanczos_algorithm) is generally well-suited to obtain the dominant eigenvector. – Fabian Mar 6 2011 at 8:43

S. Sra · Answer 1 · 2011-03-06 10:33:57Z UTC

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.

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

Tridiagonal Matrix

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.