13
$\begingroup$

In both domain decomposition (DD) and multigrid (MG) methods, one may compose the application of the block updates or coarse corrections as either additive or multiplicative. For pointwise solvers, this is the difference between the Jacobi and Gauss-Seidel iterations. The multiplicative smoother for $Ax = b$ acting as $S(x^{old}, b) = x^{new}$ is applied as

$ x_{i+1} = S_n(S_{n-1}( ..., S_1(x_i, b) ..., b), b) $

and the additive smoother is applied as

$ x_{i+1} = x_{i} + \displaystyle\sum_{\ell = 0}^{n}\lambda_\ell(S_\ell(x_i, b) - x_i) $

for some damping $\lambda_i$. The general consensus appears to be that multiplicative smoothers have much more rapid convergence properties, but I was wondering: under what situations is the performance of the additive variants of these algorithms better?

More specifically, Does anyone have any use cases where the additive variant should and/or does perform significantly better than the multiplicative variant? Are there theoretical reasons for this? Most literature on multigrid is fairly pessimistic about the Additive method, but it's used so much in the DD context as additive Schwarz. This also extends to the much more general issue of composing linear and nonlinear solvers, and which type of constructions will perform well and perform well in parallel.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
6
$\begingroup$

Additive methods expose more concurrency. They are generally only faster than multiplicative methods if you can use that concurrency. For example, coarse levels of multigrid are typically latency-limited. If you move coarse levels to smaller subcommunicators, then they could be solved independently from the finer levels. With a multiplicative scheme, all the procs have to wait while the coarse levels are solved.

Also, if the algorithm needs reductions on every level, the additive variant may be able to coalesce them where as the multiplicative method is forced to perform them sequentially.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is the answer I figured that I'd get, so I guess that I'll go even further with the question. Are there situations where additively applied methods including DD and MG, but also fieldsplitting (which may be considered DD-like but may have different characteristics in practice) or PDE splitting is actually better in terms of performance, robustness or stability than the multiplicative variant? $\endgroup$
    – Peter Brune
    Commented Dec 8, 2011 at 16:18
  • 1
    $\begingroup$ Multiplicative versions of many algorithms need to store more information, but sometimes converge roughly as fast. Sometimes additive variants are symmetric, but it may be much more work to make multiplicative symmetric. With fieldsplit, the preconditioner can become more approximate when you add those extra solves. We can demonstrate this with a PETSc Stokes example if you like. Additive is always easier to vectorize/more concurrent, but any performance win from that is problem- and architecture-specific. $\endgroup$
    – Jed Brown
    Commented Dec 9, 2011 at 2:39
5
$\begingroup$

For SPD problems additive methods are better for MG smoothing for several reasons as mentioned already and a few more: 

@Article{Adams-02, 
author = {Adams, M.~F. and Brezina, M. and Hu, J. J. and Tuminaro, R. S.}, 
title = {Parallel multigrid smoothing: polynomial versus {G}auss-{S}eidel}, 
journal = {J. Comp. Phys.}, 
year = {2003}, 
volume = {188}, 
number = {2}, 
pages = {593-610} }

Multiplicative methods do however have the correct spectral properties straight-out-of-the-box for an MG smoother, that is, they do not need damping. This can be a big win for hyperbolic problems where polynomial smoothing is not very nice.

Improve this answer
$\endgroup$
0
$\begingroup$

I will restate what @Jed said: The Multiplicative method always converges at least as well as the Additive method (asymptotically), so you only win based on concurrency, but that is architecture-dependent.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Not technically correct, the spectra of the iteration matrix for say Gauss-Seidel is not uniformly superior to Jacobi (eg, one eigenvalue gets killed with one Jacobi iteration). Mark (how do I log off as Jed...) $\endgroup$
    – Jed Brown
    Commented Dec 11, 2011 at 15:37

Your Answer

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

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