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
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
3
|
|
|||
|
|
2
|
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. |
||
|
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
0
|
Chapter 9 = Lanczos Methods, of "matrix computations", Golub, van Loan, John Hopkins univ press. |
||
|
|
