# 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... – Henrik Schumacher Apr 13 '20 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... – Henrik Schumacher Apr 13 '20 at 9:12
• Thank you, @HenrikSchumacher. I will definitely send them an email – Dario Rosa Apr 13 '20 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? – Dario Rosa Apr 20 '20 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. – Henrik Schumacher Apr 20 '20 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;
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! – Dario Rosa Apr 22 '20 at 4:43