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

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

Материал из Алговики
Перейти к навигации Перейти к поиску
 
Строка 18: Строка 18:
 
[[Категория:Последовательно-параллельная группировка операций]]
 
[[Категория:Последовательно-параллельная группировка операций]]
 
[[Категория:Алгоритмы с избыточными вычислениями]]
 
[[Категория:Алгоритмы с избыточными вычислениями]]
 +
 +
[[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