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

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

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

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

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

[math] \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} [/math]

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

1.1.2 Общая схема

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

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

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

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

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

[math] \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} [/math]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 Существующие реализации алгоритма

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