Каково состояние параллельных методов ODE?

В настоящее время я изучаю параллельные методы для интеграции ODE. Существует много новой и старой литературы, описывающей широкий спектр подходов, но я не нашел каких-либо недавних обзоров или обзорных статей, описывающих эту тему в целом.

Есть книга Burrage [1], но ей почти 20 лет, и, следовательно, она не охватывает многие из более современных идей, таких как парареальный алгоритм.

[1] К. Баррейдж, Параллельные и последовательные методы для обыкновенных дифференциальных уравнений, Кларендон Пресс, Оксфорд, 1995

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

Мне известны три широких класса параллельных по времени методов:

• по методу - независимые этапы РК или интеграторы экстраполяции могут оцениваться параллельно; см. также RIDC (ревизионистский алгоритм интегральной отложенной коррекции)
• через проблему - релаксация формы волны
• через временную область - Parareal; PITA (параллельный по времени алгоритм); и PFASST (параллельная схема полного приближения в пространстве и времени).

Методы, которые распараллеливаются по всему методу, обычно работают очень близко к спецификации, но не выходят за рамки нескольких (временных) процессоров. Как правило, их относительно легче реализовать, чем другие методы, и они хороши, если у вас есть несколько дополнительных ядер, и вы ищете предсказуемые и умеренные ускорения.

Методы, которые распараллеливают во временной области, включают Parareal, PITA, PFASST. Все эти методы итеративны и состоят из недорогих (но неточных) «грубых» пропагаторов и дорогих (но точных) «тонких» пропагаторов. Они достигают параллельной эффективности, итеративно оценивая точный пропагатор параллельно, чтобы улучшить последовательное решение, полученное с использованием грубого пропагатора.

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

Во все эти методы можно сыграть во многие игры, чтобы попытаться ускорить их, и кажется, что производительность этих методов в разных областях зависит от того, какую проблему вы решаете, и какие методы доступны для ускорения грубых ошибок. пропагатор (грубые сетки, грубые операторы, грубая физика и т. д.).

Некоторые ссылки (см. Также ссылки, перечисленные в статьях):

• Эта статья демонстрирует, как различные методы могут быть распараллелены по всему методу: теоретическое сравнение явных методов Рунге-Кутты высокого порядка, экстраполяции и отложенной коррекции ; Кетчесон и Вахид.

• В этой статье также показан хороший способ распараллеливания метода и представлен алгоритм RIDC: параллельные интеграторы высокого порядка ; Christlieb, MacDonald, Ong.

• В данной статье представлен алгоритм PITA: параллельный по времени неявный метод ускорения решения задач нелинейной структурной динамики ; Кортиал и Фархат.

• Есть много статей о Parareal (просто Google это).

• Вот статья о методе Nievergelt: минимальный коммуникационный подход к параллельной временной интеграции ; Баркер.

• Эта статья представляет PFASST: к эффективному параллельному во времени методу для дифференциальных уравнений в частных производных ; Эммет и Миньон;

• Эта статья описывает изящное применение PFASST: массивно-пространственно-временного параллельного решателя N-тел ; Спек, Рупрехт, Краузе, Эммет, Миньон, Виндел, Гиббон.

Я написал две реализации PFASST, которые доступны в сети: PyPFASST и libpfasst .

Хотя этому посту уже два года, на случай, если кто-то наткнется на него, позвольте мне дать краткое обновление:

Мартин Гандер недавно написал хорошую обзорную статью, в которой дается исторический взгляд на ситуацию и обсуждается множество различных методов PINT: http://www.unige.ch/~gander/Preprints/50YearsTimeParallel.pdf

В настоящее время существует также веб-сайт сообщества, который перечисляет очень много ссылок и дает описание различных методов: http://www.parallel-in-time.org/

В частности, обсуждение алгоритма параллельного времени Parareal можно найти здесь: https://en.wikipedia.org/wiki/Parareal

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