Does this partial eigen-expansion have a name?

Question

This question is a follow-up to this one.

Let $A\in \mathbb{R}^{n\times n}$ be large, sparse, symmetric and positive definite. Suppose for I already know $m<n$ eigenpairs of $A$, corresponding to the largest eigenvalues, i.e. $\{( \lambda_i, \vec{q}_i) \}_{i=1}^m \subset \mathbb{R}^+\times \mathbb{R}^n$.

I need to solve $A \vec{x}=\vec{b}$ for $x$.

The idea is that we expand $\vec{x}$ as $\vec{x}=\sum_{i=1}^m \chi_i \vec{q}_i + \sum_{i=m+1}^n \chi_i \vec{q}_i$. Now since the eigenvectors are orthogonal, we can take the dot product of both sides of the equation with $\vec{q}_j$, say, and immediately recover that $\chi_j = \vec{q}_j\cdot \vec{b}/ \lambda_j$. So we define

$$\vec{x}_\mathrm{guess} = \sum_{i=1}^m \frac{\vec{q}_i\cdot \vec{b}}{\lambda_i} \vec{q}_i,$$ and use it as the first guess to any iterative solver.

I would be shocked if this isn't a standard idea, but I don't know what it is called. What is it's name? I would especially like to know what papers to cite.

Answer 1

This is something like a truncated SVD or eigenvector expansion of your solution. If you take

$$x_m = \sum_{j=1}^m \frac{q_j\cdot b}{\lambda_j}q_j$$

with $m=n$, this is the exact solution to $Ax=b$. If you take instead the $m<n$ eigenvalues in the sum instead, you get an approximation. The problem is that it's a pretty poor approximation; since your eigenvalues are sorted from largest to smallest, $1/\lambda_n$ is the largest term in your series and your error is

$$\|x-x_m\| = O(1/\lambda_{n})$$

Intuitively, small eigenvalues correspond to low-frequency components in systems, which tend to have the largest components. Approximating your solution using higher frequency (larger magnitude eigenvalues) gives a good approximation of a matrix-vector product, but not the solution of a linear system.

Answer 2

I don't know for sure whether there is an existing name for this method, but @jessechan's suggestion of "truncated eigenvector expansion" sounds perfectly fine to me (and most people would understand it).

Your question had a second part embedded, namely why is this not what everyone does to get a good initial guess for iterative solvers? The answer to this is that for all interesting cases, computing eigenvectors and eigenvalues is an extremely expensive proposition, far more expensive than doing a few more iterations (which are typically rather cheap). As a consequence, within our community of computational scientists, we most frequently don't try very hard to get good initial guesses for iterative solvers for linear system. If you happen to have a good initial guess (e.g., the previous solution's timestep, or an extrapolation of the previous two time steps), then use it; if you have to work to get an initial guess, forget it -- it's going to be too expensive.