Участник:Alexboboshko/Решение начальной задачи Коши для системы ОДУ методом Рунге-Кутта 4-го порядка

РК
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ 4mn }[/math]
Объём входных данных	[math]\displaystyle{ m + 3 }[/math]
Объём выходных данных	[math]\displaystyle{ (m+1)n }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	?
Ширина ярусно-параллельной формы	?

Основные авторы описания:

Свойства и структура алгоритма

Ресурс параллелизма алгоритма

Поскольку в описанной выше вычислительной схеме наиболее трудоемкой является операция расчета правых частей ОДУ при вычислении [math]\displaystyle{ k_i ( i = 1, \dots, 4) }[/math], то основное внимание следует уделить распараллеливанию этой операции. Здесь будет применяться подход декомпозиции уравнений системы ОДУ на подсистемы. Поэтому для инициализации рассмотрим следующую схему декомпозиции данных по имеющимся процессорным элементам с локальной памятью: на каждый [math]\displaystyle{ \mu }[/math]- ПЭ (процессорный элемент) ([math]\displaystyle{ \mu = 0, \dots, p-1 }[/math]) распределяется [math]\displaystyle{ m/p }[/math] дифференциальных уравнений и вектор [math]\displaystyle{ \bar y_0 }[/math]. Далее расчеты производятся по следующей схеме:

1. на каждом ПЭ одновременно вычисляются [math]\displaystyle{ n/p }[/math] соответствующих компонент вектора [math]\displaystyle{ \bar k_1 }[/math] по формуле [math]\displaystyle{ [ \bar k_1 ]_{\mu} = h[ \bar f(x_i, \bar y_i) ]_{\mu} }[/math]
2. для обеспечения второго расчетного этапа необходимо провести сборку вектора [math]\displaystyle{ \bar k_1 }[/math] целиком на каждом ПЭ. Затем независимо выполняется вычисление компонент вектора [math]\displaystyle{ \bar k_2 }[/math] по формуле [math]\displaystyle{ [ \bar k_2 ]_{\mu} = h[ \bar f(x_i + h/2,\bar y_i + 1/2 \bar k_1)]_{\mu} }[/math];
3. проводится сборка вектора [math]\displaystyle{ \bar k_2 }[/math] на каждом ПЭ, вычисляются компоненты вектора [math]\displaystyle{ \bar k_3:\ [ \bar k_3 ]_{\mu} = h [\bar f(x_i + h/2,\bar y_i + 1/2 \bar k_2)]_{\mu} }[/math];
4. проводится сборка вектора [math]\displaystyle{ \bar k_3 }[/math] на каждом ПЭ, вычисляются компоненты вектора [math]\displaystyle{ \bar k_4:\ [ \bar k_4 ]_{\mu} = h [\bar f(x_i + h,\bar y_i + \bar k_3)]_{\mu} }[/math];
5. рассчитываются с идеальным параллелизмом компоненты вектора [math]\displaystyle{ \bar y_{i+1}:\ [\bar y_{i+1}]_{\mu} = [\bar y_{i}]_{\mu} + ([ \bar k_1 ]_{\mu} + 2[ \bar k_2 ]_{\mu} + 2[ \bar k_3 ]_{\mu} + [ \bar k_4 ]_{\mu})/6\ }[/math] и производится сборка вектора [math]\displaystyle{ \bar y_{i+1} }[/math] на каждом ПЭ. Если необходимо продолжить вычислительный процесс, то полагается [math]\displaystyle{ i = i + 1 }[/math] и осуществляется переход на п. 1

Заметим, что в данном алгоритме производится четыре операции вычисления вектора правых частей ОДУ, шестнадцать операций сложения векторов и умножения вектора на число и четыре операции глобальной сборки векторов.

Литература

[1]

<references \>