In welchen Anwendungsfällen sind additive Vorkonditionierungsschemata multiplikativen überlegen?

12

Sowohl bei der Domänenzerlegung (DD) als auch bei der Multigrid-Methode (MG) kann man die Anwendung der Blockaktualisierungen oder der Grobkorrekturen entweder additiv oder multiplikativ zusammenstellen . Für Punktlöser ist dies der Unterschied zwischen der Jacobi- und der Gauß-Seidel-Iteration. Die multiplikative glattere für , die als so angewendet wird $Ax = b$ $S(x^{old}, b) = x^{new}$

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

und der additive Glätter wird als aufgetragen

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

für eine gewisse Dämpfung . Der allgemeine Konsens scheint zu sein, dass multiplikative Glätter viel schnellere Konvergenzeigenschaften haben, aber ich habe mich gefragt: Unter welchen Umständen ist die Leistung der additiven Varianten dieser Algorithmen besser? $\lambda_i$

Konkret: Gibt es Anwendungsfälle, in denen die additive Variante eine deutlich bessere Leistung als die multiplikative Variante erbringen sollte und / oder erbringt? Gibt es dafür theoretische Gründe? Die meiste Literatur zu Multigrid ist ziemlich pessimistisch in Bezug auf die Additivmethode, wird jedoch im DD-Kontext so häufig als Additiv Schwarz verwendet. Dies erstreckt sich auch auf das viel allgemeinere Problem der Erstellung linearer und nichtlinearer Löser und darauf, welche Konstruktionsarten eine gute Leistung erbringen und welche parallel.

linear-algebra performance multigrid domain-decomposition Peter Brune
quelle

6

Additive Methoden stellen mehr Parallelität zur Verfügung. Sie sind im Allgemeinen nur dann schneller als multiplikative Methoden, wenn Sie diese Parallelität verwenden können. Grobe Multigrid-Werte sind beispielsweise in der Regel latenzbegrenzt. Wenn Sie grobe Ebenen auf kleinere Subkommunikatoren verschieben, können diese unabhängig von den feineren Ebenen gelöst werden. Bei einem multiplikativen Schema müssen alle Prozesse warten, bis die groben Ebenen gelöst sind.

Wenn der Algorithmus Reduktionen auf jeder Ebene benötigt, kann die additive Variante sie möglicherweise zusammenführen, wenn die multiplikative Methode gezwungen ist, sie sequentiell auszuführen.

Jed Brown
quelle

Dies ist die Antwort, die ich erwartet hatte, also gehe ich mit der Frage wahrscheinlich noch weiter. Gibt es Situationen, in denen additiv angewandte Methoden wie DD und MG, aber auch Feldaufteilung (die als DD-ähnlich angesehen werden kann, aber in der Praxis unterschiedliche Eigenschaften aufweist) oder PDE-Aufteilung in Bezug auf Leistung, Robustheit oder Stabilität tatsächlich besser sind als die multiplikative Variante?

Peter Brune

1

Multiplikative Versionen vieler Algorithmen müssen mehr Informationen speichern, konvergieren jedoch manchmal ungefähr so schnell. Manchmal sind additive Varianten symmetrisch, aber es kann viel aufwändiger sein, multiplikative symmetrisch zu machen. Bei der Feldaufteilung kann der Vorkonditionierer näherungsweise werden, wenn Sie diese zusätzlichen Lösungen hinzufügen. Wenn Sie möchten, können wir dies anhand eines PETSc Stokes-Beispiels demonstrieren. Additiv ist immer einfacher zu vektorisieren / paralleler, aber jeder Leistungsgewinn ist problem- und architekturspezifisch.

Jed Brown

5

Bei SPD-Problemen sind additive Methoden aus mehreren Gründen besser für die MG-Glättung, wie bereits erwähnt, und aus einigen weiteren Gründen:

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

Multiplikative Methoden haben jedoch die richtigen spektralen Eigenschaften, die für einen MG-Glatter sofort verfügbar sind, dh, sie müssen nicht gedämpft werden. Dies kann ein großer Gewinn für hyperbolische Probleme sein, bei denen das Glätten von Polynomen nicht sehr schön ist.

Adams
quelle

0

Ich werde noch einmal wiederholen, was @Jed gesagt hat: Die multiplikative Methode konvergiert immer mindestens so gut wie die additive Methode (asymptotisch), sodass Sie nur auf der Grundlage der Parallelität gewinnen, was jedoch von der Architektur abhängt.

Matt Knepley
quelle

Nicht technisch korrekt, die Spektren der Iterationsmatrix für Gauß-Seidel sind Jacobi nicht einheitlich überlegen (z. B. wird ein Eigenwert mit einer Jacobi-Iteration getötet). Mark (wie melde ich mich als Jed ab ...)

Jed Brown

In welchen Anwendungsfällen sind additive Vorkonditionierungsschemata multiplikativen überlegen?

Antworten: