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

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

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

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

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

[math] \begin{align} c_1 x_1 & = b_1, \\ a_1 x_1 + c_2 x_2 & = b_2, \\ \vdots \\ a_{k - 1} x_{k - 1} + c_k x_k & = b_k, \\ \vdots \\ a_{n - 1} x_{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_1 & = \frac{b_1}{c_1}, \\ x_k & = \frac{b_k - a_{k - 1} x_{k - 1}}{c_k}, \quad k = 2, \dots, n. \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 (входных и выходных данных почти столько же, сколько операций; если точнее — даже больше на 33 процента). При этом алгоритм полностью детерминирован. Дуги информационного графа локальны.

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

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

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

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

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