# Arnoldi method misses eigenvalues degeneracies for very sparse matrices

I am here to signal a problem very very similar to the one already discussed here

Wrong eigenvalues from a sparse matrix

In particular, I have a very sparse matrix and I am asking just few dominant eigenvalues.

I noticed that, while the algorithm (arnoldi, with max iterations very large ~ 10^6) finds the correct eigenvalues, It misses the degeneracies (my matrix as a double degeneracy for all the eigenvalues). A funny feature is that the problem gets solved if instead of asking very few eigenvalues (say, 10) I ask some more (say, 40).

• Thank you for pointing this out, although this is not the official support ;). Basically all eigensolvers have difficulties with degenerate eigenvalues. I am afraid there cannot be any other solution than increasing the size of the Krylov subspace -- what you already did. Sometimes, adding a "Shift" in the suboptions of the Arnoldi method can help (see Method subsection of the documentation of Eigensystem). One time, I observed adding "Shift"->0 or "Shift"->None alreayd helped for some reason... Commented Apr 13, 2020 at 9:10
• It would be a good idea to also tell the support about. I have the suspect that many important linear algebra routines in Mathematica have not enjoyed an update for some 20 + X years. Maybe that will help to focus Wolfram Research's work force onto the things that really matter... Commented Apr 13, 2020 at 9:12
• Thank you, @HenrikSchumacher. I will definitely send them an email Commented Apr 13, 2020 at 12:19
• Dear @HenrikSchumacher sorry to bother you again. I have a further simple question: once the matrix is given, the speed of the computation of the first, say N, dominant eigenvalues, specifying Arnoldi method and the max iterations, should be comprable between mathematica and, say, Matlab or Python, right? I guess they should be very similar because all the three software work with ARPACK. Can you confirm? Commented Apr 20, 2020 at 16:55
• No problem. And yes: For most of the linear algebra, all these tools utilize standard libraries (e.g., all three use sparse and dense linear algebra provided by the Intel Math Kernel Library). So they should behave essentially in the same way. There might however some performance degradations caused by the communication between the interpreting language and the libaries that to the heavy lifting. With respect to the backend of Eigensystem see also the discussion here. Commented Apr 20, 2020 at 17:05

I have also encountered this issue and it occurs also for small Sparse matrices. In order to identify whether the eigenvalues supplied by the Arnoldi algorithm are degenerate or not I deform the matrix by adding to it a diagonal matrix with random elements that are about 5-6 orders of magnitude less than the original matrix. This usually slightly lifts the degeneracy so that the algorithm is able to identify the extra eigenvalues. Here is an example:

    SeedRandom[111];
n = 100;
rC = SparseArray[
Transpose[{RandomInteger[{1, n}, n], RandomInteger[{1, n}, n]}] :>
RandomComplex[],
{n, n}] (* random complex n x n sparse matrix *) ;
rH = rC + ConjugateTranspose[rC] (* random hermitian n x n sparse matrix *) ;
M = ArrayFlatten[{{rH, 0}, {0, rH}}] (* M has doubly degenerate eigenvalues *) ;
Chop[Eigenvalues[M, 4]] (* Arnoldi eigenvalues *)
Chop[Eigenvalues[
M + SparseArray[Band[{1, 1}] :> RandomReal[], Dimensions[M]]/10.^6,
4]] (* Arnoldi eigenvalues after adding a small random diagonal matrix *)
Eigenvalues[Normal[M]][[1 ;; 4]] (* exact eigenvalues *)


which gives

{2.74461, -2.66169, 2.60291, -2.52665} (* Arnoldi eigenvalues *)
{2.74462, 2.74462, -2.66169, -2.66169} (* Arnoldi eigenvalues after adding a small random diagonal matrix *)
{2.74461, 2.74461, -2.66169, -2.66169} (* exact eigenvalues *)

• Thank you! It's a smart idea! Commented Apr 22, 2020 at 4:43