## How many iterations are required for the Lanczos algorithm to converge?

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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$)?

-

2
See my short note: mathoverflow.net/questions/75370/… – S. Sra Mar 8 2012 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. – unknown (yahoo) Mar 9 2012 at 1:20
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 5, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.884058952331543, "perplexity_flag": "middle"}