1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Christian Clason Feb 11 '17 at 16:50
1
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.