8
$\begingroup$

Given a large matrix $A$ with eigenvalues $\sigma_1\ge \sigma_2 \ge \dotsc $, I want to determine only a subset of these values, say $\sigma_5,\sigma_8$ and $\sigma_{19}$. Is there an algorithm that can do this, or is finding the top 19 eigenvalues the best that can be done?

$\endgroup$
  • $\begingroup$ Do your matrix has any special properties? Do you roughly know the values for $\sigma_5$, $\sigma_8$ and $\sigma_{19}$? $\endgroup$ – nicoguaro Mar 20 at 5:40
  • $\begingroup$ Nope. But feel free to let me know if there are any results assuming any special properties. $\endgroup$ – dexter04 Mar 20 at 5:45
  • $\begingroup$ Related: stackoverflow.com/questions/12167654/… maybe you can determine the method behind the scenes there. $\endgroup$ – carlosvalderrama Mar 20 at 11:31
  • $\begingroup$ I would guess something in the direction Krylov subspace, Arnoldi or Lanczos iteration is required. $\endgroup$ – carlosvalderrama Mar 20 at 11:33
  • 2
    $\begingroup$ If your matrix is Hermitian there is guarantee that you have your ordered set of eigenvalues, since all of them are real. Also, if you know roughly the values you might try using the shift-invert method. At the end of the day, I think that it might be easier to find the first $n$ eigenvalues. $\endgroup$ – nicoguaro Mar 20 at 15:18
6
$\begingroup$

No, there is nothing, as far as I know, unless you know approximately the location of these eigenvalues. As for methods that can compute a subset of the spectrum of a matrix, I know only of methods that can produce:

  • eigenvalues from "the extremes of the spectrum", e.g., the ones with the largest absolute value, or with the most negative real/imaginary part. For instance Arnoldi / subspace iteration (suitably shifted).
  • eigenvalues closest to one given point in the complex plane, e.g., the smallest ones in modulus (closest to zero). For instance (rational) shift-and-invert Arnoldi or the inverse power iteration.
  • eigenvalues in a particular region of the plane, for instance $[-1,1] \times [-1,1]$. I think FEAST-type methods do this, but I know very little about them.

From what I understand, with FEAST-type methods you can also get a count of the number of eigenvalues in a specified region of the complex plane (via a contour integral), so in case you need a specified eigenvalue from the middle of the spectrum, for instance the 300th, you can run a sort of bisection search: assume (shifting and scaling) that the spectrum of your matrix is in $[-1,1]$ (and that is real, for simplicity). Compute the eigenvalues $\mu$ closest to $\frac12$. Compute the number of eigenvalues in $[\frac12,1]$. If it is larger than 300, look for the eigenvalue closest to the midpoint of $[\mu,1]$, otherwise for the eigenvalue closest to the midpoint of $[-1,\mu]$. Repeat.

I don't think any of this stuff would be competitive with vanilla LA Arnoldi if you replace 300 with 19, as in your example. And maybe not even with 300.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.