Решение правой двухдиагональной СЛАУ, вещественная версия, последовательный вариант

1 Описание свойств и структуры алгоритма

1.1 Словесное описание алгоритма

1.1.1 Решаемая задача

Дана система линейных алгебраических уравнений (СЛАУ) с верхней (правой) двухдиагональной матрицей, в которой диагональные элементы равны 1:

$\begin{align} c_1 x_1 + a_1 x_2 & = b_1, \\ c_2 x_2 + a_2 x_3 & = b_2, \\ \vdots \\ c_k x_k + a_k x_{k + 1} & = b_k, \\ \vdots \\ c_{n - 1} x_{n - 1} + a_{n - 1} x_n & = b_{n - 1}, \\ c_n x_n & = b_n \end{align}$

Нужно найти все компоненты вектора $\vec{x}$.

1.1.2 Общая схема

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

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

Исходные данные: одномерный массив $n - 1$ чисел $a_k$ и одномерный массив $n$ чисел $b_k$.

Вычисляемые данные: одномерный массив $n$ чисел $x_k$.

Формулы метода:

$\begin{align} x_n & = \frac{b_n}{c_n}, \\ x_k & = \frac{b_k - a_k x_{k + 1}}{c_k}, \quad k = n - 1, \dots, 1 \end{align}$

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

Вычислительное ядро последовательной схемы решения задачи можно представить в качестве последовательного набора $n - 1$ «тройных» операций (умножение элементов получаемого массива на элемент одного из входных массивов и вычитание результата из следующего элемента другого входного массива, с последующим делением на элемент третьего), которому предшествует одно деление.

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

Как уже записано в описании ядра алгоритма, основную часть вычисления составляет массовый последовательный набор «тройных» операций (умножение элементов получаемого массива на элемент одного из входных массивов и вычитание результата из следующего элемента другого входного массива, с последующим делением на элемент третьего), которому предшествует одно деление.

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

Формулы метода описаны выше. Последовательность исполнения — по убыванию индексов.

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

Для вычисления решения для СЛАУ порядка $n$, количество операций умножения равно количеству операций вычитания и равно $n - 1$, количество операций деления равно $n$. Поэтому алгоритм должен быть отнесён к алгоритмам линейной сложности по количеству последовательных операций.

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

Опишем граф алгоритма в виде рисунка. Изображён граф для $n = 7$. Как видно, граф чисто последовательный. Желтым изображено деление, зеленым — «тройная» операция (умножение-вычитание-деление).

Решение правой двухдиагональной СЛАУ, последовательный вариант

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

Последовательный вариант вычисления не имеет ресурсов параллелизма. Его ЯПФ единственна и совпадает с последовательным алгоритмом. Таким образом, в получившемся алгоритме высота параллельной формы будет равна $n - 1$ операций умножения плюс $n - 1$ операций вычитания плюс $n$ операций деления. В таком виде алгоритм должен быть отнесён к алгоритмам линейной сложности по высоте параллельной формы. Ширина параллельной формы равна $1$, что даёт нам постоянную сложность по ширине параллельной формы.

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

Входные данные: массив $a$ (элементы $a_i$ с номерами от $1$ до $n - 1$), массив $c$ (элементы $c_i$ с номерами от $1$ до $n$), массив $b$ (элементы $b_i$ с номерами от $1$ до $n$).

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

Объём входных данных: $3n - 1$.

Выходные данные: массив $x$ (элементы $x_k$ с номерами от $1$ до $n$).

Объём выходных данных: $n$.

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является константой (1). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объёму входных и выходных данных — всего-навсего 1 (входных и выходных данных почти столько же, сколько операций; если точнее — даже больше в полтора раза). При этом алгоритм полностью детерминирован. Дуги информационного графа локальны.

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

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

На Фортране можно записать так:

	x(N) = b(N)/c(N)
	DO I =  N-1,1,-1
		x(I) = (b(I)-a(I)*x(I+1))/c(I)
	END DO

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

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