Skip to content
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 iterative eigenvalue finder for eigs #2179

Closed
cshaa opened this issue Apr 12, 2021 · 4 comments · Fixed by #2237
Closed

Implement iterative eigenvalue finder for eigs #2179

cshaa opened this issue Apr 12, 2021 · 4 comments · Fixed by #2237

Comments

@cshaa
Copy link
Collaborator

cshaa commented Apr 12, 2021

The current implementation of eigs relies on usolveAll to find eigenvectors. This often fails because of numerical errors. A more robust approach would be to use an iterative algorithm. The easiest one in this case would be the inverse iteration algorithm. The gist of the algorithm is this:

  1. Take a random vector b.
  2. Let A be a matrix and k an approximation of its eigenvalue.
  3. The expression ( (A − kE)⁻¹ )ⁿ b converges to an eigenvector as n → ∞.
  4. Instead of actual inversion, which is a costly operation, we can perform an implicit inversion using usolve bₖ = (A − kE) bₖ₊₁.

The relevant code is here.

@cshaa cshaa changed the title Implement iterative eigenvalue finder Implement iterative eigenvalue finder for eigs Apr 12, 2021
@josdejong
Copy link
Owner

Thanks for the clear explanation, makes sense. Are you planning on picking this up yourself @m93a?

@cshaa
Copy link
Collaborator Author

cshaa commented Apr 18, 2021

Are you planning on picking this up yourself?

When I have the time and mood, yes, definitely. (I expect this means in a month or so, but I can't tell with certainty.) However, if anyone wants to tackle this issue earlier, feel free to :)

@josdejong
Copy link
Owner

👍

@josdejong
Copy link
Owner

Published now in v9.4.2

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants