Prev: fmincon function
Next: Results not repeatable for sum() function on fixed / deterministic vector
From: Martin on 5 Apr 2010 12:35
I need to find all the eigenvalues of a large sparse matrix that lie within a specified range.

The matrix size is in the range of 6000x6000, with approximately 60,000 nonzero elements. The number of eigenvalues to be found tends to be around 1000.

Using eigs to find a large number of eigenvalues is very slow, that is, the time per eigenvalue increases dramatically with the number of eigenvalues found. I have found that the time per eigenvalue is minimized when looking for approximately 20 eigenvalues at a time.

For now, my solution is to run a loop where 20 eigenvalues are found at a time, and check to make sure there is some overlap in the eigenvalues found in successive iterations. This ensures that no eigenvalues are missed, but also creates overhead.

This eigenvalue search is the slowest part of my algorithm, and I'm looking for ways to speed it up. Any suggestions?
From: Bruno Luong on 5 Apr 2010 13:11
"Martin " <mschubert(a)micron.com> wrote in message <hpd3fo$64h$1(a)fred.mathworks.com>...

You shouldn't trust 1000 eigenvalues provided by EIGS with any degree if certainty, wouldn't you? I wouldn't, not even for 100. The algorithm used by EIGS is well known to be numerically unstable (although thing would certainly get better with long 128 but floating point).

Otherwise just use a deflection trick, find smallest eigenvalues of

B := A - m*eye(size(A))

where m = (a+b)/2, with (a,b) is the interval range of interests (I haven't not see you describe it anywhere).

Bruno
From: Martin on 5 Apr 2010 14:20
Thanks for you response.

So if I find 20 eigenvalues at a time, I should be safe, right?

Also, the eigenvalues i am finding are the smallest of the matrix, and so the deflection trick may not be necessary.

"Bruno Luong" <b.luong(a)fogale.findmycountry> wrote in message <hpd5jd$8qf$1(a)fred.mathworks.com>...
> "Martin " <mschubert(a)micron.com> wrote in message <hpd3fo$64h$1(a)fred.mathworks.com>...
>
> You shouldn't trust 1000 eigenvalues provided by EIGS with any degree if certainty, wouldn't you? I wouldn't, not even for 100. The algorithm used by EIGS is well known to be numerically unstable (although thing would certainly get better with long 128 but floating point).
>
> Otherwise just use a deflection trick, find smallest eigenvalues of
>
> B := A - m*eye(size(A))
>
> where m = (a+b)/2, with (a,b) is the interval range of interests (I haven't not see you describe it anywhere).
>
> Bruno
 | 
Pages: 1
Prev: fmincon function
Next: Results not repeatable for sum() function on fixed / deterministic vector