7
$\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$
  • 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$ – amarney Oct 23 '17 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$ – amarney Oct 23 '17 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 '17 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$ – amarney Oct 24 '17 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$ – amarney Oct 24 '17 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.