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, 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 Other methods

Methods of this group are not based on the LU-decomposition of the original coefficient matrix. Nevertheless, each of these methods has a section (different for different methods) that depends only on the entries of the coefficient matrix. If a new SLAE with the same matrix has to be solved, then this section may be used with no additional calculations, which makes repeated solutions fairly economical.

2.2.1 Methods with logarithmic or semi-logarithmic execution time

2.2.1.1 Cyclic reduction method

Diverse versions of the Cyclic reduction method originate at the turn of the 60's and 70's of the XX century и до настоящего времени является, пожалуй, самым популярным из параллельных замен метода прогонки. Несмотря на то, что для распараллеливания в нём использованы избыточные по сравнению с прогонкой вычисления, пригоден как для решения одиночных СЛАУ, так и для многих СЛАУ с одной и той же матрицей. Диапазон устойчивости находится в тех же границах, что и у классической прогонки; существует и блочный аналог метода.

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

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

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

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

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

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

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