-
-
Notifications
You must be signed in to change notification settings - Fork 1.2k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Implement eigenvalue estimation for eigs #2178
Comments
So this would improve performance, that's always nice! |
Looking at the literature, one simple choice (that used to be commonly used, but apparently has been superseded in more recent even better algorithms) is just to take k to be the bottom right corner of the current approximation to the desired triangular matrix. I just tried this, and it passes all tests and vastly improves the precision which one can use in computing the eigenvalues of the "bad" matrix in #3036 from 1e-4 to 1e-15. [Digression: This "tiny" precision 1e-15, which is smaller than the "standard" precision config.epsilon, does not produce any more accurate eigenvalues than config.epsilon does for this bad case; in fact config.epsilon produces the closest to the true eigenvalues, which are all exactly 2 -- at config.epsilon precision, they are off by around 5e-6. And shrinking both config.epsilon and the precision used doesn't improve the results either; in fact, the computed eigenvalues seem to be converging on fixed values slightly farther away from the "true" ones as config.epsilon and the precision parameter shrink below 1e-12. Perhaps we have simply reached the limit of what the combination of IEEE double arithmetic and this algorithm can accomplish with this numerically tricky matrix. Perhaps unsurprisingly, though, if one simply "guesses" the correct shift k=2 for this matrix, it not only converges right away to essentially the correct values, it also realizes that the matrix is defective, which it never does with the simple choice of the bottom right corner for k, at any precision level. Didn't try with bignumbers though; it might stand a chance there.] Anyhow, all this suggests that I should add the simple one-line change from k=0 to k = (bottom right corner of current approximation) to the current PR #3037, even though it's actually orthogonal to the issue that PR addresses, and then close this issue because it seems to be a big improvement to the convergence of the algorithm, for almost no time investment on our part, and looking into superior methods would presumably require significant immersion in the literature on this, time which might be better spent just using software that others have optimized for eigenvalue/eigenvector problems. Or I could do a separate subsequent tiny PR with this small change once #3037 is merged but still before v12, if you prefer. Let me know. |
That is awesome news @gwhitney 😎 If it's such a small change in the code, feel free to directly apply it in PR #3037. Is there still a reason to specify a custom Would this in itself be a breaking change though? (Since you're discussing it in the v12 breaking changes topic?) |
OK will do that after I respond to all the code review in #3037. This is not a breaking change, just an improvement of results, but it only works on top of #3037, which is breaking. |
Oh and on precision: it's also totally necessary with bignumbers, and I think always will be. |
Thanks! OK all is clear to me 👍 |
…ergence Although we might want to use better shifts in the future, we might just use a library instead. But for now I think this: Resolves josdejong#2178. Also responds to the review feedback provided in PR josdejong#3037.
The current eigenvalue algorithm supports shifting however as of now it is not used. The gist of shifting is this:
As I said, the shifting is already implemented, the only thing that needs to be done is to set
k
close to an eigenvalue. The relevant code is on this line.The text was updated successfully, but these errors were encountered: