Methods for solving tridiagonal SLAEs

1 SLAEs with tri-diagonal matrices

Numerous mathematical models of one-dimensional phenomena can be reduced to solving systems of linear algebraic equations (SLAEs) [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 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 , 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 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 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 as an alternative to other parallel algorithms for solving tri-diagonal SLAEs. Similarly to the Stone algorithm, the method is based on [math]LU[/math]-decomposition of the matrix of the original SLAE and the use of the associativity of matrix multiplication. и состоит из двух существенно различных по свойствам частей: последовательно-параллельного алгоритма для LU-разложения трёхдиагональной матрицы и последовательно-параллельного варианта обратной подстановки. Первая из частей метода спроектирована с использованием нормировки, что делает область устойчивости метода гораздо шире, чем у рекурсивного сдваивания Стоуна. В то же время строгое исследование области устойчивости пока не проведено. Как и алгоритм Стоуна, имеет ограниченную применимость для блочно-трёхдиагональной реализации.

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

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

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

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

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

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

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

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

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

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

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

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