Re: Complexity of 'eigs'

[c.]

On 13 Aug 2012, at 10:11, Søren Hauberg wrote:

> Hi All
> 
> Does anybody know (or know a reference that answers my question) the 
> computational complexity of computing the largest eigenvalue of a real 
> symmetric matrix using 'eigs'?
> 
> Thanks
> Søren


eigs is based on arpack, which for hermitian matrices uses Implicitly Restarted 
Lanczos Method (IRLM) [1].
This is an iterative method so I'm not sure whether your question can have a 
simple and general answer, 
anyway you can find a discussion of the algorithm in this book [2] which is 
available online here [3], 
in particular in this chapter [4].

HTH,
c.


[1] http://www.caam.rice.edu/software/ARPACK/
[2] Z. Bai, J. Demmel, J. Dongarra, A. Ruhe and H. van der Vorst, editors, 
Templates for the solution of Algebraic Eigenvalue Problems: A Practical Guide 
. SIAM, Philadelphia, 2000
[3] http://web.eecs.utk.edu/~dongarra/etemplates/index.html
[4] http://web.eecs.utk.edu/~dongarra/etemplates/node117.html