Was sind die Unterschiede zwischen Parareal, PITA und PFASST?

10

Die Algorithmen Parareal, PITA und PFASST sind domänenübergreifende Techniken zur Parallelisierung der zeitabhängigen Lösung zeitlicher Probleme.

  1. Was sind die Leitprinzipien hinter diesen Methoden?

  2. Was sind die Hauptunterschiede zwischen ihnen?

  3. Kann ich sagen, dass einer auf einem anderen basiert? Wie?

  4. Was ist mit ihren Anwendungen?

Ich weiß, dass es keine Antwort auf die Frage "Was ist besser?" Gibt, aber ein gutes Verständnis der Anwendungsbereiche und Validierungsbedingungen ist für mich hilfreich.

eccstartup
quelle
1
Hallo eccstartup. Ich würde gerne die Unterschiede und Ähnlichkeiten zwischen den beiden Ansätzen kommentieren, aber ich denke, wir sollten die Frage zuerst ein wenig überarbeiten ...
Matthew Emmett
2
Für einen historischen Hintergrund über Parareal können Sie auch en.wikipedia.org/wiki/Parareal nachschlagen. Eine umfassende Liste von Referenzen finden Sie unter parallelintime.org/references/index.html
Daniel
Update auf der URL der Website: Sie kann jetzt unter www.parallel-in-time.org
Daniel

Antworten:

6

Diese Methoden können grob anhand von zwei Zeitschrittmethoden beschrieben werden, die hier mit und . Sowohl als auch verbreiten einen Anfangswert durch Annäherung der Lösung anGFGFUnu(tn)

u(t)=u0+0tf(τ,u(τ))dτ

von bis ( ). Damit die Verfahren effizient sind, muss der Propagator rechnerisch weniger teuer sein als der Propagator, und daher ist typischerweise ein Verfahren niedriger Ordnung. Da die Gesamtgenauigkeit der Verfahren durch die Genauigkeit des Propagators begrenzt ist, ist typischerweise von höherer Ordnung und kann zusätzlich einen kleineren Zeitschritt als . Aus diesen Gründen wird als Grobpropagator und als Feinpropagator bezeichnet.tntn+1u˙=f(u,t)GFGFFGGF

Das Parareal-Verfahren beginnt mit der Berechnung einer ersten Näherung für wobei die Anzahl der Zeitschritte unter Verwendung des Grobpropagators ist. Die Parareal-Methode fährt dann iterativ fort und wechselt zwischen der parallelen Berechnung von und einer Aktualisierung der Anfangsbedingungen bei jedem Prozessor des FormularsUn+10n=0N1NF(tn+1,tn,Unk)

Un+1k+1=G(tn+1,tn,Unk+1)+F(tn+1,tn,Unk)G(tn+1,tn,Unk)

für . Das heißt, der Feinpropagator wird verwendet, um die Lösung in jeder Zeitscheibe parallel zu verfeinern, während der Grobpropagator verwendet wird, um die vom Feinpropagator durchgeführten Verfeinerungen über die Zeit zu späteren Prozessoren zu propagieren. Beachten Sie, dass wir zu diesem Zeitpunkt noch nicht angegeben haben, was die und Propagatoren sind: Dies können beispielsweise Runge-Kutta-Schemata unterschiedlicher Reihenfolge sein.G F.n=0N1GF

Die PITA-Methode ist Parareal sehr ähnlich, verfolgt jedoch frühere Aktualisierungen und aktualisiert nur den Anfangszustand jedes Prozessors auf eine Weise, die an Krylov-Subraummethoden erinnert. Dies ermöglicht es PITA, lineare Gleichungen zweiter Ordnung zu lösen, die Parareal nicht kann.

Die PFASST-Methode unterscheidet sich von der Parareal- und der PITA-Methode in zwei grundlegenden Punkten: Erstens stützt sie sich auf das Zeitschrittschema der iterativen spektralen verzögerten Korrektur (DEZA) und zweitens enthält sie Korrekturen des vollständigen Approximationsschemas für den Grobpropagator und tatsächlich PFASST kann eine Hierarchie von Propagatoren verwenden (anstelle von nur zwei). Durch die Verwendung der DEZA können zeitparallele und DEZA-Iterationen hybridisiert werden, wodurch die Effizienzbeschränkungen von Parareal und PITA gelockert werden. Die Verwendung von FAS-Korrekturen ermöglicht eine große Flexibilität beim Aufbau der Grobpropagatoren von PFASST (wenn die Grobpropagatoren so billig wie möglich sind, kann die parallele Effizienz erhöht werden). Zu den Vergröberungsstrategien gehören: Zeitvergröberung (weniger DEZA-Knoten), Raumvergröberung (für gitterbasierte PDEs), Operatorvergröberung und reduzierte Physik.

Ich hoffe, dass dies die Grundlagen, Unterschiede und Ähnlichkeiten zwischen den Algorithmen umreißt. Weitere Informationen finden Sie in den Referenzen in diesem Beitrag .

In Bezug auf Anwendungen wurden die Methoden auf eine Vielzahl von Gleichungen angewendet (Planetenbahnen, Navier-Stokes, Partikelsysteme, chaotische Systeme, Strukturdynamik, atmosphärische Strömungen usw. usw.). Wenn Sie Zeitparallelisierung auf ein bestimmtes Problem anwenden, sollten Sie die Methode auf eine Weise validieren, die für das zu lösende Problem geeignet ist.

Matthew Emmett
quelle
Gute Antwort! Kannst du mir sagen was Full Approximation Schemebedeutet?
eccstartup