Прогонка, точечный вариант

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

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

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

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

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

[math] 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]N=n+1[/math])

[math] 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} x_{0} \\ x_{1} \\ \vdots \\ x_{N} \\ \end{bmatrix} = \begin{bmatrix} f_{0} \\ f_{1} \\ \vdots \\ f_{N} \\ \end{bmatrix} [/math]

или, если записывать отдельно по уравнениям, то

[math] c_{0} y_{0} - b_{0} y_{1} = f_{0},\\ -a_{i} y_{i-1} + c_{i} y_{i} - b_{i} y_{i+1} = f_{i}, 1 \le i \le N-1, \\ -a_{N} y_{N-1} + c_{N} y_{N} = f_{N} [/math]

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

Граф алгоритма при n=8 без отображения входных и выходных данных. / - деление, f - операция a+bc или a-bc.

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

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

[math] \alpha_{1} = b_{0}/c_{0},\\ \beta_{1} = f_{0}/c_{0}, \\ \alpha_{i+1} = b_{i}/(c_{i}-a_{i}\alpha_{i}), \quad i = 1, 2, \cdots , N-1, \\ \beta_{i+1} = (f_{i}+a_{i}\beta_{i}/(c_{i}-a_{i}\alpha_{i}), \quad i = 1, 2, \cdots , N. [/math]

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

[math] y_{N} = \beta_{N+1}, \\ y_{i} = \alpha_{i+1} y_{i+1} + \beta_{i+1}, \quad i = N-1, N-2, \cdots , 1, 0. [/math]

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

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

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

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

Кроме представления макроструктуры алгоритма как совокупности прямого и обратного хода, прямой ход также может быть разложен на две макроединицы - разложения матрицы и прямого хода решения двухдиагональной СЛАУ, которые выполняются "одновременно", т.е., параллельно друг другу. При этом решение двухдиагональной СЛАУ использует результаты разложения.

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

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

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

[math] \alpha_{1} = b_{0}/c_{0},\\ \beta_{1} = f_{0}/c_{0}, \\ [/math]

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

[math] \alpha_{i+1} = b_{i}/(c_{i}-a_{i}\alpha_{i}), \\ \beta_{i+1} = (f_{i}+a_{i}\beta_{i}/(c_{i}-a_{i}\alpha_{i}). [/math]

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

[math] y_{N} = (f_{N}+a_{N}\beta_{N}/(c_{N}-a_{N}\alpha_{N}) [/math]

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

[math] y_{i} = \alpha_{i+1} y_{i+1} + \beta_{i+1}. [/math]

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

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

• [math]2n-1[/math] делений,
• [math]3n-3[/math] сложений/вычитаний,
• [math]3n-3[/math] умножений.

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

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

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

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

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

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

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

1.9 Описание входных и выходных данных

Входные данные: трёхдиагональная матрица [math]A[/math] (элементы [math]a_{ij}[/math]), вектор [math]b[/math] (элементы [math]b_{i}[/math]).

Выходные данные: вектор [math]x[/math] (элементы [math]x_{i}[/math]).

Объём выходных данных: [math]n[/math].

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

Соотношение последовательной и параллельной сложности, как хорошо видно, является константой (причём менее 2).

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

Алгоритм полностью детерминирован.

Обычно прогонка используется для решения СЛАУ с диагональным преобладанием. Тогда гарантируется устойчивость алгоритма.