Каковы различия между Parareal, PITA и PFASST?

Алгоритмы Parareal, пита, и PFASST все поголовное-области техники для распараллеливания решения нестационарных задач во времени.

1. Каковы руководящие принципы, лежащие в основе этих методов?

2. Каковы основные различия между ними?

3. Могу ли я сказать, что одно основано на другом? Как?

4. Как насчет их приложений?

Я знаю, что не будет ответа на вопрос «что лучше?», Но хорошее понимание их областей применения и условий проверки полезно для меня.

Эти методы могут быть грубо описаны в терминах двух временных пошаговые методов, обозначаемых здесь и . И и распространяют начальное значение путем аппроксимации решенияF G F U n ≈ u ( t n$G$$F$$G$$F$$U_n \approx u(t_n)$

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

от до (то есть ). Чтобы методы были эффективными, должен быть случай, когда пропагатор вычислительно менее затратен, чем пропагатор , и, следовательно, обычно является методом низкого порядка. Поскольку общая точность методов ограничена точностью пропагатор, , как правило , более высокий порядок , и, кроме того , может использовать меньший шаг времени , чем . По этим причинам упоминается как грубый пропагатор, а - тонкий пропагатор.t n + 1 ˙ u = f ( u , t ) G F G F F G G $t_n$$t_{n+1}$$\dot{u} = f(u,t)$$G$$F$$G$$F$$F$$G$$G$$F$

Метод Parareal начинается с вычисления первого приближения для где - число временных шагов, с использованием грубого пропагатора. Затем метод Parareal выполняется итеративно, чередуя параллельное вычисление и обновление начальных условий на каждом процессоре формы n = 0 … N - 1 N F ( t n + 1 , t n , U k n$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})$$

для . То есть точный пропагатор используется для уточнения решения в каждом временном интервале параллельно, в то время как грубый пропагатор используется для распространения уточнений, выполняемых тонким пропагатором, во времени на более поздние процессоры. Обратите внимание, что на данный момент мы не указали, что такое пропагаторы и : это могут быть, например, схемы Рунге-Кутты различного порядка.G $n = 0 \ldots N-1$$G$$F$

Метод PITA очень похож на Parareal, но он отслеживает предыдущие обновления и обновляет только начальные условия на каждом процессоре способом, напоминающим методы подпространства Крылова. Это позволяет PITA решать линейные уравнения второго порядка, которые Parareal не может.

Метод PFASST отличается от методов Parareal и PITA в двух основных аспектах: во-первых, он основан на схеме пошагового временного пошагового спектрального исправления ошибок (SDC), а во-вторых, включает в себя поправки схемы полной аппроксимации для грубого пропагатора и фактически PFASST. можно использовать иерархию пропагаторов (вместо двух). Использование SDC позволяет гибридизировать параллели во времени и SDC, что ослабляет ограничения эффективности Parareal и PITA. Использование поправок FAS обеспечивает большую гибкость при построении грубых пропагаторов PFASST (делая грубые пропагаторы как можно более дешевыми, помогает повысить эффективность параллельной работы). Стратегии укрупнения включают: укрупнение времени (меньшее количество узлов SDC), укрупнение пространства (для PDE на основе сетки), укрупнение операторов и уменьшение физики.

Я надеюсь, что это обрисовывает в общих чертах основы, различия и сходства между алгоритмами. Пожалуйста, смотрите ссылки в этом сообщении для более подробной информации.

Что касается приложений, методы были применены к широкому кругу уравнений (планетарные орбиты, системы Навье-Стокса, системы частиц, хаотические системы, структурная динамика, атмосферные потоки и т. Д. И т. Д.). При применении распараллеливания во времени к данной проблеме вы должны обязательно проверить метод таким образом, который соответствует решаемой проблеме.