3
$\begingroup$

Can someone please explain to me why we are using Krylov subspaces for the CG-Method, GMRES-Method and Arnoldi.

Unfortunately I do not see where the advantages are und why Krylov subspaces are so important/special.

In the literature, it says that the Krylov subspace are search spaces, but I don't understand why

I hope someone can help me

$\endgroup$
0

1 Answer 1

4
$\begingroup$

In optimisation you normally work in a particular space, known as your search space. An example of a simple search space is $\mathbb{R}$ which are the real numbers. Another example is $\mathbb{R}_{>0}$. That is, positive real numbers.

The main aim of conjugate gradient methods is to solve the following equation: $Ax = b$ where $x$ is a vector of unknown quantities, $A$ is symmetric positive definite, and $b$ is known also. It can be difficult to find the inverse for large, sparse systems, so that $A^{-1}$ is hard to calculate. Instead we can use optimisation to find the optimal $A$ to solve this system of equations.

So we have an optimisation problem (find the optimal $A$) and we know optimisation problems need a search space. But the search space is a bit weird now, since we search over an entire matrix! Not something easy like the reals. More accurately, we would like to minimise: $r := b - A x \,$ the residual error.

Now the Kyrlov subspace is defined as follows:

\begin{equation} {\mathcal {K}}_{r}(A,b)=\operatorname {span} \,\{b,Ab,A^{2}b,\ldots ,A^{r-1}b\}. \end{equation}

In the conjugate gradient optimisation scheme there are lines in the algorithm that look similar to things like: $A^{r-1}b$.

Therefore we just say the solution of the conjugate gradient involves spanning the Kyrlov subspace. It is more of a technical note, since remember optimisation needs (i) an objective, (ii) a space on which the solution must exist.

It is more than a technical note, if you want to do research by which then it is important to know the properties of the Kyrlov subspace! It could help in modelling constraints, understanding convergence rates, understanding convergence behaviour etc...

It is similar to understanding Galerkin methods for Finite Element Analysis.... Sure theoretically you need to know Galerkin theory for FEA, but if you are a practising engineer, this knowledge is just a complication. BUT, if you are a researcher, it would be important to go through the derivation, and understand the inner workings of weak formulations, the functions they can permit etc...

This answer goes more into the mathematics intuition of what I just discussed:

https://math.stackexchange.com/a/2714985/580635

$\endgroup$
7
  • $\begingroup$ Thanks for responding! I still dont understand why they call it search space (my thoughts are that we use krylov spaces because we want to find an approximation of an eigenvector so in the span of the vectors we construct the eigenvector as an linear combination of the elements from the span?) and the Galerkin methods just tells that we want to find a good approximation for eigenvectors in A. Here they construct a searh space where the residual is orthogonal to the search space.This has to be orthogonal because the residual is equal to the gradient und this tells us that the error is small $\endgroup$
    – Promendi
    Aug 21, 2019 at 11:42
  • 1
    $\begingroup$ If we want to a find a vector which has a form of $A^{r-1}b$, this vector has to exist inside of the space spanned by $K_r(A,b)$. Also Galerkin methods don't explicitly have anything to do with eigenvectors. I just used this as an example, they have nothing to do with CG methods. I didn't for that to confuse you. The way CG-Method may have been developed is that someone made the algorithm, and it just so happened that someone else noticed the updates looked like elements from the Krylov subspace. Using this knowledge you can better theoretically analyse how the update vectors should behave. $\endgroup$ Aug 21, 2019 at 11:52
  • 1
    $\begingroup$ Just understand at least what a search space is for optimization problems. Alos if you are happy with my answer, please upvote and accept as the recommended answer =) Thanks! $\endgroup$ Aug 21, 2019 at 11:54
  • $\begingroup$ In the lecture we didnt talked about optimization problems that why it is difficult for me to understand it. We started with projection methods and galerkin and after that we said good searspaces are krylov spaces and that we use for arnoldi the krylov space as search spaces.. can you possibly tell me literatures to understand it more :/ and all in all i cant upvote, everytime i try to upvote it tells me this: Thanks for the feedback! Votes cast by those with less than 15 reputation are recorded, but do not change the publicly displayed post score. $\endgroup$
    – Promendi
    Aug 21, 2019 at 12:43
  • 1
    $\begingroup$ That's ok. Maybe try clicking on the "tick" symbol instead of upvoting, this will confirm the answer. That's fine also. As for literature, it is a bit hard without knowing what is a search space from optimization. Maybe try this source to begin with arxiv.org/abs/1811.09025 $\endgroup$ Aug 21, 2019 at 12:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .