Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант: различия между версиями
Перейти к навигации
Перейти к поиску
| [непроверенная версия] | [непроверенная версия] |
Frolov (обсуждение | вклад) |
Frolov (обсуждение | вклад) |
||
| Строка 14: | Строка 14: | ||
'''Компактная схема метода Гаусса для трёхдиагональной матрицы'''<ref>Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref>Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вычисляет такое <math>LU</math>-разложение трёхдиагональной матрицы <math>A</math> на две двухдиагональные, в котором у нижней двухдиагональной матрицы <math>L</math> на главной диагонали стоят только единицы. При такой фиксации все элементы разложения становятся строго предопределёнными, с точностью до ошибок округления. Компактная схема даёт естественные формулы нахождения остальных элементов получающихся двухдиагональных матриц. | '''Компактная схема метода Гаусса для трёхдиагональной матрицы'''<ref>Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref>Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вычисляет такое <math>LU</math>-разложение трёхдиагональной матрицы <math>A</math> на две двухдиагональные, в котором у нижней двухдиагональной матрицы <math>L</math> на главной диагонали стоят только единицы. При такой фиксации все элементы разложения становятся строго предопределёнными, с точностью до ошибок округления. Компактная схема даёт естественные формулы нахождения остальных элементов получающихся двухдиагональных матриц. | ||
| − | + | <math>LU</math>-разложение трёхдиагональной матрицы является частным случаем для [[Компактная схема метода Гаусса для плотных матриц|компактной схемы метода Гаусса]] общего вида, однако из-за специфики матрицы характеристики алгоритма кардинально меняются по сравнению с компактной схемой для плотных матриц. | |
=== Математическое описание === | === Математическое описание === | ||
| Строка 29: | Строка 29: | ||
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
| + | |||
| + | Как видно из формул, n-1 раз повторяется одна и та же последовательность трёх операций: деление, умножение, вычитание. | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| + | |||
| + | В качестве макровершины можно взять последовательность трёх операций: деление, умножение, вычитание. Эти макровершины выполняются в алгоритме n-1 раз. | ||
| + | |||
=== Описание схемы реализации последовательного алгоритма === | === Описание схемы реализации последовательного алгоритма === | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
Версия 18:22, 4 июля 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 раз.
