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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 1: Строка 1:
'''Последовательно-параллельный вариант решения с LU-разложением и обратными подстановками''' - один из вариантов замены [[Прогонка, точечный вариант|прогонки]] в приложении к решению трёхдиагональной СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида <math>Ax = b</math>, где  
+
'''Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками''' - один из вариантов замены [[Прогонка, точечный вариант|прогонки]] в приложении к решению трёхдиагональной СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида <math>Ax = b</math>, где  
 
:<math>
 
:<math>
 
A = \begin{bmatrix}
 
A = \begin{bmatrix}

Версия 20:54, 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 г.