Given a sparse matrix M and a vector v, I would like to get the k eigenvectors of M that have the most overlap with v.
Is there an efficient method for doing this with sparse matrices ? All sparse solvers I ran into target specific eigenvalues, not specific eigenvectors.
Can you look for the couple eigenvectors with eigenvalues closest to Mv? It feels like these should be similar if not precisely the same.
By “overlap” you mean the largest |x^T v| / \Vert x \Vert or something like that?
Can you give us a little information about the context in which this problem arises?
You need a scalar — I assume you mean something like the Rayleigh quotient v^T M v / v^T v?
One can construct counter-examples in which an eigenvalue equals the Rayleigh quotient for v but a corresponding eigenvector is orthogonal to v.
For example, let M = Diagonal([-1, 0, 1]), and let v = [1,0,1]. Then the Rayleigh quotient v^T M v / v^T v is zero, which is also an eigenvalue, but the eigenvalue 0 of M corresponds to an eigenvector x = [0,1,0] that is \perp v.
2 Likes
Yes I think that would be a good start. But eventually I would like something more general:
I would like to extract eigenvectors that are localized on a certain subspace, i.e. eigenvectors that maximize \sum_i^{n}|x_i|^2/ \Vert x \Vert^2 where n defines some localization length.
Context: I want to extract localized eigenmodes of a certain quantum system. You can think of M as a Hamiltonian and x as a local eigenstate.
Unless you are looking for something like embedded eigenvalues or Anderson localization, localized modes typically arise in a portion of the spectrum like a band gap that can be identified in advance, no?
That being said, there should be methods that applicable for your problem, because of course people look for localized modes in all sorts of wave systems (both classical and quantum) all the time.
For example, there are time-domain methods where you “whack” the system with a localized source in the region of interest, and then evolve the oscillating system in time, e.g. you evolve dx/dt = iAx for an initial condition x(0) = v. (Typically this will be in a system with dissipation or outgoing boundary conditions so that localized modes are resonances that decay slowly.) Then you analyze a time signal like s(t) = v^T x(t) of the localized response and look for resonances — naively, sharp peaks in the Fourier spectrum, but there are more efficient methods (related in spirit to Prony’s method) that allow you to extract the dominant peaks, such as filter-diagonalization methods (Mandelshtam & Taylor, 1997), which are closely related to kernel-polynomial methods often used to analyze things like disordered systems.
More generally, you might think about whether your problem can be re-framed in terms of quantities like the local density of states (LDOS) in the region of interest. LDOS and related quantities, which are essentially the response to localized sources (the power expended by localized sources in analogous classical systems) are much easier to deal with numerically because they represent solutions of linear systems, not eigenproblems.
In general, I would think more carefully about why you want the eigenvectors: what sort of information do you want to extract from them? There are often ways to get at that information directly without going through eigenvectors first.
5 Likes
Thank you,
Indeed, I’m just realizing I actually don’t need the eigenvectors.
Here is my new problem:
Given a sparse matrix M and a vector v, find the k eigenvalues \lambda_n with the largest amplitudes a_n=\langle v,w_n \rangle. (I also need the a_n associated with the \lambda_n).
Is this a common problem ?
I have tried to time evolve v, and Fourier transform c(t)=\langle v(t),v(0) \rangle. This somehow works but I get quite large errors when I compare this to dense diagonalization for small matrices. I’d like if there was a more direct method.
As I commented above, this simple approach is inefficient in practice, because due to the uncertainty principle you need to run for quite a long time to get good resolution. That’s why people uses more efficient methods like the ones I mentioned above.
Can you provide some context on what underlying problem you are solving?
1 Like