Jaki jest stan techniki w równoległych metodach ODE?

Obecnie szukam równoległych metod integracji ODE. Istnieje wiele nowej i starej literatury opisującej szeroki wachlarz podejść, ale nie znalazłem żadnych ostatnich badań ani artykułów przeglądowych opisujących ogólnie ten temat.

Jest książka Burrage [1], ale ma ona prawie 20 lat i dlatego nie obejmuje wielu bardziej nowoczesnych pomysłów, takich jak algorytm pomocniczy.

[1] K. Burrage, równoległe i sekwencyjne metody dla równań różniczkowych zwyczajnych, Clarendon Press, Oxford, 1995

Nie znam żadnych ostatnich artykułów przeglądowych, ale jestem aktywnie zaangażowany w rozwój algorytmu PFASST, więc mogę podzielić się przemyśleniami.

Istnieją trzy szerokie klasy technik równoległych w czasie, o których wiem:

• w całej metodzie - niezależne etapy RK lub integratorów ekstrapolacji mogą być oceniane równolegle; patrz także RIDC (rewizjonistyczny zintegrowany algorytm odroczonej korekty)
• przez problem - relaksacja kształtu fali
• w dziedzinie czasu - Parareal; PITA (algorytm równoległy w czasie); i PFASST (równoległy pełny schemat aproksymacji w przestrzeni i czasie).

Metody równoległe w całej metodzie zwykle działają bardzo blisko specyfikacji, ale nie skalują się poza garść procesorów (czasowych). Zazwyczaj są one stosunkowo łatwiejsze do wdrożenia niż inne metody i są dobre, jeśli masz kilka dodatkowych rdzeni i szukasz przewidywalnych i skromnych przyspieszeń.

Metody równoległe w dziedzinie czasu obejmują Parareal, PITA, PFASST. Wszystkie te metody są iteracyjne i składają się z niedrogich (ale niedokładnych) „grubych” propagatorów i drogich (ale dokładnych) „drobnych” propagatorów. Osiągają wydajność równoległą poprzez iteracyjną ocenę równoległego drobnego propagatora w celu ulepszenia rozwiązania szeregowego uzyskanego przy użyciu grubego propagatora.

$E$$E < 1/K$$K$

Wiele gier można odtwarzać przy użyciu wszystkich tych metod, aby spróbować je przyspieszyć, i wydaje się, że wydajność tych technik w całej domenie zależy od tego, jaki problem rozwiązujesz i jakie techniki są dostępne, aby przyspieszyć zgrubienie propagator (zgrubne siatki, zgrubne operatory, zgrubna fizyka itp.).

Niektóre referencje (patrz także referencje wymienione w artykułach):

• W tym artykule pokazano, w jaki sposób można sparaliżować różne metody: Teoretyczne porównanie jawnych metod Runge-Kutty wyższego rzędu, ekstrapolacji i metod odroczonej korekty ; Ketcheson i Waheed.

• W tym artykule pokazano także przyjemny sposób równoległego łączenia metod i przedstawiono algorytm RIDC: Równoległe integratory wysokiego rzędu ; Christlieb, MacDonald, Ong.

• W artykule przedstawiono algorytm PITA: niejawna metoda czasowo-równoległa przyspieszająca rozwiązanie problemów nieliniowej dynamiki strukturalnej ; Cortial i Farhat.

• Na Parareal jest wiele artykułów (tylko Google it).

• Oto artykuł na temat metody Nievergelt: Minimalne podejście komunikacyjne do całkowania w czasie równoległym ; Szczekacz.

• W pracy przedstawiono PFASST: W kierunku wydajnej metody równoległej w czasie dla równań różniczkowych cząstkowych ; Emmett i stronnik;

• W tym artykule opisano zgrabne zastosowanie PFASST: masywnie czasoprzestrzennego solwera N-ciała ; Speck, Ruprecht, Krause, Emmett, Minion, Windel, Gibbon.

Napisałem dwie implementacje PFASST, które są dostępne w sieci: PyPFASST i libpfasst .

Chociaż ten post ma teraz dwa lata, na wypadek, gdyby ktoś się na nim natknął, dam krótką aktualizację:

Martin Gander napisał ostatnio fajny artykuł przeglądowy, który przedstawia historyczną perspektywę w tej dziedzinie i omawia wiele różnych metod PINT: http://www.unige.ch/~gander/Preprints/50YearsTimeParallel.pdf

Jest teraz także strona społeczności, która zawiera bardzo wiele referencji i zawiera opisy różnych metod: http://www.parallel-in-time.org/

Omówienie algorytmu Parareal równolegle w czasie można znaleźć tutaj: https://en.wikipedia.org/wiki/Parareal

$u_0$$u(t)=\exp(-\lambda t)u_0,$ $\mathrm{Re}\,\lambda>0.$