Методы решения СЛАУ с трёхдиагональными матрицами: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[выверенная версия][выверенная версия]
Строка 29: Строка 29:
  
 
==== Метод циклической редукции ====
 
==== Метод циклической редукции ====
[[Метод циклической редукции]] впервые появился в разных вариациях на рубеже 60-70-х гг. XX века<ref>Buneman O. A Compact Non-iterative Poisson Solver // Rep. 294, Inst. for Plasma Res., Stanford U., Stanford, Calif., 1969.</ref><ref>Buzbee B.L., Golub G.H., Nielson C.W. On Direct Methods for Solving Poisson's Equations // SIAM J. Numer. Anal., Vol. 7, No. 4 (Dec. 1970), P. 627-656.</ref><ref name="Stone 2" /> и до настоящего времени является, пожалуй, самым популярным из параллельных замен метода прогонки. Несмотря на то, что для распараллеливания в нём присутствуют избыточные вычисления, пригоден как для решения одиночных СЛАУ, так и для многих СЛАУ с одной и той же матрицей. Диапазон устойчивости находится в тех же границах, что и у классической прогонки; существует и блочный аналог метода.
+
[[Метод циклической редукции]] впервые появился в разных вариациях на рубеже 60-70-х гг. XX века<ref>Buneman O. A Compact Non-iterative Poisson Solver // Rep. 294, Inst. for Plasma Res., Stanford U., Stanford, Calif., 1969.</ref><ref>Buzbee B.L., Golub G.H., Nielson C.W. On Direct Methods for Solving Poisson's Equations // SIAM J. Numer. Anal., Vol. 7, No. 4 (Dec. 1970), P. 627-656.</ref><ref name="Stone 2" /> и до настоящего времени является, пожалуй, самым популярным из параллельных замен метода прогонки. Несмотря на то, что для распараллеливания в нём использованы избыточные по сравнению с прогонкой вычисления, пригоден как для решения одиночных СЛАУ, так и для многих СЛАУ с одной и той же матрицей. Диапазон устойчивости находится в тех же границах, что и у классической прогонки; существует и блочный аналог метода.
  
 
==== Метод дихотомии ====
 
==== Метод дихотомии ====

Версия 16:38, 7 сентября 2015

1 Методы решения СЛАУ с трёхдиагональными матрицами

Во многих математических моделях удаётся свести задачу к СЛАУ[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} [/math]

На этой странице представлены разные методы решения такой СЛАУ.

1.1 Методы, основанные на стандартном [math]LU[/math]-разложении трёхдиагональной матрицы [math]A[/math] на две двухдиагональные

1.1.1 Метод прогонки

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

1.1.2 Метод сдваивания Стоуна

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

1.1.3 Последовательно-параллельный вариант прогонки

1.2 Другие методы

1.2.1 Метод циклической редукции

Метод циклической редукции впервые появился в разных вариациях на рубеже 60-70-х гг. XX века[6][7][5] и до настоящего времени является, пожалуй, самым популярным из параллельных замен метода прогонки. Несмотря на то, что для распараллеливания в нём использованы избыточные по сравнению с прогонкой вычисления, пригоден как для решения одиночных СЛАУ, так и для многих СЛАУ с одной и той же матрицей. Диапазон устойчивости находится в тех же границах, что и у классической прогонки; существует и блочный аналог метода.

1.2.2 Метод дихотомии

Метод дихотомии предложен в 2010 г.[8] и предназначен в основном для решения большого количества СЛАУ с одной и той же трёхдиагональной матрицей. Для решения одиночных трёхдиагональных СЛАУ слишком тяжеловесен, в силу того, что количество операций O(n) выполняется при подготовительной работе на каждом из процессоров.

1.2.3 Метод окаймления

Метод окаймления

2 Литература

  1. Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
  2. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
  3. 3,0 3,1 Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.
  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. 5,0 5,1 Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.
  6. Buneman O. A Compact Non-iterative Poisson Solver // Rep. 294, Inst. for Plasma Res., Stanford U., Stanford, Calif., 1969.
  7. Buzbee B.L., Golub G.H., Nielson C.W. On Direct Methods for Solving Poisson's Equations // SIAM J. Numer. Anal., Vol. 7, No. 4 (Dec. 1970), P. 627-656.
  8. Terekhov Andrew. Parallel dichotomy algorithm for solving tridiagonal system of linear equations with multiple right-hand sides. // Parallel Comput. 2010. Vol. 36. N. 8. pp. 423–438