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

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

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

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

Дана система линейных алгебраических уравнений (СЛАУ) с верхней (правой) двухдиагональной матрицей, в которой диагональные элементы равны 1:
:<math>
\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>\vec{x}</math>.

==== Общая схема ====

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

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

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

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

Формулы метода:
<nowiki/>
:<math>
\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>n - 1</math> «двойных» операций (умножение элементов получаемого массива на элемент одного из входных массивов и вычитание результата из следующего элемента другого входного массива).

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

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

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

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

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

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

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

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

[[file:linear graph.png|center|thumb|800px]]

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

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

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

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

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

Объём входных данных: <nowiki/><math>2n - 1</math>.

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

Объём выходных данных: <nowiki/><math>n</math>.

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

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

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

На Фортране можно записать так:
<source lang="fortran">
	x(N) = b(N)
	DO I =  N-1,1,-1
		x(I) = b(I)-a(I)*x(I+1)
	END DO
</source>

=== Особенности реализации последовательного алгоритма ===
=== Описание локальности данных и вычислений ===
==== Описание локальности алгоритма ====
==== Описание локальности реализации алгоритма ====
===== Описание структуры обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
===== Анализ на основе теста Apex-Map =====
=== Возможные способы и особенности реализации параллельного алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Описание масштабируемости алгоритма ====
==== Описание масштабируемости реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

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