ЯВНЫЕ МЕТОДЫ ТИПА РУНГЕ-КУТТЫ И ИХ ПАРАЛЛЕЛЬНЫЕ АНАЛОГИ
Ващенко Г.В.
Сибирский государственный технологический университет
г. Красноярск, Россия
Для численного решения задачи Коши рассматриваются параллельные аналоги алгоритмов явных методов типа Рунге-Кутты для систем обыкновен ных дифференциальных уравнений первого порядка. Предложены параллель ные вычислительные схемы методов, ориентированных на применение в много процессорных вычислительных системах кластерной архитектуры.
Рассматривается задачи Коши для систем обыкновенных дифференциаль ных уравнений первого порядка
(1)
Для численного решения задачи (1) применяется явные s-стадийные методы типа Рунге-Кутты, (n+1) -й шаг в которых задается формулами
(2)
где
Конкретный метод Рунге – Кутты определяется набором коэффициентов bi, ci, aij , 1≤i≤s, 2≤j≤(i–1) [2-4].
Основной подход при конструировании параллельных методов состоял в распараллеливании последовательных численных алгоритмов, использовании декомпозиции и анализе информационных взаимосвязей между подзадачами [1,5].
1. Последовательная вычислительная схема
Для определенности зададимся некоторым отрезком [t0, T], введем равномерную сетку wn = (t0,t1, …, tn) с величиной шага hn +1 = h и на сетке wnв начальный момент времени t0 в качестве начального условия зададим вектор . Определение значений компонент вектора приближенного решения осуществляется по формуле (2), записанной для вычисления каждой компоненты вектора
(3)
где .
Формулы (2) и (3) показывают, что определение значения сводится к строго последовательному вычислению коэффициентов , их умножению на коэффициенты bi, i = 1,2, …, s , соответственно, и последую щему суммированию.
2 Параллельная явная s –стадийная вычислительная схема
Последовательная схема (3) дает основание для организации двух типов параллельных вычислений:
а) вычисление отдельных компонент векторов коэффициентов и вектора численного решения …, ;
б) вычисление отдельных операций внутри одного шага метода.
Вычисление отдельных операций внутри одного шага метода обеспечивает небольшую степень параллелизма и поэтому не рассматривается.
С целью выявления максимального независимого набора операций при вычислении коэффициентов , i = 1, 2, …, s используется аппарат графов зависимости. Анализ графа зависимостей, в предположении, что размерность Nисходной системы (1) кратна числу компьютеров p, N = kp и схема размещения блочная обеспечивает возможность записи параллельных схем. В каждом компьютере размещено и вычисляется последовательно по k компонент векторов коэффициентов, K1(n), K2(n),…, Ks(n). Вычисления в n-ом узле сетки wnреализуются по правилу, показанному на рис.
Алгоритм. Пусть задана система (1), правая часть которой гладкая по всем аргументам yi, 1≤i≤N и пусть на заданном отрезке [t0,T] определена равномерная сетка wn. Тогда для решения задачи Коши вычислительной системе из p = N/kкомпьютеров, Comp(i), 1≤i≤N, и блочной схемой хранения, справедлив параллельный алгоритм.
На последнем шаге в каждом компьютере вычисляется и сохраняется своя часть вектора . Таким образом, после параллельного вычисления коэффициентов параллельно определяется такое же количество компонент вектора приближенного решения . Число пересылок для одного узла сетки wn составит s(p–1)2 O(sp2).
Параллельный аналог формулы (3) для равномерной сетки может быть записан в виде
где .
Заметим, что в отдельных случаях, зависящих от типа и вида исходной системы (1), может быть достигнута максимальная степень параллелизма и, соответственно, сокращение временных затрат выполнения вычислений по разработанному алгоритму. Так, например, для двустадийной схемы Рунге-Кутты параллельный алгоритм записывается следующим образом.
Шаг 1. Вычислить по формулам
,
и переслать всем (p–1) компьютерам.
Шаг 2. Вычислить по формулам
Шаг 3. Вычислить
.
Шаг 4. Сохранить .
Шаг 5. Переслать всем (p–1) компьютерам.
Рассмотренные параллельные схемы явных методов типа Рунге-Кутты ориентированы на реализацию в многопроцессорных вычислительных системах кластерной архитектуры с использованием технологии MPI. MPI имеет в составе коммуникационные операции попарные и коллективные обмены, средства организации виртуальных топологий. Исследования представленных параллельных схем показали, что для их реализация наиболее подходящими могут быть топологии кольцо, линейка, решетка и гиперкуб. Разработанные схемы могут служить основой для разработки параллельных алгоритмов решения задачи Коши явными методами с контролем точности и устойчивости, алгоритмов переменного порядка и шага, а также возможной автоматизации построения методов интегрирования с адаптивной областью устойчивости.
Новиков Е.А. Явные методы для жестких систем / Новосибирск: Наука, 1997. – 197с.
Хайрер Э., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Жесткие и дифференциально-алгебраические задачи / М.: Мир, 1999. – 685с.
Jackson K., Norsett S. The potential for parallelism in Runge -Kutta methods. Part I: RK formulas in standart form // SIAM J. Numer. Anal., v. 32, 1996. – p. 49–82
Hendrickson B., Kolda Tamara G. Graph partitioning models for parallel computing // Parallel Computing, т. 26, № 12, 2002. – p. 181–197.
Библиографическая ссылка
Ващенко Г.В. ЯВНЫЕ МЕТОДЫ ТИПА РУНГЕ-КУТТЫ И ИХ ПАРАЛЛЕЛЬНЫЕ АНАЛОГИ // Научный электронный архив.
URL: http://econf.rae.ru/article/5579 (дата обращения: 23.11.2024).
Прочитать публикацию в формате PDF
(1)
(2)
. Определение значений компонент вектора приближенного решения 
осуществляется по формуле (2), записанной для вычисления каждой компоненты вектора 
(3)
.
, их умножению на коэффициенты bi, i = 1,2, …, s , соответственно, и последую щему суммированию. 
и вектора численного решения 
…, 
; 
, i = 1, 2, …, s используется аппарат графов зависимости. Анализ графа зависимостей, в предположении, что размерность Nисходной системы (1) кратна числу компьютеров p, N = kp и схема размещения блочная обеспечивает возможность записи параллельных схем. В каждом компьютере размещено и вычисляется последовательно по k компонент векторов коэффициентов, K1(n), K2(n),…, Ks(n). Вычисления 
в n-ом узле сетки wnреализуются по правилу, показанному на рис.
по формулам
,
по формулам
.
. 
всем (p–1) компьютерам. 
. Таким образом, после параллельного вычисления коэффициентов параллельно определяется такое же количество компонент вектора приближенного решения 
.
