13
$\begingroup$

I just read Chapter 3 in "A Multigrid Tutorial" by Briggs/Henson/McCormick, link.

The text is about Multigrid cycles such as V-cycle, mu-cycle, FMG. What caught my eye: In most iterative procedures one checks whether it has converged to the desired tolerance/accuracy and if so, the procedure stops. But Briggs/Henson/McCormick do not use any convergence checking in the presented schemes. The number of iterations and recursions are just hardcoded and one has to trust that the scheme will converge.

So how is this done in Multigrid normally? Is it usual that the number of iterations/recursions is just hardcoded? I really fear that I will either waste a lot of computation time because I'm over-precise or on the other hand, accuracy will be poor in many cases when I choose a lower number of iterations/recursions.

Improve this question
$\endgroup$
2
  • $\begingroup$ The lack of answers to this question is really surprising to me. Surely there are some very active users here who have quite a bit of multigrid experience in research and/or production environments? $\endgroup$
    – Doug Lipinski
    Sep 15, 2015 at 0:31
  • 2
    $\begingroup$ I think the problem is that multigrid nowadays is rarely used as a solver by itself (due to the lack of general convergence theory, I believe), but rather as a preconditioner for a more established iterative method such as CG or GMRES. In this context, no convergence check for multigrid is necessary, since the outer iteration takes care of it. $\endgroup$
    – Christian Clason
    Sep 15, 2015 at 8:19

3 Answers 3

Reset to default
5
$\begingroup$

Yes, it is normal to have no convergence checks in MG for a few reasons. First, if you use a different number of iterates on each pass, then the MG operator is no longer linear, and you would have to use something like FGMRES as an accelerator which can accommodate a nonlinear preconditioner. Second, FMG is an exact solver (reduces error below discretization error) when it works, so checking convergence introduces costly synchronization into the algorithm. You would generally check at the end just to verify convergence.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Do you have any sources to back this up? Currently your answer and the other top voted answer directly contradict each other. $\endgroup$
    – Doug Lipinski
    Sep 18, 2015 at 23:57
  • 1
    $\begingroup$ 1) Saad's book is the best reference for using FGMRES to accommodate a changing preconditioner: www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf 2) I believe the proof that FMG reduces error below discretization error with a sufficiently powerful V-cycle is in Trottenberg and Osterlee, but I reproduce the proof in my book: cse.buffalo.edu/~knepley/classes/caam519/CSBook.pdf $\endgroup$
    – Matt Knepley
    Sep 17, 2018 at 1:01
4
$\begingroup$

Definitely not. To pick one example, the book Multigrid has a plot on page 53 (Figure 2.10) that shows the decrease in the residual as a function of the number of V or W cycles. You would stop cycling when you are satisfied with the size of the residual.

The source of your confusion may be because some descriptions only describe a single V-cycle. In some limited cases, because multigrid is such a powerful technique, this may generate a suitable solution. Also, multigrid can be used as a preconditioner. In that case, the multigrid is just an accelerator, and the check for convergence happens at a higher level. But the check should always happen somewhere.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Do you have any sources to back this up? Currently your answer and the other top voted answer directly contradict each other. $\endgroup$
    – Doug Lipinski
    Sep 18, 2015 at 23:57
1
$\begingroup$

In Multigrid used as a solver, usually the relative norm of the residual is used as the stopping criterion. As you decrease this ratio - the accuracy of the solution should increase. Further, at the coarsest level researchers do different things :

  1. either solve using a direct solver (no convergence)
  2. use fixed iterations (no convergence)
  3. use the successive difference between iterations as convergence criterion (not a good method because you could be far away from the solution)
  4. Again use relative norm of residual as a stopping criterion.

Method 2 listed above at the coarsest level is good when Multigrid is used as a Pre-conditioner (Multigrid experts here can comment - I am a beginner).

So, in general convergence is used.

Improve this answer
$\endgroup$

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.