Finding specific eigenvalues

Question

Given an $n\times n$ matrix $Q$ (with e.g. $n\approx10^4$) I am only interested in the 3rd smallest eigenvalue of $Q,$ and not the entire spectrum (assume all eigenvalues are real, e.g. a Hermitian matrix). So one direct way would be to solve the Eigensystem, order the eigenvalues and pick the 3rd one:

{eigv, U} = Eigensystem[Q];
order = Ordering[eigv];
eigv = eigv[[order]];
res = eigv[[3]];

1. (Main question): But is there a way to go about this in a more targeted and efficient way considering that we know which eigenvalue we are looking for?

2. In the above I order the eigenvalues, but if we don't, does Eigensystem arrange them in a specific order already?

---

Addendum:

The matrix can has only nonnegative eigenvalues (M-matrix), and its first eigenvalue, $\lambda_0,$ is typically $0.$ Therefore, the idea is to find the 3rd smallest eigenvalue $\lambda$ in magnitude, knowing that the real parts of all $\lambda$ are nonnegative. These properties are e.g. satisfied for Laplacian matrices of graphs, in this case graphs with $10^4$ nodes.

Answer 1

Here is an example of what I had suggested in a comment. We will work with a 100x100 symmetric sparse matrix, and make it diagonally dominant (or close enough to that) so that all eigenvalues are positive.

rng = 100;
nonzerocount = 3*rng;
SeedRandom[1111]

mat0 = SparseArray[
   Thread[RandomInteger[{1, rng}, {nonzerocount, 2}] -> 
     RandomReal[{0, 1}, nonzerocount]], {rng, rng}];
mat = mat0 + Transpose[mat0] + SparseArray[{a_, a_} -> 5, {rng, rng}];

First check the smallest eigenvalues using the method we want to avoid:

Eigenvalues[mat, -5]

(* Out[337]= {2.6747750632, 2.43141432273, 2.40432837499, 2.30813913679, \
1.93291151486} *)

So these are values we hope to attain without requiring an linear equation solving under the hood.

First get the biggest eigenvalue.

eigbig = First[Eigenvalues[mat, 1]]

(* Out[338]= 8.94206162291 *)

Now shift by the negative of this largest, and obtain the three most negative eigenvalues, along with their corresponding eigenvectors. Shift back to get the correct eigenvalues, that is, the smallest positive ones from the original matrix.

matShifted = mat - SparseArray[{a_, a_} -> eigbig, {rng, rng}];
smallEig = Eigensystem[matShifted, 3];
smallEig[[1]] + eigbig

(* Out[344]= {1.93291151486, 2.30813913679, 2.40432837499} *)

We have recovered the ones we wanted.

When I instead use a dimension of 10000 it takes around 0.1 seconds on my desktop to find the largest eigenvalue, and around 0.5 seconds to get those eigenvalues and corresponding eigenvectors. Finding them using Eigensystem[mat,-3], in contrast, requires 6.8 seconds.

Answer 2

As yarchik says in the comments, you can use the "Arnoldi" method. However, the "Arnoldi" method doesn't work well for finding the smallest real eigenvalues (perhaps a bug), but you can instead find the largest real eigenvalues after changing the sign of the matrix. Here is an example Hermitian matrix (so eigenvalues are real):

SeedRandom[1];
m = (ConjugateTranspose[#] + #)& @ RandomComplex[10+10I, {10, 10}];

Finding the full eigenvalues (I use Eigenvalues, but Eigensystem works similarly):

Eigenvalues[m] //ReverseSort

{98.0228, 23.1452, 18.0616, 12.4434, 8.72238, -0.890917, -9.86992, -13.0016, \ -20.4409, -26.7991}

Now, using the "Arnoldi" method:

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

{-13.0016}