14
$\begingroup$

Multigrid methods usually solve Dirichlet problems on levels (e.g. point Jacobi or Gauss-Seidel). When using continuous finite element methods, it is much less expensive to assemble small Neumann problems than to assemble small Dirichlet problems. Non-overlapping domain decomposition methods such as BDDC (like FETI-DP) can be interpreted as multigrid methods that solve "pinned" Neumann problems on levels. Unfortunately, the condition number for multilevel BDDC scales as

$$C \left(1 + \log \left(\frac{H}{h}\right)\right)^{2L}$$

where $L$ is the number of levels and $H/h$ is the coarsening ratio. In contrast, the condition number for multigrid methods with smoothers based on Dirichlet problems have a condition number independent of the number of levels.

Is there a way to solve "pinned" Neumann problems without losing level-independence?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Note: this is an open research question, posted here as a challenge because it is practical concern that seems to be overlooked by many of the analysts working in this area. $\endgroup$ – Jed Brown Dec 1 '11 at 2:26
  • $\begingroup$ It's hard to say what exactly the equivalent to the "Pinned Neumann" block smoother in a multigrid context is, at least if you expect it to take the same role that it does in the DD context. Could you elaborate on any inklings you might have of what this would be? $\endgroup$ – Peter Brune Dec 7 '11 at 20:27
2
$\begingroup$

I'm not sure how different this is from BDDC, and it's not very thoroughly analyzed, but this seemed interesting when I read it before:

A parallel multigrid Poisson solver for fluids simulation on large grids

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ This paper uses finite difference methods, for which it is natural to construct local Dirichlet problems. They use a damped Jacobi smoother (single-point Dirichlet problems). It is low-memory (common for this class of methods) and uses a staggered grid interpolation (not typical). It might be a fine paper (I didn't read it carefully), but it is inconsequential to this question. $\endgroup$ – Jed Brown Dec 2 '11 at 12:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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