Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
    
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? –  shuhalo 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

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.)

share|improve this answer
    
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. –  Alexander Oct 18 '12 at 10:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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