GMRES : incomplete Krylov-subspace

Question

At each iteration $i$ of the GMRES method, is calculated a single new orthonormal vector of the existing Krylov subspace. If the norm of that vector is 0 (or close to 0), then the subspace is "complete", and we should be able to calculate the converged solution. In theory, this occurs when we have $N$ orthonormal vectors (where $N$ is the size of $A$).

The solution can then be computed using $$x=x_0+Vy$$ where $V$ is the matrix of orthonormal vectors computed above. [$x_0 (N \times 1),V(N \times N)$ and $y(N \times 1)$].

My question is: What happens if the algorithm finds only $P < N$ orthonormal vectors? How can I complete the Krylov-subspace and how can be computed $x=x_0+Vy$ if $V(N \times P)$ is not a square matrix?

Answer 1

I'm not sure I understand the question, but in GMRES you built a orthonormal base for the space $K_m \; \text{ for } m= 1 \dots N$. In this space the generic vector can be write as: $$ x = x_0 + V_m y$$ where:

• $x_0 \in \mathbb{R}^N $
• $\text{dim}(V_m) = N \times m$
• $y \in \mathbb{R}^m$, $\text{dim}(y) = m \times 1$

During the various steps the algorithm computes the unique vector of $x_0 + K_m$ such that minimize

$$ || b -Ax ||_2 = || b - A(x_0 + V_m y) ||_2 $$

Now the idea, as in other Krilov methods, is to obtain a good approximation after a value $m << N$, if $m=N$ then $K_m = \mathbb{R}^N$ the whole space and you have got the exact solution.

NOTE: $y, V$ have got a different dimension respect your question and this is the key, i.e. there is no problem if $P<N$, it is the normal case, because the dimension of matrix and vector are different.

A good reference for more detail is:

• Saad, Yousef. Iterative methods for sparse linear systems. Society for Industrial and Applied Mathematics, 2003.

Answer 2

If $A$ is invertible and the Krylov subspace $v,Av,A^2v,\ldots$ stops to expand after $m$ steps, then GMRES (and other reasonable Krylov methods) converge to the exact solution in at most $m$ steps (assuming exact arithmetic).

Proof:

The minimal polynomial of $A$ is a minimal-degree $q$ such that $q(A)=0$. Always $m\ge n$.

From http://www.maths.lth.se/na/courses/NUM115/NUM115-05/krylov.pdf p.~5 we get:

Lemma Let $m$ be the degree of the minimal polynomial of a nonsingular $A\in C^{n\times n}$. Then $A^{-1}=\sum_{i=0}^{m-1}\alpha_i A^i$. Thus, $A^{-1}b=\sum_{i=0}^{m-1}\alpha_i A^i b\in K_m$. Moreover, $m=\sum_i m_i$, where $m_i$ is the size of the biggest Jordan block of eigenvalue $i$.

By the lemma, then $x\in K_m$, QED.

However, generally $m$ is close to $n$ (and $m=n$ for almost all random matrices), so that is not the reason why GMRES is good.

By my superficial Matlab tests, Krylov is no better than a random subspace, for random $A,\ b$. Thus, GMRES (and other Krylov methods) need preconditioning, unless the matrix happens to be nice. However, in practice it does usually or at least often. Nevertheless, preconditioning is usually crucial for quick enough convergence.

Convergence depends on eigenvalues. If eigenvalues are in a tight bundle (or most eigenvalues relevant to $b$ lie in a number of tight bundles), then Krylov methods for $Ax=b$ tend to work well.

However, some methods, like IDR(s) or BiCGSTAB do not like very nonreal eigenvalues for real matrices (then use IDRstab or BiCGSTAB(l), instead, respectively). IDR* is better than BiCGSTAB if $A+A^*$ is very indefinite. See https://scicomp.stackexchange.com/a/34521/34228 for more on choosing the method.