Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант: различия между версиями
Frolov (обсуждение | вклад) |
Frolov (обсуждение | вклад) |
||
Строка 39: | Строка 39: | ||
=== Информационный граф === | === Информационный граф === | ||
+ | |||
+ | [[file:3dLU.png|thumb|center|700px|Граф алгоритма без отображения входных и выходных данных. / - деление, * - умножение, - - вычитание.]] | ||
+ | |||
=== Описание ресурса параллелизма алгоритма === | === Описание ресурса параллелизма алгоритма === | ||
Версия 16:45, 6 июля 2015
Компактная схема метода Гаусса для трёхдиагональной матрицы | |
Последовательный алгоритм | |
Последовательная сложность | [math]3n-3[/math] |
Объём входных данных | [math]3n-2[/math] |
Объём выходных данных | [math]3n-2[/math] |
Параллельный алгоритм | |
Высота ярусно-параллельной формы | [math]3n-3[/math] |
Ширина ярусно-параллельной формы | [math]1[/math] |
Основные авторы описания: А.В.Фролов
Содержание
- 1 Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Описание схемы реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Описание ресурса параллелизма алгоритма
- 1.9 Описание входных и выходных данных
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритмов
- 2.1 Особенности реализации последовательного алгоритма
- 2.2 Описание локальности данных и вычислений
- 2.3 Возможные способы и особенности реализации параллельного алгоритма
- 2.4 Масштабируемость алгоритма и его реализации
- 2.5 Динамические характеристики и эффективность реализации алгоритма
- 2.6 Выводы для классов архитектур
- 2.7 Существующие реализации алгоритма
- 3 Литература
1 Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Компактная схема метода Гаусса для трёхдиагональной матрицы[1][2] вычисляет такое [math]LU[/math]-разложение трёхдиагональной матрицы [math]A[/math] на две двухдиагональные, в котором у нижней двухдиагональной матрицы [math]L[/math] на главной диагонали стоят только единицы. При такой фиксации все элементы разложения становятся строго предопределёнными, с точностью до ошибок округления. Компактная схема даёт естественные формулы нахождения остальных элементов получающихся двухдиагональных матриц. [math]LU[/math]-разложение трёхдиагональной матрицы является частным случаем для компактной схемы метода Гаусса общего вида, однако из-за специфики матрицы характеристики алгоритма кардинально меняются по сравнению с компактной схемой для плотных матриц.
1.2 Математическое описание
Формулы метода следующие:
- [math] u_{11} = a_{11} \\ u_{i i+1} = a_{i i+1}, \quad i \in [1, n-1] \\ l_{i+1 i} = a_{i+1 i} / u_{i i} , \quad i \in [1, n-1] \\ u_{ii} = a_{ii} - l_{i i-1} u_{i-1 i}, \quad i \in [2, n] \\ [/math]
1.3 Вычислительное ядро алгоритма
Как видно из формул, n-1 раз повторяется одна и та же последовательность трёх операций: деление, умножение, вычитание.
1.4 Макроструктура алгоритма
В качестве макровершины можно взять последовательность трёх операций: деление, умножение, вычитание. Эти макровершины выполняются в алгоритме n-1 раз.