Jakie są różnice między Parareal, PITA i PFASST?

10

Algorytmy Parareal, PITA i PFASST są technikami obejmującymi całą domenę , służącymi do równoległego rozwiązywania problemów zależnych od czasu w czasie.

  1. Jakie są główne zasady tych metod?

  2. Jakie są główne różnice między nimi?

  3. Czy mogę powiedzieć, że jedna opiera się na innej? W jaki sposób?

  4. Co z ich aplikacjami?

Wiem, że nie będzie odpowiedzi na pytanie „co jest lepsze?”, Ale dobre zrozumienie obszarów ich zastosowania i warunków walidacji jest dla mnie pomocne.

eccstartup
źródło
1
Cześć eccstartup. Z przyjemnością skomentuję różnice i podobieństwa między tymi dwoma podejściami, ale myślę, że powinniśmy najpierw przerobić to pytanie ...
Matthew Emmett
2
Aby zapoznać się z historycznym tłem Parareal, możesz także zajrzeć na stronę en.wikipedia.org/wiki/Parareal Pełna lista referencji dostępna jest na stronie parallelintime.org/references/index.html
Daniel
Zaktualizuj adres URL witryny: można go teraz znaleźć na stronie www.parallel-in-time.org
Daniel

Odpowiedzi:

6

Metody te można ogólnie opisane w odniesieniu do dwóch metod czasowych stąpania, tutaj oznaczony przez i F . Zarówno G, jak i F propagują wartość początkową U nu ( t n ) , przybliżając rozwiązanie dosolfasolfaUnu(tn)

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

od do t n + 1 (tj ˙ U = K ( u , t ) ). Aby metody były skuteczne, musi być tak, że propagator G jest obliczeniowo tańszy niż propagator F , a zatem G jest zazwyczaj metodą niskiego rzędu. Ponieważ całkowita dokładność metody jest ograniczone przez dokładność F propagatora, M jest zazwyczaj wyższego rzędu, a ponadto można stosować mniejsze, niż w czasie etapu G . Z tych powodów Gtntn+1u˙=fa(u,t)solfasolfafasolsoljest określany jako gruby propagator, a drobny propagator.fa

Metoda Parareal rozpoczyna się od obliczenia pierwszego przybliżenia dla n = 0 N - 1, gdzie N jest liczbą kroków czasowych, z wykorzystaniem gruboziarnistego propagatora. Sposób Parareal następnie przebiega iteracyjnie, na przemian równolegle obliczania F ( t n + 1 , t n , U k n ) oraz zmiana warunków początkowych w każdym procesorze formieUn+10n=0N.-1N.fa(tn+1,tn,Unk)

Un+1k+1=sol(tn+1,tn,Unk+1)+fa(tn+1,tn,Unk)-sol(tn+1,tn,Unk)

n=0N.-1solfa

Metoda PITA jest bardzo podobna do Parareal, ale śledzi poprzednie aktualizacje i aktualizuje tylko stan początkowy na każdym procesorze w sposób przypominający metody podprzestrzeni Kryłowa. To pozwala PITA rozwiązać liniowe równania drugiego rzędu, których Parareal nie może.

Metoda PFASST różni się od metod Parareal i PITA na dwa podstawowe sposoby: po pierwsze, opiera się na iteracyjnym schemacie krokowym z przesunięciem w czasie Spectral Deferred Correction (SDC), a po drugie zawiera korekty schematu pełnej aproksymacji gruboziarnistego propagatora, aw rzeczywistości PFASST może korzystać z hierarchii propagatorów (zamiast tylko dwóch). Użycie SDC pozwala na hybrydyzację iteracji czasowo-równoległych i SDC, co rozluźnia ograniczenia wydajności Parareal i PITA. Korzystanie z poprawek FAS zapewnia dużą elastyczność przy konstruowaniu gruboziarnistych propagatorów PFASST (obniżenie grubości grubych propagatorów pomaga zwiększyć wydajność równoległą). Strategie zgrubienia obejmują: zgrubienie czasowe (mniej węzłów SDC), zgrubienie przestrzeni (dla PDE opartych na siatce), zgrubienie operatora i zmniejszoną fizykę.

Mam nadzieję, że to zarysuje podstawy, różnice i podobieństwa między algorytmami. Więcej informacji można znaleźć w referencjach w tym poście .

Jeśli chodzi o zastosowania, metody zostały zastosowane do wielu różnych równań (orbit planetarnych, Naviera-Stokesa, układów cząstek, układów chaotycznych, dynamiki strukturalnej, przepływów atmosferycznych itp.). Stosując równoległość czasową do danego problemu, z pewnością powinieneś zweryfikować metodę w sposób odpowiedni do rozwiązania problemu.

Matthew Emmett
źródło
Dobra odpowiedź! Czy możesz mi powiedzieć, co Full Approximation Schemeto znaczy?
eccstartup