# Does right-hand side influence convergence rate of a Krlylov supspace method?

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

Thanks.

-

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.

-
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. –  chris Oct 19 '12 at 13:06
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. –  Andrew T. Barker Oct 22 '12 at 14:21
@Wolfgang Bangerth: Please correct me if I am wrong, but isn't using precomputed solutions the basic idea of cascading multigrid? –  Martin Oct 29 '12 at 8:03
I don't know cascading multigrid enough to say. It certainly makes sense for nonlinear problems, though. –  Wolfgang Bangerth Oct 30 '12 at 2:52