Уровень метода

Метод сдваивания Стоуна: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][выверенная версия]
 
(не показано 17 промежуточных версий 3 участников)
Строка 1: Строка 1:
== Свойства и структура алгоритмов ==
+
{{level-m}}
=== Общее описание алгоритма ===
 
  
'''Метод сдваивания Стоуна''' - один из вариантов замены прогонки в приложении к решению СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида <math>Ax = b</math>, где
+
Основные авторы описания: [[Участник:Frolov|А.В.Фролов]]
:<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го века<ref>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.</ref>, в качестве замены другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, [[Метод циклической редукции|методу циклической редукции]]. В отличие от своих предшественников, метод Стоуна основан на <math>LU</math>-разложении матрицы исходной СЛАУ и состоит из двух существенно различных по свойствам частей: [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы|алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] и [[Метод сдваивания Стоуна для решения двухдиагональных СЛАУ|метода сдваивания Стоуна для решения двухдиагональных СЛАУ]].  
+
'''Метод сдваивания Стоуна''' (иначе '''схема Стона''' <ref name="F">Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре 1,2. // Кибернетика, 1977. №6. С. 28-40; 1982. №3. С. 18-31</ref>) - один из вариантов замены [[Прогонка, точечный вариант|прогонки]] в приложении к решению СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида <math>Ax = b</math>, где
 +
 
 +
{{Шаблон:Трёхдиагональная_СЛАУ_в_стандартном_виде}}
 +
 
 +
Впервые предложен в начале 70-х гг. 20го века<ref>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.</ref> в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, [[Полный метод циклической редукции|методу циклической редукции]]. В отличие от своих непосредственных предшественников с логарифмическим критическим путём графа алгоритма, метод Стоуна, как и классическая монотонная прогонка, основан на <math>LU</math>-разложении матрицы исходной СЛАУ и состоит из двух существенно различных по свойствам частей: [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы|алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] и [[Метод сдваивания Стоуна для решения двудиагональных СЛАУ|метода сдваивания Стоуна для решения двудиагональных СЛАУ]].
 +
 
 +
Несмотря на некоторые преимущества перед другими параллельными алгоритмами решения трёхдиагональных СЛАУ<ref>Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.</ref>, оказалось, что первая из частей метода - [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы|алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] - сильно уступает им по характеристикам устойчивости, расходясь уже на сколько-нибудь реальных размерах матриц. Поэтому на практике метод Стоуна не применяется. Его, однако, используют при обучении параллельным технологиям студентов, приводя как пример распараллеливания прогонки.
 +
 
 +
Вычислительные характеристики обеих частей метода лучше рассматривать отдельно, они  описаны на соответствующих страницах.  
  
=== Математическое описание ===
 
=== Вычислительное ядро алгоритма ===
 
=== Макроструктура алгоритма ===
 
=== Описание схемы реализации последовательного алгоритма ===
 
=== Последовательная сложность алгоритма ===
 
=== Информационный граф ===
 
=== Описание ресурса параллелизма алгоритма ===
 
=== Описание входных и выходных данных ===
 
=== Свойства алгоритма===
 
== Программная реализация алгоритмов ==
 
=== Особенности реализации последовательного алгоритма ===
 
=== Описание локальности данных и вычислений ===
 
=== Возможные способы и особенности реализации параллельного алгоритма ===
 
=== Масштабируемость алгоритма и его реализации ===
 
=== Динамические характеристики и эффективность реализации алгоритма ===
 
=== Выводы для классов архитектур ===
 
=== Существующие реализации алгоритма ===
 
 
== Литература ==
 
== Литература ==
  
 
<references />
 
<references />
  
[[Категория:Статьи в работе]]
+
[[Категория:Законченные_статьи]]
 +
[[Категория:Метод сдваивания]]
 +
[[Категория:Неустойчивые параллельные методы]]
 +
[[Категория:Алгоритмы с избыточными вычислениями]]
 +
 
 +
[[en:Stone doubling algorithm]]

Текущая версия на 15:29, 14 марта 2018


Основные авторы описания: А.В.Фролов

Метод сдваивания Стоуна (иначе схема Стона [1]) - один из вариантов замены прогонки в приложении к решению СЛАУ[2][3] вида [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го века[4] в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, методу циклической редукции. В отличие от своих непосредственных предшественников с логарифмическим критическим путём графа алгоритма, метод Стоуна, как и классическая монотонная прогонка, основан на [math]LU[/math]-разложении матрицы исходной СЛАУ и состоит из двух существенно различных по свойствам частей: алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы и метода сдваивания Стоуна для решения двудиагональных СЛАУ.

Несмотря на некоторые преимущества перед другими параллельными алгоритмами решения трёхдиагональных СЛАУ[5], оказалось, что первая из частей метода - алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы - сильно уступает им по характеристикам устойчивости, расходясь уже на сколько-нибудь реальных размерах матриц. Поэтому на практике метод Стоуна не применяется. Его, однако, используют при обучении параллельным технологиям студентов, приводя как пример распараллеливания прогонки.

Вычислительные характеристики обеих частей метода лучше рассматривать отдельно, они описаны на соответствующих страницах.

Литература

  1. Фаддеева В.Н., Фаддеев Д.К. Параллельные вычисления в линейной алгебре 1,2. // Кибернетика, 1977. №6. С. 28-40; 1982. №3. С. 18-31
  2. Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
  3. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
  4. 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.
  5. Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.