Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Added reference-request and cs.cc tags –  David Roberts Sep 14 '11 at 3:23

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.