Consider general system $Ax=b$. Does convergence of the Krylov subspace methods depend on actual vector $b$ assuming the initial guess is zero? I mean such factors as the locality of the source (with the limit case where RHS represents delta source) or the dynamic range of the values in there. Does finite precision play any role here?


Of course. The common Krylov space methods build the solution of $Ax=b$ as an approximation first in the space $\{r\}$ (where $r=b-Ax_0$ with the initial guess $x_0$), then $\{r,Ar\}$, then $\{r,Ar,A^2r\}$, etc. So the space in which the solution is sought depends on the right hand side vector. If your solution happens to be, say, in $\{r,Ar,A^2r\}$, then the iteration will terminate after 3 iterations.

That said, if you ask about this from a purely practical perspective, then the answer is no. In practice this kind of lucky breakdown of the iteration rarely happens, and it is a common observation that the number of iterations you need does not depend strongly on the right hand side, just as it doesn't depend strongly on the starting guess of your iteration. For example, in adaptive finite element methods one might think that it's worthwhile starting a CG iteration on one mesh with the solution from the previous mesh interpolated to the current mesh -- because it should already be close to the solution on the current mesh. However, it's not worth it: the number of iterations might be slightly lower but not enough to justify the effort of interpolating the solution. What this shows is that in practice, convergence of Krylov methods is by and large given by the matrix, not the right hand side or the starting guess.

  • 2
    $\begingroup$ From a pratical perspective, I've seen GMRES converge perfectly with $P^{-1} b$ as initial guess ($P^{-1}$ being the preconditioner) while not converging at all with $0$ as initial guess. $\endgroup$ – chris Oct 19 '12 at 13:06
  • 1
    $\begingroup$ I agree that the right hand side usually does not affect the convergence much, but an example where it does matter significantly is given in Liesen and Strakos, GMRES convergence analysis for a convection--diffusion model problem, SIAM J. Sci. Comput. 26 (2005) pp. 1989--2009. $\endgroup$ – Andrew T. Barker Oct 22 '12 at 14:21
  • $\begingroup$ @Wolfgang Bangerth: Please correct me if I am wrong, but isn't using precomputed solutions the basic idea of cascading multigrid? $\endgroup$ – shuhalo Oct 29 '12 at 8:03
  • $\begingroup$ I don't know cascading multigrid enough to say. It certainly makes sense for nonlinear problems, though. $\endgroup$ – Wolfgang Bangerth Oct 30 '12 at 2:52
  • $\begingroup$ Great answer, but I am not sure I get the argument in your first paragraph. In principle it may happen that $x$ is in that subspace, but since both $r$ and $x$ depend on $A$ and $b$, it is not at all evident that you can construct explicitly an example when this happens. $\endgroup$ – Federico Poloni Sep 5 '20 at 7:08

Just a note. I suppose you are talking about the special case of the Poisson problem. (?)

The behaviour of Krylov subspace methods depends on the initial residual. This is only the right-hand side if the initial guess is zero, which is not necessarily what you want in numerical pde, because you might have good approximations through computations on coarser grids available.

If you regard symmetric systems, then it suffices to regard a diagonal matrix to study all relevant cases (in exact arithmetics). So the convergence behaviour depends on the decomposition of the initial residual into eigenmodes of the Laplacian on your ansatz space.

(Eventually, I suppose it gets worse because the Dirac delta, as a distribution, is the superposition of a "large share" of eigenmodes of the Laplacian. Take a look at the Fourier transform on the real line.)

  • $\begingroup$ I didn't mean Poisson problem, but thanks for considering this special case. Your point about zero initial guess is also good, I edited question. I'm particularly interested if more experienced (than myself) people can infer general empirical rules on subject. $\endgroup$ – Alexander Oct 18 '12 at 10:29

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.