Встречная прогонка, блочный вариант

Встречная прогонка для трёхдиагональной матрицы, точечный вариант
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ 8n-2 }[/math]
Объём входных данных	[math]\displaystyle{ 4n-2 }[/math]
Объём выходных данных	[math]\displaystyle{ n }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ 2.5n-1 }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ 4 }[/math]

Основные авторы описания: А.В.Фролов.

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

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

Встречная блочная прогонка - один из вариантов метода исключения неизвестных в приложении к решению СЛАУ вида [math]\displaystyle{ Ax = b }[/math], где

[math]\displaystyle{ A = \begin{bmatrix} A_{11} & A_{12} & 0 & \cdots & \cdots & 0 \\ A_{21} & A_{22} & A_{23}& \cdots & \cdots & 0 \\ 0 & A_{32} & A_{33} & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & A_{n-1 n-2} & A_{n-1 n-1} & A_{n-1 n} \\ 0 & \cdots & \cdots & 0 & A_{n n-1} & A_{n n} \\ \end{bmatrix}, x = \begin{bmatrix} X_{1} \\ X_{2} \\ \vdots \\ X_{n} \\ \end{bmatrix}, b = \begin{bmatrix} B_{1} \\ B_{2} \\ \vdots \\ B_{n} \\ \end{bmatrix} }[/math]

Часто, однако, при изложении сути метода блочной прогонки блоки правой части и матрицы системы обозначают и нумеруют по-другому, например СЛАУ может иметь вид ([math]\displaystyle{ N=n+1 }[/math])

[math]\displaystyle{ A = \begin{bmatrix} C_{0} & -B_{0} & 0 & \cdots & \cdots & 0 \\ -A_{1} & C_{1} & -B_{1} & \cdots & \cdots & 0 \\ 0 & -A_{2} & C_{2} & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & -A_{N-1} & C_{N-1} & -B_{N-1} \\ 0 & \cdots & \cdots & 0 & -A_{N} & C_{N} \\ \end{bmatrix}\begin{bmatrix} Y_{0} \\ Y_{1} \\ \vdots \\ Y_{N} \\ \end{bmatrix} = \begin{bmatrix} F_{0} \\ F_{1} \\ \vdots \\ F_{N} \\ \end{bmatrix} }[/math]

Блочная встречная прогонка, как и монотонная, заключается в исключении из уравнений неизвестных, однако, в отличие от монотонной, в ней исключение ведут одновременно с обоих "краёв" СЛАУ (верхнего и нижнего). В принципе, её можно считать самым простейшим вариантом метода редукции (при m=1 и встречных направлениях монотонных блочных прогонок).

Рисунок 1. Граф алгоритма встречной прогонки при n=14 без отображения входных и выходных данных. / - операция [math]\displaystyle{ X^{-1}Y }[/math], f - операция [math]\displaystyle{ A+BC }[/math] или [math]\displaystyle{ A-BC }[/math].

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

[math]\displaystyle{ m }[/math] здесь - номер уравнения, на котором "встречаются" две ветви прямого хода - "сверху" и "снизу".

В приведённых обозначениях во встречной прогонке сначала выполняют её прямой ход - вычисляют коэффициенты

"сверху":

[math]\displaystyle{ \boldsymbol{\alpha}_{1} = C_{0}^{-1} B_{0} }[/math],

[math]\displaystyle{ \boldsymbol{\beta}_{1} = C_{0}^{-1} F_{0} }[/math],

[math]\displaystyle{ \boldsymbol{\alpha}_{i+1} = (C_{i}-A_{i}\boldsymbol{\alpha}_{i})^{-1} B_{i} }[/math], [math]\displaystyle{ \quad i = 1, 2, \cdots , m-1 }[/math],

[math]\displaystyle{ \boldsymbol{\beta}_{i+1} = (C_{i}-A_{i}\boldsymbol{\alpha}_{i})^{-1}(F_{i}+A_{i}\boldsymbol{\beta}_{i}) }[/math], [math]\displaystyle{ \quad i = 1, 2, \cdots , m-1 }[/math],

и "снизу":

[math]\displaystyle{ \boldsymbol{\xi}_{N} = C_{N}^{-1} A_{N} }[/math],

[math]\displaystyle{ \boldsymbol{\eta}_{1} = C_{N}^{-1} F_{N} }[/math],

[math]\displaystyle{ \boldsymbol{\xi}_{i} = (C_{i}-B_{i}\boldsymbol{\xi}_{i+1})^{-1} A_{i} }[/math], [math]\displaystyle{ \quad i = N-1, N-2, \cdots , m }[/math],

[math]\displaystyle{ \boldsymbol{\eta}_{i} = (C_{i}-B_{i}\boldsymbol{\xi}_{i+1})^{-1}(F_{i}+B_{i}\boldsymbol{\eta}_{i+1}) }[/math], [math]\displaystyle{ \quad i = N-1, N-2, \cdots , m }[/math],

после чего вычисляют решение с помощью обратного хода

[math]\displaystyle{ Y_{m} = (E-\boldsymbol{\xi}_{m}\boldsymbol{\alpha}_{m})^{-1}(\boldsymbol{\eta}_{m}+\boldsymbol{\xi}_{m}\boldsymbol{\beta}_{m}) }[/math],

[math]\displaystyle{ Y_{m-1} = (E-\boldsymbol{\alpha}_{m}\boldsymbol{\xi}_{m})^{-1}(\boldsymbol{\beta}_{m}+\boldsymbol{\alpha}_{m}\boldsymbol{\eta}_{m}) }[/math],

[math]\displaystyle{ Y_{i} = \boldsymbol{\alpha}_{i+1} Y_{i+1} + \boldsymbol{\beta}_{i+1} }[/math], [math]\displaystyle{ \quad i = m-1, m-2, \cdots , 1, 0 }[/math],

[math]\displaystyle{ Y_{i+1} = \boldsymbol{\xi}_{i+1} Y_{i} + \boldsymbol{\eta}_{i+1} }[/math], [math]\displaystyle{ \quad i = m, m+1, \cdots , N-1 }[/math].

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

Рисунок 2. Детальный граф алгоритма встречной блочной прогонки с однократным вычислением обратных блоков при n=6 без отображения входных и выходных данных. inv - вычисление обратного блока, mult - операция перемножения блоков. Серым выделены операции, повторяющиеся при замене правой части СЛАУ

Последовательность исполнения метода следующая:

1. Инициализируется прямой ход прогонки:

[math]\displaystyle{ \boldsymbol{\alpha}_{1} = C_{0}^{-1} B_{0} }[/math],

[math]\displaystyle{ \boldsymbol{\beta}_{1} = C_{0}^{-1} F_{0} }[/math],

[math]\displaystyle{ \boldsymbol{\xi}_{N} = C_{N}^{-1} A_{N} }[/math],

[math]\displaystyle{ \boldsymbol{\eta}_{1} = C_{N}^{-1} F_{N} }[/math].

2. Последовательно выполняются формулы прямого хода:

[math]\displaystyle{ \boldsymbol{\alpha}_{i+1} = (C_{i}-A_{i}\boldsymbol{\alpha}_{i})^{-1} B_{i} }[/math], [math]\displaystyle{ \quad i = 1, 2, \cdots , m-1 }[/math],

[math]\displaystyle{ \boldsymbol{\beta}_{i+1} = (C_{i}-A_{i}\boldsymbol{\alpha}_{i})^{-1}(F_{i}+A_{i}\boldsymbol{\beta}_{i}) }[/math], [math]\displaystyle{ \quad i = 1, 2, \cdots , m-1 }[/math],

[math]\displaystyle{ \boldsymbol{\xi}_{i} = (C_{i}-B_{i}\boldsymbol{\xi}_{i+1})^{-1} A_{i} }[/math], [math]\displaystyle{ \quad i = N-1, N-2, \cdots , m }[/math],

[math]\displaystyle{ \boldsymbol{\eta}_{i} = (C_{i}-B_{i}\boldsymbol{\xi}_{i+1})^{-1}(F_{i}+B_{i}\boldsymbol{\eta}_{i+1}) }[/math], [math]\displaystyle{ \quad i = N-1, N-2, \cdots , m }[/math].

3. Инициализируется обратный ход:

[math]\displaystyle{ Y_{m} = (E-\boldsymbol{\xi}_{m}\boldsymbol{\alpha}_{m})^{-1}(\boldsymbol{\eta}_{m}+\boldsymbol{\xi}_{m}\boldsymbol{\beta}_{m}) }[/math]

[math]\displaystyle{ Y_{m-1} = (E-\boldsymbol{\alpha}_{m}\boldsymbol{\xi}_{m})^{-1}(\boldsymbol{\beta}_{m}+\boldsymbol{\alpha}_{m}\boldsymbol{\eta}_{m}) }[/math]

4. Последовательно выполняются формулы обратного хода:

[math]\displaystyle{ Y_{i} = \boldsymbol{\alpha}_{i+1} Y_{i+1} + \boldsymbol{\beta}_{i+1} }[/math], [math]\displaystyle{ \quad i = m-1, m-2, \cdots , 1, 0 }[/math],

[math]\displaystyle{ Y_{i+1} = \boldsymbol{\xi}_{i+1} Y_{i} + \boldsymbol{\eta}_{i+1} }[/math], [math]\displaystyle{ \quad i = m, m+1, \cdots , N-1 }[/math].

В связи с тем, что почти во всех формулах есть пары делений на одно и то же выражение, можно поменять их на последовательности вычисления обратных чисел с последующими умножениями на ниx (см. Рисунок 2)

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

Для выполнения блочной встречной прогонки в трёхдиагональной СЛАУ из n уравнений с n неизвестными в последовательном (наиболее быстром) варианте требуется:

• [math]\displaystyle{ 2n+2 }[/math] умножений обратного одному блока на другой,
• [math]\displaystyle{ 3n-2 }[/math] сложений/вычитаний блоков,
• [math]\displaystyle{ 3n-2 }[/math] умножений блоков.

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

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

Информационный макрограф встречной блочной прогонки изображён на рис.1. Как видно, он параллелен на прямом ходе со степенью не более 4, на обратном - не более 2. При выполнении прямого хода не только ветви, но и две подветви каждой из ветвей (левая - разложение матрицы, правая - решение первой из двухдиагональных систем) могут выполняться параллельно друг другу. Правые подветви соответствуют обратному ходу. По рисунку видно, что не только математическая суть обработки подвекторов, но даже структура графа алгоритма и направление потоков данных в нём вполне соответствуют названию "обратный ход". На рис.2 изображена версия встречной блочной прогонки, в которой благодаря малоразмерности блоков сразу можно вычислить обратный блок.

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

Обе ветви прямого хода выполняются одновременно для [math]\displaystyle{ N=2m-1 }[/math], т.е. для [math]\displaystyle{ n=2m }[/math]. Тогда для выполнения встречной блочной прогонки требуется последовательно выполнить следующие ярусы:

• [math]\displaystyle{ m+1 }[/math] ярусов умножения блока, обратного к одному, на другой или на вектор (в каждом из ярусов, кроме одного, по 4 таких операции, в одном - 2),
• по [math]\displaystyle{ 2m-1 }[/math] ярусов умножений и сложений/вычитаний блоков (в [math]\displaystyle{ m-1 }[/math] ярусах - по 4 операции, в [math]\displaystyle{ m-1 }[/math] - по две, в одном - три операции).

При классификации по высоте ЯПФ, таким образом, блочная встречная прогонка относится к алгоритмам со сложностью [math]\displaystyle{ O(n }[/math] макропераций. При классификации по ширине ЯПФ его макросложность будет равна [math]\displaystyle{ 4 }[/math].

При нечётном [math]\displaystyle{ n }[/math] ветви нельзя выполнить синхронно, поэтому предпочтительнее выбирать чётные размеры задач.

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

Входные данные: блочно-трёхдиагональная матрица [math]\displaystyle{ A }[/math] (блоки [math]\displaystyle{ A_{ij} }[/math]), вектор [math]\displaystyle{ B }[/math] (блоки [math]\displaystyle{ B_{i} }[/math]).

Выходные данные: вектор [math]\displaystyle{ X }[/math] (блоки [math]\displaystyle{ X_i }[/math] ).

Объём выходных данных: [math]\displaystyle{ n }[/math] блоков.

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

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

В зависимости от нужд вычислений, возможны как разные способы хранения матрицы СЛАУ (в виде одного массива с 3 блочными строками или в виде 3 разных массивов), так и разные способы хранения вычисляемых коэффициентов (на месте использованных уже элементов матрицы либо отдельно).

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

Встречная прогонка задумана изначально для случая, когда нужно найти только какую-то близкую к "середине" блочную компоненту вектора решения, а остальные были не нужны (решение т.н. "частичной задачи"). При появлении параллельных компьютерных устройств оказалось, что у встречной блочной прогонки есть небольшой дополнительный ресурс параллелизма. Однако для получения массового параллелизма встречная блочная прогонка должна быть распараллелена на уровне блочных операций.