Implement a method to calculate only largest eigenvalues

[StHagel]

Is your feature request related to a problem? Please describe. faer is very fast at computing all eigenvalues of a matrix, but oftentimes you only need a few eigenvalues (e.g. the largest/smallest ones). In fact, when I benchmark it against the spectra C++ library (which is based on eigen3), faer outperforms it by a lot when calculating all or almost all eigenvalues of a 4096x4096 matrix (~23s for faer, ~650s for spectra), but when only calculating the largest eigenvalue, spectra outperforms faer by a lot (again 23s for faer, ~0.22s for spectra).

Describe the solution you'd like It would be great, if faer would incorporate a pure-rust implementation of an eigenvalue finding algorithm, that is able to calculate only a specified number of the largest/smallest eigenvalues. Typically, other libraries (spectra, arpack, slepc, ...) use methods based on Krylov subspaces, such as Arnoldi iteration, for these tasks. Maybe something along those lines would be a feasible and worthwhile extension to faer?

Describe alternatives you've considered Thus far, I have not found any pure-rust crates to efficiently calculate eigenvalue problems with dense, non-hermitian matrices, where only a few eigenvalues need to be calculated. The ones that come closest are arpack-ng, which is essentially a wrapper around the Fortran library arpack, and faer. arpack-ng has its own fair share of problems, which is why I thus far always used the cpp crate to call into the spectra library.

Additional context Benchmarks run on a AMD Ryzen 9 5950X processor https://en.wikipedia.org/wiki/Arnoldi_iteration https://en.wikipedia.org/wiki/Krylov_subspace https://spectralib.org/ https://slepc.upv.es/ https://crates.io/crates/arpack-ng

[guiburon]

Hi,

I am not related to the faer crate but I am curious.

Was your 4096x4096 matrix dense in your example? Spectra seems to be a sparse eigensolver. I think Arnoldi iteration eigensolvers in general are much more suited to sparse eigenproblems. Also the rule of thumb for Arnoldi iteration is that you need a Krylov subspace 2 times larger than the number of eigenpairs wanted so it is very ill suited to computing all the eigenpairs.

May I suggest taking a look at power iteration and subspace iteration if you want the dominant or the few largest eigenpairs? Otherwise, I think for general dense matrices it is typically not faster to extract less than all of the eigenpairs. I am curious about what would be the faer approach though.

[sarah-quinones]

I've recently been studying iterative solvers so this is on my to-do list for the near future

[StHagel]

Hi,

I am not related to the faer crate but I am curious.

Was your 4096x4096 matrix dense in your example? Spectra seems to be a sparse eigensolver. I think Arnoldi iteration eigensolvers in general are much more suited to sparse eigenproblems. Also the rule of thumb for Arnoldi iteration is that you need a Krylov subspace 2 times larger than the number of eigenpairs wanted so it is very ill suited to computing all the eigenpairs.

May I suggest taking a look at power iteration and subspace iteration if you want the dominant or the few largest eigenpairs? Otherwise, I think for general dense matrices it is typically not faster to extract less than all of the eigenpairs. I am curious about what would be the faer approach though.

Spectra does have methods for dense matrices as well (https://spectralib.org/doc/classspectra_1_1geneigssolver), which I have been using in my example benchmarks (the 4096x4096 matrices have all been dense). Spectra is in fact not well suited for finding all the eigenvalues, but in my applications I only need the leading eigenpairs, hence this issue, asking for a way to get those using faer.

I've recently been studying iterative solvers so this is on my to-do list for the near future

Awesome! Btw, if such a method would also calculate the eigenvectors, that would be even more awesome :)

[StHagel]

Hey there, it's me again.

Did you have time yet to look into this? If not, is there a way I can help out with it? If you point me towards some specific algorithm(s), which would suite this usecase in faer and point me towards where in the repo such a method would make most sense, I could see if I can write up a draft for a PR to work with.

[Makogan]

@StHagel I am not related to the faer project, but if oyu want to implement a state of the art iterative eigenvalue solver that only finds leading eigenvalues, I recommend searching for the krylov schur method.

[StHagel]

I recently saw commit bb213d11f98689df415c7af12d70be8ba4a59029. I think that means it is being worked on.