Suppose we use a preconditioned iterative solver for a linear system. If the initial state for the solver can be chosen very close to the exact solution - does this reduce requirements for the preconditioner?
-
5$\begingroup$ It's not the distance to the exact solution but whether the error or residual (depending on the flavor of iterative solver you use) lies in the right eigenspace. (This is roughly the principle behind multigrid methods, in fact.) $\endgroup$– Christian ClasonMar 9, 2016 at 8:55
3 Answers
Practical experience shows that trying to get good initial iterates has little value. For example, in the context of solving partial differential equations, if you take the solution from one mesh, interpolate it onto a finer mesh, and use that as the starting guess for something like a CG iteration to solve the same problem on the finer mesh, then it turns out that you will only need a negligible number of iterations less than if you had started the iteration with a zero vector. The gain is not worth the code or the time to do the interpolation.
The situation is very different, however, if you have a nonlinear problem, or if you used a fixed point iteration rather than something like CG.
-
1$\begingroup$ Interesting +1! Can you provide any references? Or is this your personal experience? $\endgroup$– nluigiMar 9, 2016 at 13:10
-
1$\begingroup$ @nluigi: personal experience, as well as that of others in the community. I'm not aware of a publication -- I'm sure it exists, but have never bothered to search for one. $\endgroup$ Mar 9, 2016 at 23:17
It can be even harmful.
In Liesen/Strakos Krylov subspace methods principles and analysis (Chapter 5.8.3) it is reported that a nonzero initial x0
makes a GMRes iteration first remove unwanted components of x0
before it starts the approximation of the wanted solution.
If a nonzero initial guess is used, it should be rescaled by the Hegedus trick; see the explanation and implementation in the Krypy package.
PS: Nonetheless I made good experience with a nonzero initial guess, when solving the linear systems within a time stepping scheme.
This answer is an addition to the one from Wolfgang Bangerth.
It is certainly not worth to bother with the initial guess for the iterative linear solver if there is any work to be done: coding, solution, interpolation, etc. As the effect of the proper initial guess compared to the zero-vector will be very little.
However, in certain situations, a decent initial guess is actually already available. One example would be a frequency sweep with a constant (over frequency) mesh.
Say, one computes a scattering pattern from an object due to some excitation in the frequency domain and desires to have solutions for a set of frequencies ($\{f_1,\ldots,f_N\}$ – sorted). Now, while solving for the $i$th frequency $f_i$, it totally makes sense to use a solution for a previous frequency $f_{i-1}$ as an initial guess. The solution for $f_{i-1}$ has already been computed and no interpolation needs to be done – thus, saving several iterations for a literally zero cost.
Side Notes:
- it usually makes sense to start from $f_N$ descending to a lower frequency $f_1$ during a frequency sweep such that a solution for a higher frequency becomes an initial guess for a lower frequency.
- certainly, if the frequencies in $\{f_1,\ldots,f_N\}$ are very much apart and solution for $f_i$ has nothing to do with the $f_{i-1}$th – it will be hard to benefit from such initial guess choice.