MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am trying to find the n smallest eigenvalues and eigenvectors of a NxN SPD matrix using Lanczos method. What is the number of iterations usually required? I mean, does it scale as $O(N)$ or $O(\sqrt{N})$ assuming n << N (n is usually <=10 and N ~ $10^6$ or $10^7$)?

share|cite|improve this question
See my short note:… – Suvrit Mar 8 '12 at 0:52
Thanks Suvrit. From "Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start by J. Kuczyński and H. Woźniakowski", it looks like for a fixed error, the number of iterations for the Lanczos method scales as $O(ln(N))$ for finding the eigenvalues. Is there a difference if I need to calculate the eigenvectors too? I assume the complexity is not different, but would like to know if that is not so. – user21969 Mar 9 '12 at 1:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.