Заочные электронные конференции
 
     
Явные методы типа Рунге-Кутты и их параллельные аналоги
Ващенко Г.В.


Для чтения PDF необходима программа Adobe Reader
GET ADOBE READER

УДК 519.852.6

ЯВНЫЕ МЕТОДЫ ТИПА РУНГЕ-КУТТЫ И ИХ ПАРАЛЛЕЛЬНЫЕ АНАЛОГИ

Ващенко Г.В.

Сибирский государственный технологический университет

г. Красноярск, Россия

Для численного решения задачи Коши рассматриваются параллельные аналоги алгоритмов явных методов типа Рунге-Кутты для систем обыкновен ных дифференциальных уравнений первого порядка. Предложены параллель ные вычислительные схемы методов, ориентированных на применение в много процессорных вычислительных системах кластерной архитектуры.

Рассматривается задачи Коши для систем обыкновенных дифференциаль ных уравнений первого порядка

(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, и блочной схемой хранения, справедлив параллельный алгоритм.

Шаг 1. Вычислить по формулам

,

и переслать всем (p–1) компьютерам.

Шаг 2. Вычислить по формулам

ипереслать всем (p–1) компьютерам.

.. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Шаг s. Вычислить .

Шаг (s+1). Вычислить

.

Шаг (s+2). Сохранить .

Шаг (s+3). Переслать всем (p–1) компьютерам.

Рис. Вычисление коэффициентов и вектора

приближенного решения при N = kp

На последнем шаге в каждом компьютере вычисляется и сохраняется своя часть вектора . Таким образом, после параллельного вычисления коэффициентов параллельно определяется такое же количество компонент вектора приближенного решения . Число пересылок для одного узла сетки wn составит s(p–1)2 O(sp2).

Параллельный аналог формулы (3) для равномерной сетки может быть записан в виде

где .

Заметим, что в отдельных случаях, зависящих от типа и вида исходной системы (1), может быть достигнута максимальная степень параллелизма и, соответственно, сокращение временных затрат выполнения вычислений по разработанному алгоритму. Так, например, для двустадийной схемы Рунге-Кутты параллельный алгоритм записывается следующим образом.

Шаг 1. Вычислить по формулам

,

и переслать всем (p–1) компьютерам.

Шаг 2. Вычислить по формулам

Шаг 3. Вычислить

.

Шаг 4. Сохранить .

Шаг 5. Переслать всем (p–1) компьютерам.

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

Литература

  1. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления / Спб.: БХВ – Петербург, 2002. – 806 с.

  2. Новиков Е.А. Явные методы для жестких систем / Новосибирск: Наука, 1997. – 197с.

  3. Хайрер Э., Ваннер Г. Решение обыкновенных дифференциальных уравнений. Жесткие и дифференциально-алгебраические задачи / М.: Мир, 1999. – 685с.

  4. 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

  5. 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/5396 (дата обращения: 29.03.2024).



Сертификат Получить сертификат