Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][выверенная версия]
м
м
Строка 21: Строка 21:
 
</math>
 
</math>
  
−
Предложен [http://russianscdays.org/node/28 в 2015 г.]<ref>Фролов А.В. Ещё один метод распараллеливания прогонки с использова-нием ассоциативности операций // Принята в качестве доклада на первую объединенную международную конференцию "Суперкомпьютерные дни в России", Москва, 28-29 сентября 2015 г.</ref> в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, [[Метод циклической редукции|методу циклической редукции]]. В отличие от своих предшественников, метод Стоуна основан на <math>LU</math>-разложении матрицы исходной СЛАУ и состоит из двух существенно различных по свойствам частей: [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы|алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] и [[Метод сдваивания Стоуна для решения двухдиагональных СЛАУ|метода сдваивания Стоуна для решения двухдиагональных СЛАУ]].
+
Предложен [http://russianscdays.org/node/28 в 2015 г.]<ref>Фролов А.В. Ещё один метод распараллеливания прогонки с использованием ассоциативности операций // Принята в качестве доклада на первую объединенную международную конференцию "Суперкомпьютерные дни в России", Москва, 28-29 сентября 2015 г.</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-разложения трёхдиагональной матрицы]] - сильно уступает им по характеристикам устойчивости. Поэтому на практике метод Стоуна давно не применяется. Его, однако, используют при обучении параллельным технологиям студентов, приводя как пример распараллеливания прогонки.  
+
В отличие от метода Стоуна, однако, первая из частей метода спроектирована с использованием нормировки, что делает область устойчивости метода гораздо шире, чем при рекурсивном сдваивании Стоуна.  
  
 
Вычислительные характеристики обеих частей метода лучше рассматривать отдельно, они  описаны на соответствующих страницах.  
 
Вычислительные характеристики обеих частей метода лучше рассматривать отдельно, они  описаны на соответствующих страницах.  
Строка 32: Строка 32:
  
 
[[Категория:Законченные_статьи]]
 
[[Категория:Законченные_статьи]]
−
[[Категория:Метод сдваивания]]
+
[[Категория:Последовательно-параллельная группировка операций]]
−
[[Категория:Неустойчивые параллельные методы]]
 
 
[[Категория:Алгоритмы с избыточными вычислениями]]
 
[[Категория:Алгоритмы с избыточными вычислениями]]

Версия 20:50, 10 августа 2015

Последовательно-параллельный вариант решения с 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]

Предложен в 2015 г.[3] в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, методу циклической редукции. Как и непосредственный идейный предшественник, метод Стоуна, он также основан на [math]LU[/math]-разложении матрицы исходной СЛАУ с использованием ассоциативности операции матричного умножения и тоже состоит из двух существенно различных по свойствам частей: последовательно-параллельного алгоритма для LU-разложения трёхдиагональной матрицы и последовательно-параллельного варианта обратной подстановки.

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

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

Литература

  1. ↑ Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
  2. ↑ Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
  3. ↑ Фролов А.В. Ещё один метод распараллеливания прогонки с использованием ассоциативности операций // Принята в качестве доклада на первую объединенную международную конференцию "Суперкомпьютерные дни в России", Москва, 28-29 сентября 2015 г.
Источник — https://algowiki-project.org/w/ru/index.php?title=Последовательно-параллельный_вариант_решения_трёхдиагональной_СЛАУ_с_LU-разложением_и_обратными_подстановками&oldid=2323