5
$\begingroup$

I am trying to find the first three lowest eigenvalues of large sparse matrices of size range $10^3 - 10^5$. The matrices depend on some parameter $x$, so I first construct the matrices and then use Eigenvalues[Mat(x), 3]. Mathematica however orders the eigenvalues by absolute value so there is no guarantee in finding the lowest eigenvalue by the method above. See figure below

enter image description here

I can find all the eigenvalues, order them, and then find the minimum using the instructions found here but that defeats the point of using sparse matrices or Mathematica altogether. Moreover, the code slows down even more when cycling through all values of $x$. So, can this problem be done in Mathematica?

$\endgroup$
  • 2
    $\begingroup$ Why not use Eigenvalues[Mat[x], -3]? $\endgroup$ – Carl Woll Jun 10 at 17:58
  • $\begingroup$ It is not clear what you want. Show on a simple example on a matrix m[x] of low dimension. $\endgroup$ – Alex Trounev Jun 10 at 18:05
  • $\begingroup$ Duplicate of mathematica.stackexchange.com/q/194807 ? $\endgroup$ – Roman Jun 10 at 18:11
  • 1
    $\begingroup$ The title is a little misleading. If you asked me for the "lowest magnitude" eigenvalues, I would assume that you wanted the ones closest to zero. Maybe "largest-magnitude negative eigenvalues" would be more accurate? $\endgroup$ – Michael Seifert Jun 12 at 12:48
1
$\begingroup$

To calculate the lowest eigenvalues using Mathematica, I always introduce a "shift" in the following way:

mat1 = mat - IdentityMatrix[Length[mat]]*large

and then add large to the result of Eigenvalues[mat1]. This operation leaves the eigenvectors unchanged and I do not need to use Arnoldi specifically. Of course, Arnoldi does a similar shift inside, however I am not sure if that is used correctly in the Mathematica implementation.

Example:

mat={{1.,2.},{3.,4.}};

The eigenvalues are in the order given by Eigenvalues

{5.37228, -0.372281}.

The procedure above produces for any large enough large:

{-0.372281, 5.37228}

with the smallest first. Or Eigenvalues[mat1,1]+large just the lowest eigenvalue.

$\endgroup$
  • $\begingroup$ It worked! I also realize original question was needlessly ambiguous. I get the general idea of the shift but is there a way to systematically guess a value for large? Or alternatively, 'large' compared to what (|large| > 1)? Thanks. $\endgroup$ – WikawTirso Jun 12 at 13:16
  • $\begingroup$ Well, the idea is to introduce a shift that all eigenvalues of the "shifted" matrix are negative. So you could calculate the largest eigenvalue of the shifted matrix, and if is negative, your shift is fine. if not, shift more. $\endgroup$ – Michael Weyrauch Jun 12 at 14:16
8
$\begingroup$

Use the Arnoldi method with shift-inversion:

Eigenvalues[A, 3, Method -> {"Arnoldi", "Criteria" -> "Magnitude", "Shift" -> 0}]

gives you the three smallest eigenvalues by absolute value (by magnitude). See here: Efficiently find all values of parameter such that any of the eigenvalues of a matrix is equal to 1

After comments by @HenrikSchumacher it appears that the same can be achieved with

Eigenvalues[A, -3, Method -> {"Arnoldi", "Criteria" -> "Magnitude"}]

and there is no need for explicit shift-inversion.

And as @CarlWoll points out, this method is the default method for sparse matrices, so even

Eigenvalues[A, -3]

achieves the same effect. For non-sparse matrices, however, specifying the method can give a large speedup.

update

It now looks like you want the eigenvalues with smallest real part, not those with smallest magnitude. This you can also achieve with the Arnoldi method:

Eigenvalues[M, 3, Method -> {"Arnoldi", "Criteria" -> "RealPart"}]

gives the three eigenvalues with largest real part. To get the smallest ones, do

-Eigenvalues[-M, 3, Method -> {"Arnoldi", "Criteria" -> "RealPart"}]

The trick is that M and -M have the same eigenvalues (up to sign) and eigenvectors.

Of course this trick also works with the other methods presented above.

$\endgroup$
  • $\begingroup$ Reading this, I realized once more that Mathematica's implementation of Arnoldi's method is really inconsistent: Both Eigenvalues[A, 1, Method -> {"Arnoldi", "Criteria" -> "Magnitude", "Shift" -> 0}] and Eigenvalues[A, -1, Method -> {"Arnoldi", "Criteria" -> "Magnitude", "Shift" -> 0}] return the same. $\endgroup$ – Henrik Schumacher Jun 10 at 21:30
  • $\begingroup$ @HenrikSchumacher I would report this to Wolfram support. This problem only happens with the Shift option. $\endgroup$ – Roman Jun 10 at 21:43
  • $\begingroup$ I have reported it already ([CASE:4270162]), but it cannot harm to build up some peer pressure. =) $\endgroup$ – Henrik Schumacher Jun 10 at 21:49
  • 1
    $\begingroup$ I believe Eigenvalues with the default method already uses the "Arnoldi" method when the input matrix is sparse and only a limited set of eigenvalues is requested. So, for sparse matrices, Eigenvalues[A, -1], Eigenvalues[A, -1, Method->"Arnoldi"] and Eigenvalues[A, -1, Method->{"Arnoldi", "Criteria"->"Magnitude"}] should all be equivalent. $\endgroup$ – Carl Woll Jun 10 at 22:08
  • $\begingroup$ @CarlWoll I think you're right. $\endgroup$ – Roman Jun 10 at 22:21

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.