Параллелизация по времени для гиперболических и параболических задач

Параллелизация по времени, также известная как PinT (параллелизация по времени), представляет собой новое направление исследований, связанное с разработкой алгоритмов для решения эволюционных задач очень большого масштаба на высокопараллельных вычислительных архитектурах. Несмотря на то что интересные теоретические работы по PinT появились еще в 1964 году, активное развитие исследований в этой области началось лишь в 2004 году, когда тактовые частоты процессоров достигли физического предела. Отличительной особенностью параллелизации по времени является то, что поток информации направлен только вперед во времени, поэтому процессы временной эволюции, по-видимому, неизбежно должны выполняться последовательно. Тем не менее за последние два десятилетия было разработано множество алгоритмов для вычислений PinT, которые часто объединяют в четыре основные класса в зависимости от принципа работы и способов применения соответствующих методов: методы стрельбового типа; методы релаксации волнового поля, основанные на декомпозиции области; многосеточные методы в пространстве–времени; и прямые методы параллелизации по времени. Однако в последние несколько лет было признано, что высокоэффективные алгоритмы PinT для параболических задач испытывают трудности при применении к гиперболическим задачам. Поэтому мы сосредоточимся на этом важном аспекте, начав с обзора фундаментальных различий между параболическими и гиперболическими задачами с точки зрения параллелизации по времени. Затем мы разделим алгоритмы PinT на две основные группы. Первая группа включает четыре эффективных метода PinT для гиперболических задач: релаксацию волнового поля Шварца (SWR) и ее связь с построением шатровых сеток; параллельную интегральную отсроченную коррекцию; ParaExp; и ParaDiag. Хотя методы первой группы также хорошо работают для параболических задач, во второй группе мы представим методы PinT, специально разработанные для параболических задач: Parareal; параллельную схему полной аппроксимации в пространстве–времени (PFASST); многосеточное сокращение по времени (MGRiT); и многосеточный метод в пространстве–времени (STMG). Наш анализ дополнен численными иллюстрациями с использованием четырех зависящих от времени уравнений в частных производных: уравнения теплопроводности; уравнения адвекции–диффузии; уравнения Бюргерса; и волнового уравнения второго порядка.