3
$\begingroup$

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).

Is there any updates about this problem?

Improve this question
$\endgroup$
6
  • $\begingroup$ 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... $\endgroup$
    – Henrik Schumacher
    Commented Apr 13, 2020 at 9:10
  • 1
    $\begingroup$ 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... $\endgroup$
    – Henrik Schumacher
    Commented Apr 13, 2020 at 9:12
  • $\begingroup$ Thank you, @HenrikSchumacher. I will definitely send them an email $\endgroup$
    – Dario Rosa
    Commented Apr 13, 2020 at 12:19
  • $\begingroup$ 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? $\endgroup$
    – Dario Rosa
    Commented Apr 20, 2020 at 16:55
  • $\begingroup$ 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. $\endgroup$
    – Henrik Schumacher
    Commented Apr 20, 2020 at 17:05

1 Answer 1

Reset to default
4
$\begingroup$

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 *)
Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! It's a smart idea! $\endgroup$
    – Dario Rosa
    Commented Apr 22, 2020 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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