7
$\begingroup$

Hi, all

I am working on an algorithm which uses Lanczos method to compute K smallest eigenvalue(and their eigenvectos) of a sparse matrix, just want some information or links about the complexity of Lanczos method.

Thank you

Improve this question
$\endgroup$
1
  • $\begingroup$ Added reference-request and cs.cc tags $\endgroup$
    – David Roberts ♦
    Commented Sep 14, 2011 at 3:23

2 Answers 2

Reset to default
8
$\begingroup$

Complexity analysis of Lanczos seems to be hard to find in the literature. Here are two leads, that might help a bit.

For the largest eigenvalue, you might find the complexity analysis in the following paper to be useful.

Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start by J. Kuczyński and H. Woźniakowski

A very important point raised in the above paper is that even if an eigenvalue is easily estimable, its corresponding eigenvector can be computationally hard to estimate!

Also see Lemma 2 of Fast algorithms for approximate semidefinite programming ... by S. Arora, E. Hazan, and S. Kale, for additional results.

Improve this answer
$\endgroup$
2
$\begingroup$

Chapter 9 = Lanczos Methods, of "matrix computations", Golub, van Loan, John Hopkins univ press.

Improve this answer
$\endgroup$

You must log in to answer this question.

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