Dans quels cas d'application les schémas de préconditionnement additif sont-ils supérieurs aux schémas multiplicatifs?

12

Dans les deux méthodes de décomposition de domaine (DD) et multigrille (MG), on peut composer l'application des mises à jour de bloc ou des corrections grossières comme additive ou multiplicative . Pour les solveurs ponctuels, c'est la différence entre les itérations de Jacobi et de Gauss-Seidel. Le lisseur multiplicatif pour agissant comme est appliqué comme $Ax = b$ $S(x^{old}, b) = x^{new}$

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

et l'additif plus lisse est appliqué comme

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

pour un certain amortissement . Le consensus général semble être que les lisseurs multiplicatifs ont des propriétés de convergence beaucoup plus rapides, mais je me demandais: dans quelles situations les performances des variantes additives de ces algorithmes sont-elles meilleures? $\lambda_i$

Plus précisément, quelqu'un a-t-il des cas d'utilisation dans lesquels la variante additive devrait et / ou fonctionne bien mieux que la variante multiplicative? Y a-t-il des raisons théoriques à cela? La plupart de la littérature sur les multigrilles est assez pessimiste à propos de la méthode Additive, mais elle est tellement utilisée dans le contexte DD que l'additif Schwarz. Cela s'étend également à la question beaucoup plus générale de la composition de solveurs linéaires et non linéaires, et quel type de constructions fonctionnera bien et fonctionnera bien en parallèle.

linear-algebra performance multigrid domain-decomposition Peter Brune
la source

6

Les méthodes additives exposent plus de simultanéité. Ils ne sont généralement plus rapides que les méthodes multiplicatives si vous pouvez utiliser cette concurrence. Par exemple, les niveaux grossiers de multigrilles sont généralement limités en latence. Si vous déplacez des niveaux grossiers vers des sous-communicateurs plus petits, ils pourraient être résolus indépendamment des niveaux plus fins. Avec un schéma multiplicatif, tous les procs doivent attendre pendant que les niveaux grossiers sont résolus.

De plus, si l'algorithme a besoin de réductions à tous les niveaux, la variante additive peut être capable de les fusionner là où la méthode multiplicative est forcée de les exécuter séquentiellement.

Jed Brown
la source

C'est la réponse que je pensais obtenir, donc je suppose que j'irai encore plus loin avec la question. Existe-t-il des situations où les méthodes appliquées additivement, y compris DD et MG, mais aussi le découpage sur le terrain (qui peut être considéré comme DD mais peut avoir des caractéristiques différentes dans la pratique) ou le fractionnement PDE est en fait meilleur en termes de performances, de robustesse ou de stabilité que la variante multiplicative?

Peter Brune

1

Les versions multiplicatives de nombreux algorithmes doivent stocker plus d'informations, mais convergent parfois à peu près aussi rapidement. Parfois, les variantes additives sont symétriques, mais il peut être beaucoup plus difficile de créer une symétrie multiplicative. Avec fieldsplit, le préconditionneur peut devenir plus approximatif lorsque vous ajoutez ces résolutions supplémentaires. Nous pouvons le démontrer avec un exemple PETSc Stokes si vous le souhaitez. L'additif est toujours plus facile à vectoriser / plus simultané, mais tout gain de performance est spécifique au problème et à l'architecture.

Jed Brown

5

Pour les problèmes de SPD, les méthodes additives sont meilleures pour le lissage MG pour plusieurs raisons, comme déjà mentionné et quelques autres:

@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} }

Les méthodes multiplicatives ont cependant les propriétés spectrales correctes dès le départ pour un MG plus lisse, c'est-à-dire qu'elles n'ont pas besoin d'amortissement. Cela peut être une grande victoire pour les problèmes hyperboliques où le lissage polynomial n'est pas très agréable.

Adams
la source

0

Je vais répéter ce que @Jed a dit: La méthode multiplicative converge toujours au moins aussi bien que la méthode additive (asymptotiquement), donc vous ne gagnez qu'en fonction de la concurrence, mais cela dépend de l'architecture.

Matt Knepley
la source

Pas techniquement correct, les spectres de la matrice d'itération de Gauss-Seidel, par exemple, ne sont pas uniformément supérieurs à Jacobi (par exemple, une valeur propre est tuée avec une itération de Jacobi). Mark (comment puis-je me déconnecter en tant que Jed ...)

Jed Brown

Dans quels cas d'application les schémas de préconditionnement additif sont-ils supérieurs aux schémas multiplicatifs?

Réponses: