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

  • $\begingroup$ Added reference-request and cs.cc tags $\endgroup$ Sep 14 '11 at 3:23

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.


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


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.