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 algoruthm

Two-sided Thomas algoruthm is also a particular case тоже является частным случаем общего метода исключения неизвестных. Получена из алгоритмов монотонной прогонки за счёт идеи встречного (откуда и её название) исключения неизвестных в уравнениях "с начала" и "с конца" СЛАУ.

2.1.2 Метод с логарифмическим временем вычислений

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

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

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

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

Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками предложен в 2015 г. в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ. Как и метод Стоуна, основан на [math]LU[/math]-разложении матрицы исходной СЛАУ с использованием ассоциативности операции матричного умножения и состоит из двух существенно различных по свойствам частей: последовательно-параллельного алгоритма для 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-разложением и обратными подстановками в ответ на замечание рецензента о схожести его схемы с методом окаймления автором было вставлено замечание о разных структурах образующихся разложений.