6
$\begingroup$

What is the most efficient way to calculate the dominant eigenvector of a real symmetric tridiagonal matrix? What's the corresponding time complexity bound?

Could someone give me a reference for this special structure? Thank you in advance.

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

1 Answer 1

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .