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

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

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

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

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

[math]\displaystyle{ \begin{align} x_1 + a_1 x_2 & = b_1, \\ x_2 + a_2 x_3 & = b_2, \\ \vdots \\ x_k + a_k x_{k + 1} & = b_k, \\ \vdots \\ x_{n - 1} + a_{n - 1} x_n & = b_{n - 1}, \\ x_n & = b_n \end{align} }[/math]

Нужно найти все компоненты вектора [math]\displaystyle{ \vec{x} }[/math].

Общая схема

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

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

Исходные данные: одномерный массив [math]\displaystyle{ n - 1 }[/math] чисел [math]\displaystyle{ a_k }[/math] и одномерный массив [math]\displaystyle{ n }[/math] чисел [math]\displaystyle{ b_k }[/math].

Вычисляемые данные: одномерный массив [math]\displaystyle{ n }[/math] чисел [math]\displaystyle{ x_k }[/math].

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

[math]\displaystyle{ \begin{align} x_n & = b_n, \\ x_k & = b_k - a_k x_{k + 1}, \quad k = n - 1, \dots, 1 \end{align} }[/math]

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

Вычислительное ядро последовательной схемы решения задачи можно представить в качестве последовательного набора [math]\displaystyle{ n - 1 }[/math] «двойных» операций (умножение элементов получаемого массива на элемент одного из входных массивов и вычитание результата из следующего элемента другого входного массива).

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

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

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

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

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

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

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

Опишем граф алгоритма в виде рисунка. Изображён граф для [math]\displaystyle{ n = 10 }[/math]. Как видно, граф чисто последовательный.

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

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

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

Входные данные: массив [math]\displaystyle{ a }[/math] (элементы [math]\displaystyle{ a_i }[/math] с номерами от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n - 1 }[/math]), массив [math]\displaystyle{ b }[/math] (элементы [math]\displaystyle{ b_i }[/math] с номерами от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n }[/math]).

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

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

Выходные данные: массив [math]\displaystyle{ x }[/math] (элементы [math]\displaystyle{ x_k }[/math] с номерами от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n }[/math]).

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

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

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

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

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

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

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

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