Search for eigenvalues under a specific upper boundary

Hello, I am trying to solve an eigenvalue problem in which eigenvalues lesser than a upper boundary are solved.

The linear operator is hermitian or real symmetric, and the eigenvalues are guaranteed to be positive, so I just need to specify a upper bound. Because the problem is large and I only need the lowest eigenvalues, I have used iterative methods, specifically KrylovKit.jl. My state vectors are structured so turning it into AbstractVector would lose all the structure, and VectorInterface.jl solved the problem for me.

As for the iterative eigensolves I’ve investigated (KrylovKit.jl, ArnoldiMethod.jl), they have the EigSorter argument which specifies the requirement for the first eigenvalue.

From my very small understanding we could write a restart algorithm where the Krylov subspace are saved and reused.

Sorry for the clumped post, is there any solver out there that can use a generic Vector and calculate eigenvalues in a bound?

It sounds like you have already solved the problem? What is wrong with KrylovKit and VectorInterface for your task?

Sorry, it seems like I didn’t state the problem clearly. The problem is I can specify the number of eigenvalues, but not all the values (generally an unknown number of) under a certain boundary.

With the current algorithm, to calculate all eigenvalues under a upper bound, say bound, I have to specify a guessed number to solve, say n, in the solver, but the problem is:

  1. if the largest eigenvalue in total n of them is way larger than bound, then I wasted calculation time;
  2. else the largest eigenvalue is still lesser than bound, then without a restart algorithm(in my knowledge), I’ll have to specify a larger n and start the calculation all over again, which may not even be enough this time, and the process goes on and on…

Well, in my knowledge the krylov algorithm needs a krylovdim parameter to build the krylov subspace, and calculating eigenvalues in a range means unknown number of solutions. So determining krylovdim could be tricky and not enough. But I think a new algorithm could be where user specifies krylovdim and bound, and once the algorithm uses all krylov space it just expands it(could it work?), and continue until the largest eigenvalue reaches bound. (This paragraph is just me rumbling :slightly_smiling_face:)

Sorry for another clumped reply.

KrylovKit main developer here. While what you request is certainly feasible within the current implementation (provided that at least krylovdim is large enough to capture all the eigenvalues smaller bound), it is indeed currently not supported in the way the function is called and the arguments are specified.

As is often the case, the hardest part is coming up with a good interface to support these different ways of specifying the problem. Asking for a fixed number of eigenvalues is the typical interface provided by these Krylov eigensolvers.

Maybe you can open an issue about this on the KrylovKit github repository?

PS: Note that KrylovKit already returns all the eigenvalues that have converged, when more than the requested number have converged.

Would love to open an issue for this.

You said that krylovdim must be large enoigh, so dynamically adjusting the krylov subspace is not possible? Does this mean a restart algorithm that reuses and expands krylov subspace is not possible?

The krylov subspace is of course expanded and shrunk and expanded again during the course of the eigsolve algorithm. It is just that the maximal dimension of the Krylov subspace to which it is expanded before there it is shrunk and restarted, is currently also a fixed parameter that you specify.

But since the eigsolve interface and implementation would anyway need to be changed to accommodate a bound argument, I guess making the krylovdim dynamic at the same time is also possible. It is just not easy to do this in a “black box” manner, i.e. what are reasonable values for the maximal dimension of the Krylov subspace? That can be very much problem dependent.

I guess one way to do this is let user specify an initial krylovdim and an increment size n. So that once all krylovdim eigenvalues have converged and still not enough, just increment it by n.