8
$\begingroup$

Suppose you solve a linear system $Au = f$ by an iterative method, e.g. conjugate gradients or Richardson iteration. Then you try to solve a linear system that is slightly perturbed in the matrix and the right-hand side, say, $\tilde A \tilde u = \tilde f$.

Does it make sense to use the old solution as starting value $\tilde u_0 = u$ for the iterative method? "Makes sense" means that there is a relyable gain in the running time of the iterative method. I wonder whether this leads to an improvement in general, such that it can be regarded as advised practice.

An application that I have in mind comes from adaptive finite elements. If we have computed a solution $u$ on a coarse grid, and want to find a solution $\tilde u$ on a finer grid (which might have been generated based by an adaptive method), the starting value for any iterative algorithm can be the prolongation of $u$ onto the finer grid. Similarly, the Newton-method or Picard-iteration, which is involved in the solution of nonlinear problems, could be "boosted" that way, if it makes any sense at all.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ At least from a theoretical point of view, recycling a solution on a coarse grid as a starting value on a fine grid gives an initial error bound that grows smaller and smaller as the mesh is (uniformly) refined, while $0$ as a starting value leads to an ever increasing initial error. So very basic error estimates suggest it makes a tremendous difference. - So for me, I still wonder whether this is done in practice. In many communities, it is not standard. $\endgroup$
    – shuhalo
    Mar 5, 2012 at 23:32

2 Answers 2

Reset to default
5
$\begingroup$

We have tried this out with adaptive finite elements where we take the previous solution over to the new mesh by interpolation. It turns out that starting with this vector has no noticeable effect on the number of CG iterations. In other words, for the CG iteration, a good initial guess is mostly useless.

Of course, the situation is entirely different for nonlinear methods (such as Newton's method) where it is absolutely worth it to take the last iterate on the coarse mesh as the starting guess for the fine mesh. In practice, one often does 5-10 iterations on the coarsest mesh, but then needs only 1-2 iterations on every successively refined mesh.

Improve this answer
$\endgroup$
4
$\begingroup$

I think it really depends on the condition number of the matrix A. If it has a large condition number, then perturbing the system ever-so-slightly may produce a radically different solution. For Adaptive FEM, it depends on what you expect the behavior of the system to be (and, obviously, the quality of the mesh itself). If you expect fairly smooth transition from the coarse to the fine grid, then we should expect the perturbed system to have a solution fairly close to the unperturbed system. If you can expect sudden dramatic changes, there is no real guarantee of the closeness of the perturbed and unperturbed systems.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Good way to think about this! There is some value to thinking about what $(A-\tilde{A})(f-\tilde{f})$ looks like too I think. $\endgroup$
    – meawoppl
    Mar 5, 2012 at 21:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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