GMRES : incomplete Krylov-subspace

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?

• Note that you don't have to invert $V$, so it's no problem that it's not square -- the product of $V\in\mathbb{R}^{N\times P}$ with $y\in \mathbb{R}^P$ is well-defined (and in $\mathbb{R}^N$, so the right size for $x$). You do have to invert a matrix to compute $y$, but that one is in $\mathbb{R}^{P\times P}$, so again no problem. – Christian Clason Feb 11 '17 at 16:50

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.