Problem level

Difference between revisions of "Methods for solving tridiagonal SLAEs"

From Algowiki
Jump to navigation Jump to search
[unchecked revision][unchecked revision]
Line 41: Line 41:
 
==== Method with a sub-linear execution time ====
 
==== Method with a sub-linear execution time ====
 
===== Serial-parallel variant for solving tri-diagonal SLAEs via the ''LU''-decomposition and the substitution process =====
 
===== Serial-parallel variant for solving tri-diagonal SLAEs via the ''LU''-decomposition and the substitution process =====
−
The [[serial-parallel variant for solving tri-diagonal SLAEs via the LU-decomposition and the substitution process]] was proposed in [http://russianscdays.org/node/28 2015]<ref name="FAV">А.В.Фролов. Ещё один метод распараллеливания прогонки с использованием ассоциативности операций // Суперкомпьютерные дни в России: Труды международной конференции (28-29 сентября 2015 г., г. Москва). – М.: Изд-во МГУ, 2015. с. 151-162</ref> as an alternative to other parallel algorithms for solving tri-diagonal SLAEs. Similarly to the Stone algorithm, this method is based on <math>LU</math>-decomposition of the matrix of the original SLAE and the use of the associativity of matrix multiplication. The method consists of two significantly different parts, namely, [[Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы|serial-parallel algorithm for the LU-decomposition of a tri-diagonal matrix]] and [[Последовательно-параллельный вариант обратной подстановки|serial-parallel variant of the back substitution]]. Первая из частей метода спроектирована с использованием нормировки, что делает область устойчивости метода гораздо шире, чем у рекурсивного сдваивания Стоуна. В то же время строгое исследование области устойчивости пока не проведено. Как и алгоритм Стоуна, имеет ограниченную применимость для блочно-трёхдиагональной реализации.
+
The [[serial-parallel variant for solving tri-diagonal SLAEs via the LU-decomposition and the substitution process]] was proposed in [http://russianscdays.org/node/28 2015]<ref name="FAV">А.В.Фролов. Ещё один метод распараллеливания прогонки с использованием ассоциативности операций // Суперкомпьютерные дни в России: Труды международной конференции (28-29 сентября 2015 г., г. Москва). – М.: Изд-во МГУ, 2015. с. 151-162</ref> as an alternative to other parallel algorithms for solving tri-diagonal SLAEs. Similarly to the Stone algorithm, this method is based on <math>LU</math>-decomposition of the matrix of the original SLAE and the use of the associativity of matrix multiplication. The method consists of two significantly different parts: [[Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы|serial-parallel algorithm for the LU-decomposition of a tri-diagonal matrix]] and [[Последовательно-параллельный вариант обратной подстановки|serial-parallel variant of the back substitution]]. The first part is designed so that to use normalization, which considerably expands the stability region of the method compared to the Stone recursive doubling. On the other hand, a rigorous analysis of the stability region has not so far been carried out. Similarly to the Stone algorithm, the method has a restricted applicability to block tri-diagonal implementations.
  
 
=== Другие методы ===
 
=== Другие методы ===

Revision as of 11:38, 27 October 2017


1 SLAEs with tri-diagonal matrices

Numerous mathematical models of one-dimensional phenomena can be reduced to solving systems of linear algebraic equations (SLAEs) [1][2] [math]Ax = b[/math] with tri-diagonal matrices

[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]

2 Methods for solving SLAEs with tri-diagonal matrices

Here, we review various methods for solving SLAEs with tri-diagonal matrices.

2.1 Methods based on the conventional LU-decomposition of a tri-diagonal matrix A into the product of two bi-diagonal matrices

Several methods are based on the LU-decomposition of the matrix of the original system and the subsequent solution of the resulting bi-diagonal SLAEs. If a new SLAE with the already decomposed matrix should be solved, then this approach makes it possible not to repeat the decomposition but only solve bi-diagonal SLAEs.

2.1.1 Methods with linear execution time

2.1.1.1 Thomas algorithms
2.1.1.1.1 Monotone Thomas algorithm

Monotone Thomas algorithm[3] is a serial algorithm for solving tri-diagonal SLAEs. This is a particular case of the general elimination method, which received a special name due to the broad propagation of such systems in applied problems. According to the mathematical literature [3], an application of the Thomas algorithm consists in the successive solution of two problems: the [math]LU[/math]-decomposition of a tri-diagonal matrix [math]A[/math] into the product of two bi-diagonal systems by using the compact scheme of Gaussian elimination and then the solution of two SLAEs with bi-diagonal matrices by using the conventional forward and backward substitution. The method is almost serial (except for the possibility to solve the first bi-diagonal system almost in parallel with the decomposition of the tri-diagonal matrix). If the algorithm is used again for solving a new SLAE with the same matrix, then it becomes completely serial.

2.1.1.1.2 Two-sided Thomas algorithm

Two-sided Thomas algorithm [3] is also a particular case of the general elimination method. It combines the basic Thomas algorithm with the idea of eliminating the unknowns simultaneously from the top end and lower end of a SLAE (which explains the name of the method).

2.1.2 Method with the logarithmic execution time

2.1.2.1 Stone doubling algorithm

Stone doubling algorithm[4][5] was developed in the early seventies of the XX century. Similarly to the Thomas algorithm, which it was designed to replace, the Stone doubling algorithm for solving SLAEs with tri-diagonal matrices consists of two separate parts, namely, the Stone doubling algorithm for the LU-decomposition of a tri-diagonal matrix and the Stone doubling method for solving bi-diagonal SLAEs. For a number of reasons presented at the corresponding pages, the former method is not used in practice, while the latter is little popular.

2.1.3 Method with a sub-linear execution time

2.1.3.1 Serial-parallel variant for solving tri-diagonal SLAEs via the LU-decomposition and the substitution process

The serial-parallel variant for solving tri-diagonal SLAEs via the LU-decomposition and the substitution process was proposed in 2015[6] as an alternative to other parallel algorithms for solving tri-diagonal SLAEs. Similarly to the Stone algorithm, this method is based on [math]LU[/math]-decomposition of the matrix of the original SLAE and the use of the associativity of matrix multiplication. The method consists of two significantly different parts: serial-parallel algorithm for the LU-decomposition of a tri-diagonal matrix and serial-parallel variant of the back substitution. The first part is designed so that to use normalization, which considerably expands the stability region of the method compared to the Stone recursive doubling. On the other hand, a rigorous analysis of the stability region has not so far been carried out. Similarly to the Stone algorithm, the method has a restricted applicability to block tri-diagonal implementations.

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

Эта часть методов не основана на LU-разложении исходной матрицы системы. Тем не менее, в каждом из методов есть такая (особенная для каждого метода) часть, которая зависит только от элементов матрицы систем. Её при повторных решениях СЛАУ с той же матрицей можно использовать уже ранее вычисленную. Это делает повторные решения довольно экономичными.

2.2.1 Методы с логарифмическим или полулогарифмическим временем решения

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

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

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

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

2.2.2 Методы с меньшим линейного временем решения

2.2.2.1 Метод редукции

Метод редукции нециклического вида, несмотря на то, что известен давно[10], обычно рассматривается как "недоделка" циклической редукции, а не самостоятельный параллельный алгоритм, в частности, из-за избыточных вычислений. Вместе с тем для большей сбалансированности и меньших простоев оборудования именно нециклическая редукция должна рассматриваться как предпочтительная[11].

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

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

3 References

  1. ↑ Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
  2. ↑ Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
  3. ↑ 3.0 3.1 3.2 Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 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. ↑ 6.0 6.1 А.В.Фролов. Ещё один метод распараллеливания прогонки с использованием ассоциативности операций // Суперкомпьютерные дни в России: Труды международной конференции (28-29 сентября 2015 г., г. Москва). – М.: Изд-во МГУ, 2015. с. 151-162
  7. ↑ Buneman O. A Compact Non-iterative Poisson Solver // Rep. 294, Inst. for Plasma Res., Stanford U., Stanford, Calif., 1969.
  8. ↑ 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.
  9. ↑ 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
  10. ↑ Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Главная редакция физико-математической литературы, 1985г. ,208 с.
  11. ↑ А.В.Фролов "Нециклическая редукция - незаслуженно забытый метод?" // Параллельные вычислительные технологии (ПаВТ'2016): труды международной научной конференции (г. Архангельск, 28 марта - 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 800.
  12. ↑ А.В.Попов. Решение задач линейной алгебры с разреженными симметричными матрицами на MIMD-компьютере // Искусственный интеллект (Донецк). — 2006, №4, с. 670-679
Retrieved from "https://algowiki-project.org/algowiki/en/index.php?title=Methods_for_solving_tridiagonal_SLAEs&oldid=834"