Quel est l'état de l'art dans les méthodes ODE parallèles?

Je suis actuellement à la recherche de méthodes parallèles d'intégration ODE. Il existe de nombreux ouvrages anciens et anciens décrivant un large éventail d'approches, mais je n'ai trouvé aucun sondage récent ni article récapitulatif décrivant le sujet en général.

Il y a le livre de Burrage [1], mais il a presque 20 ans et ne couvre donc pas beaucoup des idées les plus modernes comme l'algorithme de Parareal.

[1] K. Burrage, méthodes parallèle et séquentielle pour les équations différentielles ordinaires, Clarendon Press, Oxford, 1995.

Je ne connais aucun article de synthèse récent, mais je participe activement au développement de l'algorithme PFASST afin de pouvoir partager quelques réflexions.

Je connais trois grandes classes de techniques parallèles dans le temps:

• à travers la méthode - les étapes indépendantes de la RK ou des intégrateurs d'extrapolation peuvent être évaluées en parallèle; voir aussi le RIDC (algorithme de correction différée intégrale révisionniste)
• à travers le problème - relaxation de forme d'onde
• dans le domaine temporel - Parareal; PITA (algorithme parallèle dans le temps); et PFASST (schéma d’approximation complète parallèle dans l’espace et le temps).

Les méthodes parallélisées d'une méthode à l'autre fonctionnent généralement très près des spécifications mais n'évoluent pas au-delà d'une poignée de processeurs (temporels). Généralement, elles sont relativement plus faciles à mettre en œuvre que d’autres méthodes et sont utiles si vous avez quelques noyaux supplémentaires et que vous recherchez des accélérations prévisibles et modestes.

Les méthodes parallèles dans le domaine temporel comprennent Parareal, PITA, PFASST. Ces méthodes sont toutes itératives et comprennent des propagateurs "grossiers" peu coûteux (mais inexacts) et des propagateurs "fins" coûteux (mais précis). Ils obtiennent une efficacité parallèle en évaluant de manière itérative le propagateur fin en parallèle afin d'améliorer une solution en série obtenue à l'aide du propagateur grossier.

Les algorithmes de Parareal et de PITA présentent une limite supérieure assez malheureuse quant à leur efficacité parallèle : où est le nombre d'itérations nécessaires pour obtenir la convergence dans tout le domaine. Par exemple, si votre mise en œuvre Parareal a nécessité 10 itérations pour converger et que vous utilisez 100 processeurs (temporisés), l'accélération la plus grande que vous puissiez espérer serait 10x. L'algorithme PFASST assouplit cette limite supérieure en hybridant les itérations parallèles dans le temps avec les itérations de la méthode de progression temporelle à correction différée spectrale et en incorporant les corrections du schéma d'approximation complet à une hiérarchie des discrétisations spatio-temporelles.$E$$E < 1/K$$K$

On peut jouer à de nombreux jeux avec toutes ces méthodes pour essayer de les accélérer, et il semble que la performance de ces techniques à travers le domaine dépende du problème que vous résolvez et des techniques disponibles pour accélérer le traitement grossier. propagateur (réseaux grossiers, opérateurs grossiers, physique grossière, etc.).

Quelques références (voir aussi les références listées dans les articles):

• Cet article montre comment différentes méthodes peuvent être mises en parallèle sur l'ensemble de la méthode: une comparaison théorique des méthodes de Runge-Kutta explicites d'ordre élevé, d'extrapolation et de correction différée ; Ketcheson et Waheed.

• Cet article montre également un moyen intéressant de mettre en parallèle la méthode et présente l’algorithme RIDC: Intégrateurs parallèles d’ordre élevé ; Christlieb, MacDonald, Ong.

• Cet article présente l’algorithme PITA: une méthode implicite temporelle parallèle pour accélérer la résolution des problèmes de dynamique structurale non linéaire ; Cortial et Farhat.

• Il y a beaucoup de papiers sur Parareal (juste sur Google).

• Voici un article sur la méthode de Nievergelt: Une approche de communication minimale pour l’intégration de temps parallèle ; Aboyeur.

• Ce document présente PFASST: Vers une méthode efficace du parallèle dans le temps pour les équations aux dérivées partielles ; Emmett et Minion;

• Cet article décrit une application ordonnée de PFASST: un résolveur N-corps parallèle très volumineux dans l’ espace-temps ; Speck, Ruprecht, Krause, Emmett, Minion, Windel, Gibbon.

J'ai écrit deux implémentations de PFASST qui sont disponibles sur le net: PyPFASST et libpfasst .

Bien que ce message date maintenant de deux ans, au cas où quelqu'un tomberait dessus, laissez-moi vous donner une brève mise à jour:

Martin Gander a récemment écrit un bel article de synthèse qui donne une perspective historique sur le terrain et traite de nombreuses méthodes PINT différentes: http://www.unige.ch/~gander/Preprints/50YearsTimeParallel.pdf

Il existe maintenant aussi un site Web communautaire qui répertorie de très nombreuses références et décrit différentes méthodes: http://www.parallel-in-time.org/

Une discussion de l'algorithme parallèle dans le temps de Parareal en particulier peut être trouvée ici: https://en.wikipedia.org/wiki/Parareal

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