Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Строка 48: Строка 48:
 
Важным моментом является то, что в условиях точных вычислений алгоритм сдваивания Стоуна вычислит то же самое разложение, что и [[Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант|компактная схема метода Гаусса]].
 
Важным моментом является то, что в условиях точных вычислений алгоритм сдваивания Стоуна вычислит то же самое разложение, что и [[Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант|компактная схема метода Гаусса]].
  
−
=== Математическое описание ===
+
=== Математическое описание алгоритма ===
 
=== Вычислительное ядро алгоритма ===
 
=== Вычислительное ядро алгоритма ===
 
=== Макроструктура алгоритма ===
 
=== Макроструктура алгоритма ===
−
=== Описание схемы реализации последовательного алгоритма ===
+
=== Схема реализации последовательного алгоритма ===
 
=== Последовательная сложность алгоритма ===
 
=== Последовательная сложность алгоритма ===
 
=== Информационный граф ===
 
=== Информационный граф ===
−
=== Описание ресурса параллелизма алгоритма ===
+
=== Ресурс параллелизма алгоритма ===
−
=== Описание входных и выходных данных ===
+
=== Входные и выходные данные алгоритма ===
−
=== Свойства алгоритма===
+
=== Свойства алгоритма ===
 +
 
 +
== Программная реализация алгоритма ==
  
−
== Программная реализация алгоритмов ==
 
 
=== Особенности реализации последовательного алгоритма ===
 
=== Особенности реализации последовательного алгоритма ===
  
 
Из-за большой избыточности вычислений алгоритм сдваивания Стоуна никогда не предназначался для последовательной реализации.
 
Из-за большой избыточности вычислений алгоритм сдваивания Стоуна никогда не предназначался для последовательной реализации.
  
−
=== Описание локальности данных и вычислений ===
+
=== Локальность данных и вычислений ===
−
=== Возможные способы и особенности реализации параллельного алгоритма ===
+
=== Возможные способы и особенности параллельной реализации алгоритма ===
 
=== Масштабируемость алгоритма и его реализации ===
 
=== Масштабируемость алгоритма и его реализации ===
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
=== Выводы для классов архитектур ===
 
=== Выводы для классов архитектур ===
 
=== Существующие реализации алгоритма ===
 
=== Существующие реализации алгоритма ===
 +
 
== Литература ==
 
== Литература ==
  

Версия 17:30, 28 июля 2015

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 Особенности реализации последовательного алгоритма

Из-за большой избыточности вычислений алгоритм сдваивания Стоуна никогда не предназначался для последовательной реализации.

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

  1. ↑ Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
  2. ↑ Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
  3. ↑ Stone H.S. An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations // J. ACM, Vol. 20, No. 1 (Jan. 1973), P. 27-38.
Источник — https://algowiki-project.org/w/ru/index.php?title=Алгоритм_сдваивания_Стоуна_для_LU-разложения_трёхдиагональной_матрицы&oldid=2217