¿Cuáles son las diferencias entre Parareal, PITA y PFASST?

Los algoritmos Parareal, PITA y PFASST son todos técnicas de todo el dominio para paralelizar la solución de problemas dependientes del tiempo en el tiempo.

1. ¿Cuáles son los principios rectores detrás de estos métodos?

2. ¿Cuáles son las principales diferencias entre ellos?

3. ¿Puedo decir que uno está basado en otro? ¿Cómo?

4. ¿Qué pasa con sus aplicaciones?

Sé que no habrá respuesta a la pregunta "¿cuál es mejor?", Pero una buena comprensión de sus áreas de aplicación y condiciones de validación es útil para mí.

Estos métodos se pueden describir más o menos en términos de dos métodos de tiempo-escalonamiento, denotadas aquí por y F . Tanto G como F propagan un valor inicial U n ≈ u ( t n ) al aproximar la solución a$G$$F$$G$$F$$U_n \approx u(t_n)$

$$u(t) = u_0 + \int_0^t f(\tau,u(\tau)) \,d\tau$$

de a t n + 1 (es decir, ˙ u = f ( u , t ) ). Para que los métodos sean eficientes, debe darse el caso de que el propagador G sea ​​computacionalmente menos costoso que el propagador F y, por lo tanto, G es típicamente un método de bajo orden. Puesto que la precisión global de los métodos está limitado por la precisión de la F propagador, F es típicamente de orden superior y, además, puede utilizar un paso de tiempo menor que G . Por estas razones, $t_n$$t_{n+1}$$\dot{u} = f(u,t)$$G$$F$$G$$F$$F$$G$$G$se denomina propagador grueso y propagador fino.$F$

El método Parareal comienza calculando una primera aproximación para n = 0 ... N - 1 donde N es el número de pasos de tiempo, utilizando el propagador grueso. Luego, el método Parareal procede de forma iterativa, alternando entre el cálculo paralelo de F ( t n + 1 , t n , U k n ) y una actualización de las condiciones iniciales en cada procesador de la forma$U_{n+1}^0$$n = 0 \ldots N-1$$N$$F(t_{n+1},t_n,U_n^k)$

$$U_{n+1}^{k+1} = G(t_{n+1}, t_n, U_n^{k+1}) + F(t_{n+1}, t_n, U_n^k) - G(t_{n+1}, t_n, U_n^{k})$$

$n = 0 \ldots N-1$$G$$F$ son los propagadores : podrían ser, por ejemplo, esquemas Runge-Kutta de orden variable.

El método PITA es muy similar a Parareal, pero realiza un seguimiento de las actualizaciones anteriores y solo actualiza la condición inicial en cada procesador de una manera que recuerda los métodos del subespacio de Krylov. Esto le permite a PITA resolver ecuaciones lineales de segundo orden que Parareal no puede.

El método PFASST difiere de los métodos Parareal y PITA en dos formas fundamentales: primero, se basa en el esquema iterativo de tiempo de corrección espectral diferido (SDC), y en segundo lugar incorpora correcciones de esquema de aproximación completa al propagador grueso, y de hecho PFASST puede usar una jerarquía de propagadores (en lugar de solo dos). El uso de SDC permite el tiempo paralelo y las iteraciones SDC se hibridan, lo que relaja las limitaciones de eficiencia de Parareal y PITA. El uso de correcciones FAS permite mucha flexibilidad al construir los propagadores gruesos de PFASST (hacer que los propagadores gruesos sean lo más baratos posible ayuda a aumentar la eficiencia paralela). Las estrategias de engrosamiento incluyen: engrosamiento de tiempo (menos nodos SDC), engrosamiento de espacio (para PDE basados ​​en cuadrícula), engrosamiento de operadores y física reducida.

Espero que esto describa los fundamentos, diferencias y similitudes entre los algoritmos. Por favor vea las referencias en esta publicación para más detalles.

Con respecto a las aplicaciones, los métodos se han aplicado a una amplia variedad de ecuaciones (órbitas planetarias, Navier-Stokes, sistemas de partículas, sistemas caóticos, dinámica estructural, flujos atmosféricos, etc.). Al aplicar la paralelización de tiempo a un problema determinado, sin duda debe validar el método de manera apropiada para el problema que se está resolviendo.