8
$\begingroup$

Iterative eigensolvers such as ARPACK, give the option to find a subset of the eigenvalues which have the largest imaginary part. My question is how do these algorithms work.

As I understand it, generally such algorithms use Krylov spaces and shift-invert methods which are very good at finding eigenvalues either at the extremes of the spectrum or around a given value. This is essentially because repeated applications of a matrix projects onto the eigenvector with largest magnitude eigenvalue. However, since the imaginary part of an eigenvalue need not have any correlation with its real part, I can't see how it's able to `ignore' the real part.

If anyone has any idea how these algorithms work, or alternatively know a way to search for eigenvalues which is ignorant of the real part of the eigenvalue I'd be very grateful.

Note that I previously asked this question on the maths stackexchange but didn't receive any answers:

https://math.stackexchange.com/questions/2437587/eigenvalue-with-largest-imaginary-part

$\endgroup$
6
  • 2
    $\begingroup$ I think one can simply shift the spectrum of $\textbf{A}$ upwards by applying the algorithm to $\textbf{B} = \textbf{A} + \mu i \textbf{I}$, where $\mu$ is a parameter which is sufficiently large, and has the same sign as the imaginary part of the eigenvalue you are looking for. The idea is that $\textbf{B}$ has the same eigenvectors as $\textbf{A}$, but by shifting the spectrum, we give more weight to the imaginary part when looking at the modulus of the eigenvalues. This seems very crude, and in many cases would cluster the eigenvalues closely together, giving a poor rate of convergence. $\endgroup$ Oct 23, 2017 at 19:08
  • 1
    $\begingroup$ Slight correction: one would want to shift the spectrum of $\textbf{A}$ not upwards, but in the direction of the sign of the imaginary part of the eigenvalue with largest imaginary part. This is why one must choose $\mu$ to have the same sign as the eigenvalue we are looking for. Once again, this is fairly crude, so I imagine ARPACK uses something more sophisticated. $\endgroup$ Oct 23, 2017 at 20:04
  • $\begingroup$ Thanks but this idea of shifting the imaginary part won't work in quite a few simple cases. For instance, consider two eigenvalues 10+0.5i and 1+1i. No matter what you add to the imaginary part, the first eigenvalue will always have the largest magnitude but this isn't the one we want. $\endgroup$
    – as2457
    Oct 24, 2017 at 7:08
  • 1
    $\begingroup$ I think it should always work, for instance, in MATLAB if I compute $sqrt(1^2 + (100 + 1)^2) > sqrt(10^2 + (100 + 0.5)^2)$ it returns true'. In chapter 3 of ARPACK Users' Guide, it does seem to use some sort of shift-and-invert when you specify to use 'LI' or 'SI'. $\endgroup$ Oct 24, 2017 at 13:04
  • 2
    $\begingroup$ If you are at a university, you might have access to the online user manual here: epubs.siam.org/doi/book/10.1137/1.9780898719628. Check out section 3.7, starting on page 33. $\endgroup$ Oct 24, 2017 at 20:00

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.