Complexity of 'eigs'

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

Complexity of 'eigs'

Søren Hauberg
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
_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Complexity of 'eigs'

c.-2

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
_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

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

_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Complexity of 'eigs'

c.-2

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

> Thanks
> Søren
c.
_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Complexity of 'eigs'

Søren Hauberg

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

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?

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
_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Complexity of 'eigs'

c.-2

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.
_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Complexity of 'eigs'

Søren Hauberg

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
_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Complexity of 'eigs'

c.-2

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.
_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Complexity of 'eigs'

Søren Hauberg

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

_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave