Efficiently computing a few localized eigenvectors - MathOverflow

Efficiently computing a few localized eigenvectors

2012-02-11T02:18:54Z

Let $H = \triangle + V(x) : \mathbb{R}^2 \rightarrow \mathbb{R}^2$. I am interested in domain decomposition for an eigenproblem involving $H$.

The lowest 1000 eigenfunctions of $H$, $ \psi_i $, can be partitioned using a region, $\Omega \subset \mathbb{R}^2$, such that each $\psi_i$ localizes either inside of $\Omega$ or outside of $\Omega$. $\Omega$ is not a subspace of $\mathbb{R}^2$ as it may be an oddly shaped region.

Label the inner eigenfunctions $\psi_i^{in}$ and the outer ones $\psi_i^{out}$. There's only about 10 $\psi_i^{in}$s. Given $\Omega$, my goal is to efficiently compute the $\psi_i^{in}$.

One way to find the $\psi_i^{in}$ would be to discretize, compute all 1000 $\psi_i$s, and then partition. This is what I do now (5-point stencil for $\triangle$ on a $10^3 \times 10^3$ grid). The problem is that this requires diagonalizing over a 1000 dimensional space in order to get 10 eigenvectors. It seems like there would be a cheaper way to compute the $\psi_i^{in}$.

Edit: I reposted to http://scicomp.stackexchange.com/questions/1396/efficiently-computing-a-few-localized-eigenvectors#comment2200_1396 and hopefully clarified the problem statement.

Edit I think I can solve this if I can at least figure a way to solve \begin{equation} \max \psi^T H \psi \text{ subject to } P\psi = \psi \text{ and } \psi^T \psi = 1 \end{equation} where $P$ is projection onto the space of functions localized over $\Omega$. My guess is that this will end up looking like power iterations with a projection step built in between matrix applies. If this is doable then something like inverse iteration should be doable which will give me what I want.

Answer by Federico Poloni for Efficiently computing a few localized eigenvectors

2012-02-11T09:15:41Z

Just a random idea:

The standard method for getting a small part of the spectrum in large and sparse symmetric problems is the restarted Lanczos method. Essentially, you run some iterations of the Lanczos method, then you check the eigenpairs that have been computed, keep some of them and throw away the rest. Typically the pairs to drop and keep are selected based on the eigenvalues (you want the ones with smallest or largest modulus, for instance), but in this case you could try to modify the method and keep the ones that are "localized" in your region of interest.

Problems:

I cannot tell you for sure that this would work --- as far as I know there is no easy way to tell to which eigenvalues Lanczos will converge, and it is known that it has a tendency to converge to those at the border of the spectrum, so your efforts to steer it away from selected eigenpairs could be useless.
As far as I know, hooks for the selection strategy are not present in the usual Lanczos implementations, so you may have to code it yourself.

In any case I agree with Suvrit's comment --- your dimensions are kind of borderline for Lanczos to be more effective than full diagonalization.

Answer by Kirk S. for Efficiently computing a few localized eigenvectors

2012-02-11T16:12:51Z

To build on Federico's answer, why not run a restarted Lanczos iteration but compute harmonic Ritz vectors to get approximations to the interior eigenpairs? For something so small, though, why not just diagonalize, as has already be stated.