Разложение трёхдиагональной матрицы, вещественная версия, последовательный вариант (первая стадия прогонки)
Описание свойств и структуры алгоритма[править]
Словесное описание алгоритма[править]
Решаемая задача[править]
Дана трёхдиагональная матрица [math]\displaystyle{ A }[/math]. Нужно найти её разложение в произведение двух двудиагональных [math]\displaystyle{ L }[/math] (левая с единичной диагональю) и [math]\displaystyle{ U }[/math] (правая). Для задачи решения СЛАУ с матрицей [math]\displaystyle{ A }[/math] это разложение является первой стадией решения (известного под именем прогонки).
Общая схема[править]
Реализуется компактная схема метода Гаусса, с учётом структуры матриц.
Математическое описание[править]
Исходные данные: одномерный массив [math]\displaystyle{ n - 1 }[/math] чисел [math]\displaystyle{ b_k }[/math] (поддиагональ исходной матрицы), одномерный массив [math]\displaystyle{ n }[/math] чисел [math]\displaystyle{ a_k }[/math] (диагональ исходной матрицы), одномерный массив [math]\displaystyle{ n - 1 }[/math] чисел [math]\displaystyle{ c_k }[/math] (наддиагональ исходной матрицы).
Вычисляемые данные: одномерный массив [math]\displaystyle{ n - 1 }[/math] чисел [math]\displaystyle{ l_k }[/math] (поддиагональ матрицы [math]\displaystyle{ L }[/math]), одномерный массив [math]\displaystyle{ n }[/math] чисел [math]\displaystyle{ u_k }[/math] (диагональ матрицы [math]\displaystyle{ U }[/math]), одномерный массив [math]\displaystyle{ n - 1 }[/math] чисел [math]\displaystyle{ r_k }[/math] (наддиагональ матрицы [math]\displaystyle{ U }[/math]).
Формулы метода:
- [math]\displaystyle{ \begin{align} u_1 & = a_1, \\ r_k & = c_k, & k & = 1, \dots, n - 1, \\ l_k & = \frac{b_k}{u_k}, & k & = 1, \dots, n - 1, \\ u_k & = a_k - l_{k-1} r_{k-1}, & k & = 2, \dots, n. \end{align} }[/math]
В «очищенном» виде последний массив не вычисляется, поскольку берёт значения из входного массива.
Вычислительное ядро алгоритма[править]
Вычислительное ядро последовательной схемы решения задачи можно представить в качестве последовательного набора [math]\displaystyle{ n - 1 }[/math] «тройных» операций (деление элементов одного из входных массивов на элементы одного из получаемых массивов, умножение элементов получаемого массива на элемент одного из входных массивов и вычитание результата из следующего элемента другого входного массива).
Макроструктура алгоритма[править]
Как уже записано в описании ядра алгоритма, основную часть вычисления составляет массовый последовательный набор «тройных» операций (деление элементов одного из входных массивов на элементы одного из получаемых массивов, умножение элементов получаемого массива на элемент одного из входных массивов и вычитание результата из следующего элемента другого входного массива).
Описание схемы реализации последовательного алгоритма[править]
Формулы метода описаны выше. Последовательность исполнения — по возрастанию индексов.
Последовательная сложность алгоритма[править]
Для вычисления разложения матрицы порядка [math]\displaystyle{ n }[/math], количество операций умножения равно количеству операций вычитания и количеству операций деления и равно [math]\displaystyle{ n - 1 }[/math]. Поэтому алгоритм должен быть отнесён к алгоритмам линейной сложности по количеству последовательных операций.
Информационный граф[править]
Опишем граф алгоритма в виде рисунка. Изображён граф для [math]\displaystyle{ n = 7 }[/math]. Как видно, граф чисто последовательный. Вершине соответствует «тройная» операция (деление-умножение-вычитание).
Описание ресурса параллелизма алгоритма[править]
Последовательный вариант вычисления не имеет ресурсов параллелизма. Его ЯПФ единственна и совпадает с последовательным алгоритмом. Таким образом, в получившемся алгоритме высота параллельной формы будет равна [math]\displaystyle{ n - 1 }[/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 }[/math]), массив [math]\displaystyle{ c }[/math] (элементы [math]\displaystyle{ c_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 - 1 }[/math]).
Дополнительные ограничения: отсутствуют.
Объём входных данных: [math]\displaystyle{ 3n - 2 }[/math].
Выходные данные: массив [math]\displaystyle{ l }[/math] (элементы [math]\displaystyle{ l_k }[/math] с номерами от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n-1 }[/math]), массив [math]\displaystyle{ u }[/math] (элементы [math]\displaystyle{ u_k }[/math] с номерами от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n }[/math]).
Объём выходных данных: [math]\displaystyle{ 2n - 1 }[/math].
Свойства алгоритма[править]
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является константой (1). При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных — всего-навсего 1 (входных и выходных данных почти столько же, сколько операций; если точнее — даже больше на 66 процентов). При этом алгоритм полностью детерминирован. Дуги информационного графа локальны.
Программная реализация[править]
На Фортране можно записать так:
U(1) = A(1)
DO I = 1, N-1
L(I) = B(I)/U(I)
U(I+1) = A(I+1)-L(I)*C(I)
END DO
Если хранить выходные данные на местах входных, что часто практикуется, то программа будет выглядеть ещё короче:
DO I = 1, N-1
B(I) = B(I)/A(I)
A(I+1) = A(I+1)-B(I)*C(I)
END DO