# the complexity of Lanczos method

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

-
Added reference-request and cs.cc tags –  David Roberts 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.

-