Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы: различия между версиями
[непроверенная версия] | [непроверенная версия] |
Frolov (обсуждение | вклад) м (→Литература) |
ASA (обсуждение | вклад) |
||
Строка 48: | Строка 48: | ||
Важным моментом является то, что в условиях точных вычислений алгоритм сдваивания Стоуна вычислит то же самое разложение, что и [[Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант|компактная схема метода Гаусса]]. | Важным моментом является то, что в условиях точных вычислений алгоритм сдваивания Стоуна вычислит то же самое разложение, что и [[Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант|компактная схема метода Гаусса]]. | ||
− | === Математическое описание === | + | === Математическое описание алгоритма === |
=== Вычислительное ядро алгоритма === | === Вычислительное ядро алгоритма === | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
− | === | + | === Схема реализации последовательного алгоритма === |
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
=== Информационный граф === | === Информационный граф === | ||
− | === | + | === Ресурс параллелизма алгоритма === |
− | === | + | === Входные и выходные данные алгоритма === |
− | === Свойства алгоритма=== | + | === Свойства алгоритма === |
+ | |||
+ | == Программная реализация алгоритма == | ||
− | |||
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
Из-за большой избыточности вычислений алгоритм сдваивания Стоуна никогда не предназначался для последовательной реализации. | Из-за большой избыточности вычислений алгоритм сдваивания Стоуна никогда не предназначался для последовательной реализации. | ||
− | === | + | === Локальность данных и вычислений === |
− | === Возможные способы и особенности реализации | + | === Возможные способы и особенности параллельной реализации алгоритма === |
=== Масштабируемость алгоритма и его реализации === | === Масштабируемость алгоритма и его реализации === | ||
=== Динамические характеристики и эффективность реализации алгоритма === | === Динамические характеристики и эффективность реализации алгоритма === | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
=== Существующие реализации алгоритма === | === Существующие реализации алгоритма === | ||
+ | |||
== Литература == | == Литература == | ||
Версия 17:30, 28 июля 2015
Содержание
- 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 Общее описание алгоритма
Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы - часть метода сдваивания Стоуна для решения СЛАУ[1][2] вида [math]Ax = b[/math], где
- [math] A = \begin{bmatrix} a_{11} & a_{12} & 0 & \cdots & \cdots & 0 \\ a_{21} & a_{22} & a_{23}& \cdots & \cdots & 0 \\ 0 & a_{32} & a_{33} & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & a_{n-1 n-2} & a_{n-1 n-1} & a_{n-1 n} \\ 0 & \cdots & \cdots & 0 & a_{n n-1} & a_{n n} \\ \end{bmatrix}, x = \begin{bmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \\ \end{bmatrix}, b = \begin{bmatrix} b_{1} \\ b_{2} \\ \vdots \\ b_{n} \\ \end{bmatrix} [/math]
Метод сдваивания Стоуна впервые предложен в начале 70-х гг. 20го века[3] в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, методу циклической редукции.
Здесь рассматривается его первая часть - [math]LU[/math]-разложение. Оно состоит в представлении матрицы [math]A[/math] в виде произведения
- [math] \begin{bmatrix} 1 & 0 & 0 & \cdots & \cdots & 0 \\ l_{21} & 1 & 0 & \cdots & \cdots & 0 \\ 0 & l_{32} & 1 & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & l_{n-1 n-2} & 1 & 0 \\ 0 & \cdots & \cdots & 0 & l_{n n-1} & 1 \\ \end{bmatrix} \begin{bmatrix} u_{11} & u_{12} & 0 & \cdots & \cdots & 0 \\ 0 & u_{22} & u_{23}& \cdots & \cdots & 0 \\ 0 & 0 & u_{33} & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & 0 & u_{n-1 n-1} & u_{n-1 n} \\ 0 & \cdots & \cdots & 0 & 0 & u_{n n} \\ \end{bmatrix} [/math]
Важным моментом является то, что в условиях точных вычислений алгоритм сдваивания Стоуна вычислит то же самое разложение, что и компактная схема метода Гаусса.
1.2 Математическое описание алгоритма
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
1.9 Входные и выходные данные алгоритма
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
Из-за большой избыточности вычислений алгоритм сдваивания Стоуна никогда не предназначался для последовательной реализации.