Участник:Popko Fedor/Параллельная реализация явной разностной схемы для решения уравнения теплопроводности: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 163: Строка 163:
 
* Вершины графа соответствуют узлам сетки, обозначаемым координатами <math>(n,i,p)</math>, где <math>n</math> — временной слой, <math>i</math> — пространственный узел, <math>p</math> — номер процессора.
 
* Вершины графа соответствуют узлам сетки, обозначаемым координатами <math>(n,i,p)</math>, где <math>n</math> — временной слой, <math>i</math> — пространственный узел, <math>p</math> — номер процессора.
 
* Дуги графа: черным показаны локальные зависимости между узлами, обрабатываемые одним процессором, красным - связь между процессами.
 
* Дуги графа: черным показаны локальные зависимости между узлами, обрабатываемые одним процессором, красным - связь между процессами.
[[Файл:Информационный граф для явной схемы.png|300px|thumb|center|Рис.1. Информационная структура]]
+
[[Файл:Информационный граф для явной схемы.png|300px|thumb|слева|Рис.1. Информационная структура]]
  
 
===  Ресурс параллелизма алгоритма ===
 
===  Ресурс параллелизма алгоритма ===

Версия 18:29, 5 декабря 2024

Участник:Popko Fedor

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

1.1 Общее описание алгоритма

Явная разностная схема для решения уравнения теплопроводности с правой частью предназначена для моделирования процессов теплопередачи в материале с учётом внешнего источника тепла. Уравнение теплопроводности [1] с правой частью имеет вид:

\frac{\partial u}{\partial t} = a\frac{\partial^2 u}{\partial x^2} + f(x, t),

где u(x, t) — температура в точке x в момент времени t, a — коэффициент теплопроводности материала, f(x, t) — правая часть, описывающая внешний источник или сток тепла. Также необходимо задать:

1. Граничные условия:

Граничные условия задаются на краях области x = 0 и x = L и бывают нескольких типов.

  • Граничные условия первого рода (условия Дирихле):

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

\begin{cases} u(0, t) = u_{\text{left}}(t), \\ u(L, t) = u_{\text{right}}(t), \end{cases}

где u_{\text{left}}(t) и u_{\text{right}}(t) — заданные значения температуры на левой и правой границах области.

  • Граничные условия второго рода (условия Неймана):

Граничные условия второго рода определяют тепловой поток через границы области, то есть устанавливают значение производной температуры по нормали к поверхности. Это означает, что на границах тепловой поток поддерживается постоянным.

\begin{cases} \frac{\partial u}{\partial x}\Big|_{x=0} = q_{\text{left}}(t), \\ \frac{\partial u}{\partial x}\Big|_{x=L} = q_{\text{right}}(t), \end{cases}

где q_{\text{left}}(t) и q_{\text{right}}(t) — заданные значения теплового потока на левой и правой границах.

2. Начальные условия:

Задаются для всего стержня при начальном времени t = 0: u(x, 0) = u_0(x), где u_0(x) — начальное распределение температуры по всей длине стержня.


Далее будем рассматривать граничные условия первого рода равные нулю. Тогда итоговая система будет иметь вид:

\begin{cases} \frac{\partial u}{\partial t} = a \frac{\partial^2 u}{\partial x^2} + f(x, t), & 0 \lt x \lt L, \, t \gt 0, \\ u(0, t) = u(L, t) = 0, \\ u(x, 0) = u_0(x), & 0 \leq x \leq L . \end{cases}


1.2 Математическое описание алгоритма

Для явной разностной схемы[2] приближаем производные конечными разностями на каждом временном шаге, обновляя u(x, t) в каждой точке сетки по пространству, используя значения с предыдущего временного шага. Пусть \Delta x — шаг по пространству, а \Delta t — шаг по времени.

1. Аппроксимация производной по пространству:

Вторую производную по x можно аппроксимировать следующим образом: \frac{\partial^2 u}{\partial x^2} \approx \frac{u_{i+1}^{n} - 2 u_{i}^{n} + u_{i-1}^{n}}{(\Delta x)^2}, где u_i^n — значение температуры в узле i на временном слое n.

2. Аппроксимация производной по времени:

Первую производную по t можно аппроксимировать так: \frac{\partial u}{\partial t} \approx \frac{u_i^{n+1} - u_i^n}{\Delta t}.

3. Схема явного метода:

Подставляем аппроксимации производных в исходное уравнение теплопроводности:

\frac{u_i^{n+1} - u_i^n}{\Delta t} = a \frac{u_{i+1}^{n} - 2 u_{i}^{n} + u_{i-1}^{n}}{(\Delta x)^2} + f(x_i, t_n).

Теперь выразим u_i^{n+1}:

u_i^{n+1} - u_i^n = \Delta t \cdot \left( a \frac{u_{i+1}^{n} - 2 u_{i}^{n} + u_{i-1}^{n}}{(\Delta x)^2} + f(x_i, t_n) \right).

u_i^{n+1} = u_i^n + \Delta t \cdot \left( a \frac{u_{i+1}^{n} - 2 u_{i}^{n} + u_{i-1}^{n}}{(\Delta x)^2} + f(x_i, t_n) \right).

У нас получилось явное выражение для u_i^{n+1}, которое позволяет вычислить температуру в узле i на следующем временном слое, используя значения с текущего временного слоя n.


4. Граничные условия:

Устанавливаем граничные условия для расчёта на краях области, в зависимости от физической постановки задачи, например, u(0, t) = 0 и u(L, t) =0 для закрепленных концов стержня.

5. Начальные условия:

Начальные условия для температуры по всему стержню u(x, 0) = u_0(x) для начального распределения температуры.

В результате, итоговая система уравнений для каждого временного слоя n+1 и каждого узла i в сетке может быть записана как:

\begin{cases} u_i^{n+1} = u_i^n + \Delta t \cdot \left( a \frac{u_{i+1}^n - 2 u_i^n + u_{i-1}^n}{(\Delta x)^2} + f(x_i, t_n) \right), i = 1, \dots, L-1, \\ u_0^{n+1} = u_L^{n+1} = 0, \\ u_i^0 = u_0(x_i), i = 0, \dots, L. \end{cases}

6. Устойчивость схемы

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

\frac{a \Delta t}{(\Delta x)^2} \leq \frac{1}{2}, где: a — коэффициент теплопроводности материала, \Delta t — шаг по времени, \Delta x — шаг по пространству.

1.3 Вычислительное ядро алгоритма

[3] Вычислительное ядро алгоритма состоит в обновлении значений температуры в каждой точке сетки на каждом временном шаге согласно явной разностной схеме. Основная вычислительная операция заключается в вычислении новой температуры:

u_i^{n+1} = u_i^n + \Delta t \cdot \left( a \frac{u_{i+1}^n - 2 u_i^n + u_{i-1}^n}{(\Delta x)^2} + f(x_i, t_n) \right), \quad i = 1, \dots, L-1

Это обновление выполняется для каждой внутренней точки сетки на каждом временном шаге.

1.4 Макроструктура алгоритма

  1. Инициализация: На этом этапе задаются все входные параметры: коэффициент теплопроводности a, шаги по пространству и времени \Delta x, \Delta t, длина стержня L, общее время моделирования T, а также начальные и граничные условия. Этот этап не требует параллелизации.
  2. Основной цикл по времени: Для каждого временного шага n вычисляются новые значения температуры для всех внутренних точек стержня. Каждый временной слой обрабатывается отдельно, и для каждой внутренней точки стержня вычисляется температура в следующем временном слое, а также происходит обновление граничных условий для новых значений u_0^{n+1}, u_L^{n+1}.
  3. Основной цикл по пространству: На каждом временном шаге, для каждого узла i, выполняется вычисление новой температуры по следующей формуле: u_i^{n+1} = u_i^n + \Delta t \cdot \left( a \frac{u_{i+1}^n - 2 u_i^n + u_{i-1}^n}{(\Delta x)^2} + f(x_i, t_n) \right). Этап является параллельным, так как каждое вычисление для узла i зависит только от значений на предыдущем временном шаге, что позволяет выполнять вычисления независимо для каждого узла на одном временном шаге.


1.5 Схема реализации последовательного алгоритма

Последовательный алгоритм реализуется в виде вложенных циклов:

  • Цикл по времени: Для каждого временного шага выполняется обновление температур в пространстве.
  • Цикл по пространству:Обновление значений u_i^{n+1} для всех внутренних точек сетки.
Инициализация параметров и массивов;

Для n от 0 до N_t - 1:
    Для i от 1 до N_x - 1:
        u_new[i] = u_old[i] + Δt * (a * (u_old[i+1] - 2*u_old[i] + u_old[i-1]) / (Δx)^2 + f(x_i, t_n));
    Конец цикла по i;
    
    Применение граничных условий для u_new;
    
    u_old = u_new;
    
Конец цикла по n;


1.6 Последовательная сложность алгоритма

Для каждого временного шага необходимо обновить значения температуры во всех внутренних точках сетки. Если сетка содержит N_x пространственных узлов, то на каждом временном шаге требуется выполнить N_x-2 обновлений (исключая граничные узлы). Каждое обновление включает три арифметические операции: два вычитания и одно сложение, а также умножение на константу. Таким образом, общее число арифметических операций на один временной шаг пропорционально \mathcal{O}(N). Для всех временных шагов общее количество операций составляет: \mathcal{O}(N_t \cdot N_x), где N_t — общее число временных шагов.

1.7 Информационный граф

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

  • Вершины графа соответствуют узлам сетки, обозначаемым координатами (n,i,p), где n — временной слой, i — пространственный узел, p — номер процессора.
  • Дуги графа: черным показаны локальные зависимости между узлами, обрабатываемые одним процессором, красным - связь между процессами.
Рис.1. Информационная структура

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

1.9 Входные и выходные данные алгоритма

2 Программная реализация алгоритма

2.1 Масштабируемость алгоритма и его реализации

2.2 Существующие реализации алгоритма

3 Литература

  1. Тихонов А.Н., Самарский А.А. Уравнения математической физики.
  2. Самарский А.А. Теория разностных схем. — Москва: Наука, 1989.
  3. Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, № 7, С. 36-39.