Efficient computation of largest eigenvalue

General Usage
,
1

For some numerical simulations I run, I need to construct a matrix and obtain its leading eigenvalue. I will make use of both of them.

I was using the LinearAlgebra package, and computing the leading eigenvalue as maximum(real(eigvals(matrix))). When profiling the code, I noticed that this computation takes a noticeable amount of time, especially for larger matrices, so I am trying to speed it up.

I cannot use eigvals! because I need the matrix later and do not want to override it. Furthermore, I only need one eigenvalue. I found that Arpack.jl can compute the leading eigenvalue directly. It is way faster, but it fails to diagonalize some matrices, with the error

┌ Error: XYAUPD_Exception: Maximum number of iterations taken. All possible eigenvalues of OP has been found.
│ IPARAM(5) returns the number of wanted converged Ritz values.

Looking at the package issues, it seems that version 0.5.4 of the package is broken and leads to this problem. Other users have reported this problem, see 1, 2. Might be that some matrices actually cannot be solved by this method (the ones I am using are dense and large), but the error is not clear about it and the package does not seem to be maintained anymore. Other alternatives such as KrylovKit.jl or Arnoldi.jl also do not have any recent commit, nor answer to open issues, so they all seem to be unmaintained.

So I wonder what the supported, most efficient way of computing just a single eigenvalue is, and if there’s any plan to re-take Arpack.jl package again. The speed difference is noticeable, especially for large matrices.

Thank you for your help!

2

https://jutho.github.io/KrylovKit.jl/latest/man/eig/#KrylovKit.eigsolve

what didn’t work for you?

2 Likes
3

Power method ?
`https://services.math.duke.edu/~jtwong/math361-2019/lectures/Lec10eigenvalues.pdf

1 Like
4

You can try to pass a sigma to Arpack and that should work

5

Regarding KrylovKit.jl, it seems to work for my case (a bit more of testing is needed but seems stable). The problem is that the package does not seem to be maintained, but I might be mistaken (is it?). I would like to rely on packages that will have some continuity.

About the use of sigma in Arpack.jl, @rveltz , as far as I understand I need an initial guess of the eigenvalues beforehand, which I might not have. Also, does this mean that the XYAUPD error is the expected behaviour of the package?

6

not updated doesn’t mean not maintained, maybe it’s just mature? The author is still active

7

Definitely, I was lurking around the issues and gave me some abandonware impression, but it seems I was wrong. Then KrylovKit seems to get the job done efficiently (speed is comparable to Arpack). Thanks!!

8

FWIW : I don’t know how efficiently KrylovKit.jl and Arpack.jl deal with the specialized largest eigenvalue case, but I used to work on a large project where the (accelerated inverse) power method was the fastest approach.

It may be interesting to check what gives non accelerated PM using:

https://docs.juliahub.com/IterativeSolvers/ef2NV/0.8.5/eigenproblems/power_method/

9

I have tried, but the amount of iterations I need for the power method to converge to the correct result makes it way slower than the other available options. Even the function from LinearAlgebra package gives me better results when I run it with @benchmark.

1 Like
10

You might have an idea by now. You can then update it when you change the problem a little based on a previous computation