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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][выверенная версия]
(Новая страница: «'''Последовательно-параллельный вариант решения с LU-разложением и обратными подстановка…»)
 
 
(не показано 8 промежуточных версий 1 участника)
Строка 1: Строка 1:
−
'''Последовательно-параллельный вариант решения с LU-разложением и обратными подстановками''' - один из вариантов замены [[Прогонка, точечный вариант|прогонки]] в приложении к решению трёхдиагональной СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида <math>Ax = b</math>, где
+
{{level-m}}
−
:<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 г. http://russianscdays.org/node/28]<ref>Фролов А.В. Ещё один метод распараллеливания прогонки с использова-нием ассоциативности операций // Принята в качестве доклада на первую объединенную международную конференцию "Суперкомпьютерные дни в России", Москва, 28-29 сентября 2015 г.</ref> в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, [[Метод циклической редукции|методу циклической редукции]]. В отличие от своих предшественников, метод Стоуна основан на <math>LU</math>-разложении матрицы исходной СЛАУ и состоит из двух существенно различных по свойствам частей: [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы|алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] и [[Метод сдваивания Стоуна для решения двухдиагональных СЛАУ|метода сдваивания Стоуна для решения двухдиагональных СЛАУ]].
+
'''Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками''' - один из вариантов замены [[Прогонка, точечный вариант|прогонки]] в приложении к решению трёхдиагональной СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида <math>Ax = b</math>, где
  
−
Несмотря на некоторые преимущества перед другими параллельными алгоритмами решения трёхдиагональных СЛАУ<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-разложения трёхдиагональной матрицы]] - сильно уступает им по характеристикам устойчивости. Поэтому на практике метод Стоуна давно не применяется. Его, однако, используют при обучении параллельным технологиям студентов, приводя как пример распараллеливания прогонки.  
+
{{Шаблон:Трёхдиагональная_СЛАУ_в_стандартном_виде}}
 +
 
 +
Предложен <ref>А.В.Фролов. Ещё один метод распараллеливания прогонки с использованием ассоциативности операций // Суперкомпьютерные дни в России: Труды международной конференции (28-29 сентября 2015 г., г. Москва). – М.: Изд-во МГУ, 2015. с. 151-162</ref> в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ, например, [[Метод циклической редукции|методу циклической редукции]]. Как и  непосредственный идейный предшественник, [[Метод сдваивания Стоуна|метод Стоуна]], он также основан на <math>LU</math>-разложении матрицы исходной СЛАУ с использованием ассоциативности операции матричного умножения и тоже состоит из двух существенно различных по свойствам частей: [[Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы|последовательно-параллельного алгоритма для LU-разложения трёхдиагональной матрицы]] и [[Последовательно-параллельный вариант обратной подстановки|последовательно-параллельного варианта обратной подстановки]].
 +
 
 +
В отличие от метода Стоуна, однако, первая из частей метода спроектирована с использованием нормировки, что делает область устойчивости метода гораздо шире, чем при рекурсивном сдваивании Стоуна. Тем не менее, она всё же уступает областям устойчивости как обычной и встречной прогонок, так и редукции (в её обычном и циклическом вариантах).  
  
 
Вычислительные характеристики обеих частей метода лучше рассматривать отдельно, они  описаны на соответствующих страницах.  
 
Вычислительные характеристики обеих частей метода лучше рассматривать отдельно, они  описаны на соответствующих страницах.  
Строка 32: Строка 16:
  
 
[[Категория:Законченные_статьи]]
 
[[Категория:Законченные_статьи]]
−
[[Категория:Метод сдваивания]]
+
[[Категория:Последовательно-параллельная группировка операций]]
−
[[Категория:Неустойчивые параллельные методы]]
 
 
[[Категория:Алгоритмы с избыточными вычислениями]]
 
[[Категория:Алгоритмы с избыточными вычислениями]]
 +
 +
[[en:Serial-parallel method for solving tridiagonal matrices based on the LU decomposition and backward substitutions]]

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


Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с 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]

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

В отличие от метода Стоуна, однако, первая из частей метода спроектирована с использованием нормировки, что делает область устойчивости метода гораздо шире, чем при рекурсивном сдваивании Стоуна. Тем не менее, она всё же уступает областям устойчивости как обычной и встречной прогонок, так и редукции (в её обычном и циклическом вариантах).

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

Литература

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