Re: Complexity of 'eigs'

[Søren Hauberg]

On Aug 13, 2012, at 10:44 AM, c. wrote:

> 
> 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].

Thanks, that helped quite a bit, actually. I am fine with having the complexity 
of each iteration, which I understood to be O(D^3) if the matrix is dense DxD.

Thanks
Søren

> 
> 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