6
$\begingroup$

Short synopsis: for a specific family of sparse matrices, the eigensolver seems to be unstable (kernel quitting) for certain examples, and when it works it seems to consistently return vectors which are not eigenvectors.

I would like to know if there are any known options or pre-conditioning methods which fix this, and which are feasible for large sparse matrices.

More details:

I have a family of sparse Hermitian cyclic-banded matrices $M$, and I want to calculate the smallest (absolute value) eigenvalue for each of them.

However, the kernel seems to unexpectedly quit (a problem which I have not diagnosed) during execution of Eigensystem.

In a possibly related problem, when Eigensystem executes without quitting the Kernel, it consistently returns vectors which are not eigenvectors.

An example $1220\times1220$ matrix which can be obtained using Import (not Get) can be found here. The matrix is hermitian (see In[4] in image below) converting to a dense matrix and solving yields an eigenvector $\phi$ (In[5]) which satisfies the eigenvector equation (Out[7]).

Working with sparse matrices is much faster (compare $\tau$ from In[5] and In[8]) but is not even close to satisfying the eigenvector equation (Out[10]).

Using Method->banded resolves the issue (Out[13]), but the performance is horrible ($\tau$ from In[11] is worse than the dense solve).

I believe the default method is Arnoldi, and I have been unable to fix this by playing around with the options. Arnoldi always returns a vector which does not satisfy the eigenvector equation, even if it is handed the correct solution as the sarting vector.

Is there anything I can do about this problem?

Possible Bug??

$\endgroup$
  • $\begingroup$ what version are you running? and what OS, too? including the os version, of course. $\endgroup$ – rcollyer Sep 19 '18 at 4:25
  • 1
    $\begingroup$ 11.2.0 for Mac OS X x86 (64-bit), Mac OS High Sierra 10.13.3 (17D47). Problem also occurs on the cluster I have access to as well, which is running 11.1.1 for Linux x86 (64-bit). $\endgroup$ – ComptonScattering Sep 19 '18 at 4:30
  • 1
    $\begingroup$ ok. I'll look at it more thoroughly in the morning. $\endgroup$ – rcollyer Sep 19 '18 at 4:33
  • 2
    $\begingroup$ There's known issues with the lowest eigenvalue for some of the sparse methods. But, setting Method -> "FEAST" works very well. $\endgroup$ – rcollyer Sep 19 '18 at 13:38
  • 2
    $\begingroup$ @rcollyer That is really unfortunate as the lowest eigenvalue is frequently the most important one... Would be great to see that repaired soon. $\endgroup$ – Henrik Schumacher Sep 19 '18 at 17:07
5
$\begingroup$

Perhaps you can add a "Shift" option to help out the Arnoldi algorithm:

{{λ}, {v}} = Eigensystem[
    M,
    -1,
    Method->{"Arnoldi", "Tolerance"->10^-12, "Shift"->0}
]; //AbsoluteTiming

{0.007198, Null}

I added the tolerance to get a slightly better result than the default. Check:

λ
Norm[M.v - λ v]

0.0039334

3.96868*10^-15

$\endgroup$
  • $\begingroup$ Interesting - thank you for this - I had assumed Shift->0 was the default setting. Since I was targetting eigenvalues near 0 didn't think it would be helpful to change this. $\endgroup$ – ComptonScattering Sep 19 '18 at 16:41
  • $\begingroup$ As a follow up, I continued to have occasional stability issues that would cause the kernel to quit. These seemed to correspond to cases when there was an exact eigenvalue close to zero. In this case of Hermitian $M$, it seems a small imaginary shift seems to have fixed this, although the convergence is noticeably slower. $\endgroup$ – ComptonScattering Sep 20 '18 at 20:59

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.