3
$\begingroup$

Anyone can help describe any known specialized algorithm that finds (or quite accurately approximates) the largest eigenvalue and its eigenvectors of a symmetric tri-diagonal matrix in the form $\left( {\begin{array}{*{20}{c}} {{x_1}}&{{y_1}}&{}&{} \\ {{y_1}}&{{x_2}}& \ddots &{} \\ {}& \ddots & \ddots &{{y_{n - 1}}} \\ {}&{}&{{y_{n - 1}}}&{{x_n}} \end{array}} \right)$, where $y_1,...,y_{n-1}$ are positive numers? Is there any known best algorithm? "Specialized" means the algorithm is desired to use special properties of symmetric tridiagoal matrices run faster for them than classic method like QR Method or Rayleigh quotient iteration for general (symmetric) matrices. Many thanks!

$\endgroup$
  • $\begingroup$ What do you know about the power iteration algorithm and how do you evaluate it? $\endgroup$ – Lutz Lehmann Jul 31 '17 at 4:54
  • $\begingroup$ The "QR method" is a common approach here. $\endgroup$ – Omnomnomnom Jul 31 '17 at 11:41
  • $\begingroup$ Thanks for comment. I know some about both. The algorithm is desired to use properties of tridiagonal matrices so it can run faster than methods for general symmetric matrices. $\endgroup$ – Ralph B. Jul 31 '17 at 12:02
  • $\begingroup$ Try to find some articles on internet, there are many since 90th - $O(n^2)$ with parallelism should be good enough. $\endgroup$ – z100 Jul 31 '17 at 15:03
1
$\begingroup$

To the best of my knowledge, there is no method which can take advantage of the fact that the off diagonal elements have the same sign.

The inverse subspace iteration with Rayleigh-Ritz acceleration can be applied to compute the dominant eigenpairs. You will need the following kernels:

  1. Symmetric tridiagonal linear solver.
  2. Eigendecomposition of small dense symmetric matrix.
  3. Tall and skinny QR factorization

You can find sequential routines for all these operations in LAPACK. Good parallel routines is a question for another day.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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