¿Cuál es el estado del arte en los métodos paralelos de EDO?

Actualmente estoy buscando métodos paralelos para la integración de ODE. Existe una gran cantidad de literatura nueva y antigua que describe una amplia gama de enfoques, pero no he encontrado encuestas recientes ni artículos de descripción general que describan el tema en general.

Existe el libro de Burrage [1], pero tiene casi 20 años y, por lo tanto, no cubre muchas de las ideas más modernas, como el algoritmo parareal.

[1] K. Burrage, métodos paralelos y secuenciales para ecuaciones diferenciales ordinarias, Clarendon Press, Oxford, 1995

No conozco ningún artículo de resumen reciente, pero participo activamente en el desarrollo del algoritmo PFASST, por lo que puedo compartir algunas ideas.

Hay tres clases amplias de técnicas paralelas en el tiempo que conozco:

• a través del método: se pueden evaluar en paralelo etapas independientes de RK o integradores de extrapolación; ver también el RIDC (algoritmo de corrección diferida integral revisionista)
• a través del problema: relajación de la forma de onda
• a través del dominio del tiempo - Parareal; PITA (algoritmo paralelo en el tiempo); y PFASST (esquema de aproximación completa paralela en espacio y tiempo).

Los métodos que se paralelizan a través del método generalmente funcionan muy cerca de las especificaciones pero no escalan más allá de un puñado de procesadores (de tiempo). Por lo general, son relativamente más fáciles de implementar que otros métodos y son buenos si tiene algunos núcleos adicionales y está buscando aceleraciones modestas y predecibles.

Los métodos que se paralelizan en el dominio del tiempo incluyen Parareal, PITA, PFASST. Todos estos métodos son iterativos y se componen de propagadores "gruesos" económicos (pero imprecisos) y propagadores "finos" caros (pero precisos). Alcanzan la eficiencia paralela evaluando iterativamente el propagador fino en paralelo para mejorar una solución en serie obtenida usando el propagador grueso.

Los algoritmos Parareal y PITA sufren de un límite superior bastante desafortunado en su eficiencia paralela : donde es el número de iteraciones requeridas para obtener la convergencia en todo el dominio. Por ejemplo, si su implementación de Parareal requirió 10 iteraciones para converger y está utilizando 100 procesadores (de tiempo), la mayor aceleración que podría esperar sería 10x. El algoritmo PFASST relaja este límite superior mediante la hibridación de las iteraciones paralelas en el tiempo con las iteraciones del método paso a paso Corrección espectral diferida e incorpora las correcciones del esquema de aproximación completa a una jerarquía de discretizaciones espacio / tiempo.E < 1 / K $E$$E < 1/K$$K$

Se pueden jugar muchos juegos con todos estos métodos para tratar de acelerarlos, y parece que el rendimiento de estas técnicas en todo el dominio depende de qué problema está resolviendo y qué técnicas están disponibles para acelerar lo burdo propagador (cuadrículas gruesas, operadores gruesos, física gruesa, etc.).

Algunas referencias (ver también referencias enumeradas en los documentos):

• Este documento demuestra cómo varios métodos pueden ser paralelizados a través del método: una comparación teórica de los métodos explícitos de alto orden Runge-Kutta, extrapolación y corrección diferida ; Ketcheson y Waheed.

• Este documento también muestra una buena manera de paralelizar el método e introduce el algoritmo RIDC: integradores paralelos de alto orden ; Christlieb, MacDonald, Ong.

• Este artículo presenta el algoritmo PITA: un método implícito paralelo al tiempo para acelerar la solución de problemas de dinámica estructural no lineal ; Cortial y Farhat.

• Hay muchos documentos sobre Parareal (solo Google).

• Aquí hay un documento sobre el método de Nievergelt: un enfoque de comunicación mínima para la integración de tiempo paralelo ; Pregonero.

• Este artículo presenta PFASST: Hacia un método eficiente en paralelo en el tiempo para ecuaciones diferenciales parciales ; Emmett y Minion;

• Este documento describe una aplicación ordenada de PFASST: un solucionador de N-cuerpo paralelo masivo espacio-temporal ; Speck, Ruprecht, Krause, Emmett, Minion, Windel, Gibbon.

He escrito dos implementaciones de PFASST que están disponibles en la red: PyPFASST y libpfasst .

Aunque esta publicación tiene ahora dos años, en caso de que alguien se encuentre con ella, permítanme hacer una breve actualización:

Martin Gander recientemente escribió un buen artículo de revisión, que brinda una perspectiva histórica en el campo y discute muchos métodos PINT diferentes: http://www.unige.ch/~gander/Preprints/50YearsTimeParallel.pdf

Ahora también hay un sitio web de la comunidad que enumera muchas referencias y ofrece descripciones de diferentes métodos: http://www.parallel-in-time.org/

Aquí se puede encontrar una discusión sobre el algoritmo Parareal paralelo en el tiempo: https://en.wikipedia.org/wiki/Parareal

Aquí hay una breve introducción a la relajación de la forma de onda . Cuando se habla del método paralelo al tiempo como parareal o PITA u otros métodos, se debe distinguir entre los sistemas ODE disipativos y conservadores (hamiltonianos). Esto último parece más difícil de paralelizar en la dimensión del tiempo mediante la división en subintervalos de tiempo. Aquí hay un análisis de lo parareal para los sistemas hamiltonianos . El sistema disipativo es más fácil porque el error causado en el momento inicial tiende a desaparecer debido a la disipación u ( t ) = exp ( - λ t ) u 0 , R $u_0$$u(t)=\exp(-\lambda t)u_0,$ $\mathrm{Re}\,\lambda>0.$