Алгоритм продольно-поперечной прогонки

Основные авторы описания: Дружкина А.И., Лиходед Н.А.

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

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

Продольно–поперечная схема, которая также носит название метода переменных направлений (ADI – alternate directions implicit method), получила широкое применение для решения многомерных задач, приводящих к уравнениям в частных производных параболического типа (уравнение диффузии, уравнение теплопроводности). Эта схема была предложена в 1955 году Писменом и Рэкфордом.

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

Рассмотрим в области

$\begin{align} D_{T}=G\times [0\leq t\leq T], \\ G=[0\leq x\leq l_{x}]\times[0\leq y\leq l_{y}]\end{align}$

двумерное нелинейное уравнение теплопроводности

$\frac{\partial u}{\partial t} = \frac{\partial }{\partial x_{1}}\left ( k_{1}(x_{1}, x_{2}, t)\frac{\partial }{\partial x_{1}} \right ) + \frac{\partial }{\partial x_{2}}\left ( k_{1}(x_{1}, x_{2}, t)\frac{\partial }{\partial x_{2}} \right ) + f\left ( x_{1}, x_{2}, t \right )$

с начальными

$T(x,y,0) = T_{0}(x,y), (x,y)\in G,$

и граничными условиями

$T(x,y,t)|_{S_{T}} = \mu (x,y,t), (x,y,t)\in S_{T}\equiv \partial D_{T}$

Введем в области $G$ сетку узлов $\bar{\omega_{h}} = \left \{ x^{i}=i\cdot h_{x}, i=0,1,...,N_{x}, N_{x}\cdot h_{x}=l_{x},y^{j}=j\cdot h_{y}, j=0,1,...,N_{y}, N_{y}\cdot h_{y}=l_{y} \right \}$, а на отрезке $[0\leq t\leq T]$ сетку узлов $\omega_{\tau } = \left \{ t_{j}=n\tau, n=0,1,...,k, k\tau=T \right \}.$. Запишем разностную схему для заданной задачи ($k_{1} = k_{2} = \lambda$):

$\left\{\begin{matrix} \frac{y_{i,j}^{n+\frac{1}{2}} - y_{i,j}^{n}}{\tau} = \frac{1}{2}\left ( \frac{\lambda_{i+\frac{1}{2}, j}(y_{i+1,j}^{n+\frac{1}{2}} - y_{i,j}^{n+\frac{1}{2}}) - \lambda_{i-\frac{1}{2}, j}(y_{i,j}^{n+\frac{1}{2}} - y_{i-1,j}^{n+\frac{1}{2}})}{h_{x}^{2}} \right ) + \frac{1}{2}\left ( \frac{\lambda_{i, j+\frac{1}{2}}(y_{i,j+1}^{n} - y_{i,j}^{n}) - \lambda_{i, j-\frac{1}{2}}(y_{i,j}^{n} - y_{i,j-1}^{n})}{h_{y}^{2}} \right ), \\ \frac{y_{i,j}^{n+1} - y_{i,j}^{n+\frac{1}{2}}}{\tau} = \frac{1}{2}\left ( \frac{\lambda_{i+\frac{1}{2}, j}(y_{i+1,j}^{n+\frac{1}{2}} - y_{i,j}^{n+\frac{1}{2}}) - \lambda_{i-\frac{1}{2}, j}(y_{i,j}^{n+\frac{1}{2}} - y_{i-1,j}^{n+\frac{1}{2}})}{h_{x}^{2}} \right ) + \frac{1}{2}\left ( \frac{\lambda_{i, j+\frac{1}{2}}(y_{i,j+1}^{n+1} - y_{i,j}^{n+1}) - \lambda_{i, j-\frac{1}{2}}(y_{i,j}^{n+1} - y_{i,j-1}^{n+1})}{h_{y}^{2}} \right ) \end{matrix}\right.$

где $\lambda _{i\pm \frac{1}{2}, j} = \frac{\lambda _{i\pm 1, j} + \lambda _{i, j}}{2},$ $\lambda _{i, j\pm \frac{1}{2}} = \frac{\lambda _{i, j\pm 1} + \lambda _{i, j}}{2}.$

Зафиксировав в первом из уравнений системы $j$, получим систему уравнений относительно значений $y_{i,j}^{n+\frac{1}{2}}$, где $j = 1,...,N_{x}-1$, состоящую из ($N_{x}-1$) линейного уравнения, которую можно решить методом прогонки. В целом систему на каждом половинном временном слое можно представить как ($N_{x}-1$) независимую задачу (для каждого фиксированного $j$), решаемую методом прогонки. Аналогично решение второго из уравнений системы на каждом слое $t_{n+1}$ представляет собой решение ($N_{x}-1$) независимой задачи при фиксированном $i$. Каждая из указанных задач является системой линейных уравнений относительно значений сеточной функции по неявному направлению и решается методом прогонки. Сеточная функция , является приближенным решением задачи. По каждому из неявных направлений разностная схема является линейной и может быть записана в следующем виде:

$A_{i,j}y_{i-1,j}^{n+\frac{1}{2}} + C_{i,j}y_{i,j}^{n+\frac{1}{2}} + B_{i,j}y_{i+1,j}^{n+\frac{1}{2}} = F_{i,j}^{n}$

$A_{i,j} = \frac{\lambda_{i-\frac{1}{2},j}}{-2h_{y}^{2}}, B_{i,j} = \frac{\lambda_{i+\frac{1}{2},j}}{-2h_{y}^{2}}, C_{i,j} = \frac{1}{\tau} - A_{i,j} - B_{i,j},$

$F_{i,j}^{n+\frac{1}{2}} = \frac{y_{i,j}^{n+\frac{1}{2}}}{\tau} + \frac{\lambda _{i+\frac{1}{2}, j}(y_{i+1, j}^{n+\frac{1}{2}} - y_{i, j}^{n+\frac{1}{2}}) - \lambda _{i-\frac{1}{2}, j}(y_{i,j}^{n+\frac{1}{2}} - y_{i-1, j}^{n+\frac{1}{2}})}{h_{y}^{2}}$

и соответственно

$A_{i,j}y_{i,j-1}^{n+1} + C_{i,j}y_{i,j}^{n+1} + B_{i,j}y_{i,j+1}^{n+1} = F_{i,j}^{n+\frac{1}{2}}.$

Для решения уравнений воспользуемся формулами прогонки. Значения прогоночных коэффициентов находятся по рекуррентным формулам:

где $k$ – индекс неявного направления. Из граничных условий при $k=0$ и $k=N$ определяются значения прогоночных коэффициентов. При этом $\alpha _{0}$ и $\alpha _{N}$ равны нулю, а значения $\beta _{0}$ и $\beta _{N}$ определяются из соответствующих краевых условий.

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

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

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

Алгоритм представляет собой совокупность продольной и поперечной прогонки, а также прямого и обратного хода.

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

Последовательность исполнения метода следующая: Осуществляется прогонка вдоль строк, как это изображено на рисунке 1.1 [4]:

Рисунок 1.1– Прогонка вдоль строк

Затем осуществляется прогонка вдоль столбцов, как это представлено на рисунке 1.2 [4]:

Рисунок 1.2- Прогонка вдоль столбцов

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

Таким образом, при классификации по последовательной сложности продольно–поперечная прогонка относится к алгоритмам с линейной сложностью. При переходе от слоя $j$ к слою $j+1$ требуется $O(\frac{1}{h^{2}})$ арифметических действий. Чтобы найти $y^{j_{0}}$ при $t_{0} = j_{0}\tau$ по начальным данным требуется, очевидно, $O(\frac{1}{h^{2}})j_{0} = O(\frac{1}{\tau h^{2}})$ операций, то есть число операций пропорционально числу используемых узлов пространственно–временной сетки $w_{h\tau}$. Наряду с основными значениями $u_{ij}^{k}$ и $u_{i,j}^{k+1}$ вводится значение на промежуточном слое – $u_{ij}^{k+\frac{1}{2}}$, что фактически является значением $u$ при $t = t_{k+\frac{1}{2}}=t+\frac{\tau}{2}$. Благодаря этому, переход на следующий слой осуществляется в два шага.

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

Алгоритм метода переменных направлений обладает естественным параллелизмом: можно организовать независимые вычислительные процессы на каждом временном слое.

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

Входные данные: матрица $y$ (элементы $y_{i,j}^{1}, i = 0,...,N_{x}, j = 0,...,N_{y}$).

Конечные значения $y_{(2)}(i_{1}, i_{2})$ являются приближенным решением задачи

Выходные данные: обновленная матрица $y$ (элементы $y_{i,j}^{n+1}, i = 0,...,N_{x}, j = 0,...,N_{y}$).

Объём выходных данных: $(N_{x} + 1) * (N_{y} + 1)$

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

Продольно–поперечная схема является одной из первых экономичных схем. Она сочетает в себе лучшее качество явной схемы – экономичность и неявной – устойчивость. Основной идеей экономичных разностных схем является сведение многомерной задачи к цепочке одномерных задач. Продольно–поперечная схема равномерно и безусловно устойчива по начальным данным, так как при переходе с одного целого слоя на следующий целый слой ошибки начальных данных не нарастают. При переходе с целого слоя на целый погрешность локальной аппроксимации на равномерных сетках есть $O(\tau^{2} + h_{x}^{2} + h_{y}^{2})$ т.е. продольно–поперечная схема имеет второй порядок аппроксимации по всем переменным.

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

2.1 Особенности реализации последовательного алгоритма

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

2.3 Возможные способы и особенности параллельной реализации алгоритма

Вычислительные процессы реализаций, основанных на естественном па-раллелизме, на каждом временном слое могут выполняться независимо, но при переходе к новому слою требуют групповых коммуникаций “каждый с каждым”. С ростом числа используемых процессов это приводит к большим накладным расходам. Локальность алгоритма – это вычислительное свойство, отражающее степень использования при реализации алгоритма памяти с быстрым доступом. При многопроцессорной обработке памятью с быстрым доступом считается локальная память процессора. В этой работе вместо части естественного параллелизма предлагается использовать конвейерный параллелизм. Такой параллелизм приводит к разгону и торможению вычислительного конвейера на каждом временном слое, но позволяет построить параллельный алгоритм с улучшенной локальностью (с существенно меньшим объемом коммуникационных операций).

2.3.1 Вычислительный алгоритм продольно-поперечной прогонки

Основную вычислительную часть алгоритма, реализующего двухшаговую разностную схему продольно–поперечной прогонки, т.е. метода переменных направлений, можно представить в виде следующего псевдокода (циклы, итерации которых заведомо можно выполнять независимо, запишем как dopar):

do  j =1, j0  
     dopar  i2= 1, N2 –1 
          do  i1= 1, N1 –1
S1:            
S2:            
          enddo
          do  i1= 1, N1 –1
S3:           
          enddo
     enddopar
     dopar  i1= 1, N1 –1
          do  i2= 1, N2 –1
S4:            
S5:            
          enddo
          do  i2= 1, N2 –1
S6:          
          enddo
     enddopar
enddo(j)

Здесь (i) и (i) – коэффициенты прогонки, возникающие при решении промежуточных систем линейных алгебраических уравнений. Конечные значения являются приближенным решением задачи. Алгоритм метода переменных направлений обладает естественным параллелизмом: можно организовать независимые вычислительные процессы на каждом временном слое. Так как число вычислительных ядер обычно гораздо меньше N1 и N2, то при реализации на параллельных компьютерах с распределенной памятью итерации циклов, отмеченных как dopar, следует сгруппировать и получить макрооперации, называемые зернами вычислений или тайлами. Процесс получения макроопераций–тайлов называется тайлингом.

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

В языке Matlab существует реализация алгоритма продольно-поперечной прогонки. Также метод продольно–поперечной прогонки реализован в библиотеке для решения дифференциальных уравнений языка Python.