

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
_______________________________________________
Helpoctave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/helpoctave


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_______________________________________________
Helpoctave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/helpoctave


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_______________________________________________
Helpoctave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/helpoctave


On Aug 13, 2012, at 12:06 PM, c. wrote:
>
> On 13 Aug 2012, at 12:01, Søren Hauberg wrote:
>
>> 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.
>
> If your matrix is dense I am not sure using "eigs" rather than "eig" is convenient, the deirect algorithm in "eig" should be O(D^2):
> http://web.eecs.utk.edu/~dongarra/etemplates/node93.html#sec:denseThe way I read the text at this link, 'eig' is O(D^3), but perhaps I'm missing something. I understand this as, first the matrix is put into tridiagonal form, which is O(D^3), and then another method (i.e. QR) is applied to get the eigenvectors, which takes O(D^2). Am I misunderstanding something?
Practially, I actually find 'eigs' to be faster than 'eig' if I only care about the first eigenvector; if I want them all, then 'eig' is better.
Søren
_______________________________________________
Helpoctave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/helpoctave


On 13 Aug 2012, at 12:13, Søren Hauberg wrote:
> The way I read the text at this link, 'eig' is O(D^3), but perhaps I'm missing something. I understand this as, first the matrix is put into tridiagonal form, which is O(D^3), and then another method (i.e. QR) is applied to get the eigenvectors, which takes O(D^2). Am I misunderstanding something?
No, you're right mine was just a typo.
> Practially, I actually find 'eigs' to be faster than 'eig' if I only care about the first eigenvector; if I want them all, then 'eig' is better.
I would not expect the advantage of "eigs" over "eig" to be very important if your matrix is dense and you do not need to compute the eigenvectors.
But maybe I am missing some implementation detail.
> Søren
c.
_______________________________________________
Helpoctave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/helpoctave


On Aug 13, 2012, at 12:25 PM, c. wrote:
>
> On 13 Aug 2012, at 12:13, Søren Hauberg wrote:
>
>> The way I read the text at this link, 'eig' is O(D^3), but perhaps I'm missing something. I understand this as, first the matrix is put into tridiagonal form, which is O(D^3), and then another method (i.e. QR) is applied to get the eigenvectors, which takes O(D^2). Am I misunderstanding something?
>
> No, you're right mine was just a typo.
Ok.
>> Practially, I actually find 'eigs' to be faster than 'eig' if I only care about the first eigenvector; if I want them all, then 'eig' is better.
>
> I would not expect the advantage of "eigs" over "eig" to be very important if your matrix is dense and you do not need to compute the eigenvectors.
> But maybe I am missing some implementation detail.
I need the actual eigenvectors (not just the eigenvalues). Does that make a difference?
Søren
_______________________________________________
Helpoctave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/helpoctave


On 13 Aug 2012, at 12:26, Søren Hauberg wrote:
> I need the actual eigenvectors (not just the eigenvalues). Does that make a difference?
If I am not mistaken, from the same reference I cited before it seems that if only eigenvalues are required you could get it about 77% faster with the QR algorithm.
c.
_______________________________________________
Helpoctave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/helpoctave


On Aug 13, 2012, at 12:39 PM, c. wrote:
>
> On 13 Aug 2012, at 12:26, Søren Hauberg wrote:
>
>> I need the actual eigenvectors (not just the eigenvalues). Does that make a difference?
>
> If I am not mistaken, from the same reference I cited before it seems that if only eigenvalues are required you could get it about 77% faster with the QR algorithm.
Okay, thanks
Søren
_______________________________________________
Helpoctave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/helpoctave

