View source for Methods for solving tridiagonal SLAEs

{{level-p}}
== SLAEs with tri-diagonal matrices ==

Numerous mathematical models of one-dimensional phenomena can be reduced to solving systems of linear algebraic equations (SLAEs) <ref>Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref>Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> <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>

== Methods for solving SLAEs with tri-diagonal matrices ==

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

=== 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. 
==== Methods with linear execution time ==== 

===== Thomas algorithms =====

====== Monotone Thomas algorithm ======

[[Прогонка, точечный вариант|Monotone Thomas algorithm]]<ref name="setki">Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.</ref> 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 <ref name="setki" />, 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 for tri-diagonal matrices, serial variant компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант|compact scheme of Gaussian elimination]] and then the solution of two SLAEs with bi-diagonal matrices by using the conventional forward and backward [[Прямая и обратная подстановка в СЛАУ с двухдиагональной матрицей|substitution]]. Метод почти последователен (исключением является то, что решение первой из двухдиагональных СЛАУ можно выполнять почти параллельно с разложением трёхдиагональной матрицы). При повторении прогонки для новой СЛАУ с той же матрицей алгоритм [[Повторная прогонка, точечный вариант|повторной прогонки]] полностью последователен.

====== Встречная прогонка ======

[[Встречная прогонка, точечный вариант|Встречная прогонка]]<ref name="setki" /> - тоже является частным случаем общего метода исключения неизвестных. Получена из алгоритмов монотонной прогонки за счёт идеи встречного (откуда и её название) исключения неизвестных в уравнениях "с начала" и "с конца" СЛАУ.

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

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

[[Метод сдваивания Стоуна]]<ref>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.</ref><ref name="Stone 2">Stone H.S. Parallel Tridiagonal Equation Solvers // ACM Trans. on Math. Software, Vol. 1, No. 4 (Dec. 1975), P. 289-307.</ref> разработан в начале 70-х гг. 20го века. Как и [[Прогонка|прогонка]], которую он должен был заменить, [[Метод сдваивания Стоуна|метод сдваивания Стоуна для решения СЛАУ с трёхдиагональными матрицами]] состоит из двух отдельно разработанных частей: [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы|алгоритма сдваивания Стоуна для LU-разложения трёхдиагональной матрицы]] и  [[Метод сдваивания Стоуна для решения двудиагональных СЛАУ|метода сдваивания Стоуна для решения двудиагональных СЛАУ]]. По ряду причин, изложенных на соответствующих страницах, первый из них не применяется на практике, а второй - малораспространён.

==== Метод с временем вычислений меньше линейного ====
===== Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с ''LU''-разложением и обратными подстановками =====
[[Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками]] предложен [http://russianscdays.org/node/28 в 2015 г.]<ref name="FAV">А.В.Фролов. Ещё один метод распараллеливания прогонки с использованием ассоциативности операций // Суперкомпьютерные дни в России: Труды международной конференции (28-29 сентября 2015 г., г. Москва). – М.: Изд-во МГУ, 2015. с. 151-162</ref> в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ. Как и метод Стоуна, основан на <math>LU</math>-разложении матрицы исходной СЛАУ с использованием ассоциативности операции матричного умножения и состоит из двух существенно различных по свойствам частей: [[Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы|последовательно-параллельного алгоритма для LU-разложения трёхдиагональной матрицы]] и [[Последовательно-параллельный вариант обратной подстановки|последовательно-параллельного варианта обратной подстановки]]. Первая из частей метода спроектирована с использованием нормировки, что делает область устойчивости метода гораздо шире, чем у рекурсивного сдваивания Стоуна. В то же время строгое исследование области устойчивости пока не проведено. Как и алгоритм Стоуна, имеет ограниченную применимость для блочно-трёхдиагональной реализации.

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

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

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

===== Метод циклической редукции =====
[[Метод циклической редукции]] впервые появился в разных вариациях на рубеже 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" /> и до настоящего времени является, пожалуй, самым популярным из параллельных замен метода прогонки. Несмотря на то, что для распараллеливания в нём использованы избыточные по сравнению с прогонкой вычисления, пригоден как для решения одиночных СЛАУ, так и для многих СЛАУ с одной и той же матрицей. Диапазон устойчивости находится в тех же границах, что и у классической прогонки; существует и блочный аналог метода.

===== Метод дихотомии =====
[[Метод дихотомии]] предложен в 2010 г.<ref>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</ref> и предназначен в основном для решения большого количества СЛАУ с одной и той же трёхдиагональной матрицей. Для решения одиночных трёхдиагональных СЛАУ слишком тяжеловесен, в силу того, что количество операций ''O(n)'' выполняется при подготовительной работе на каждом из процессоров.

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

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

[[Метод редукции]] нециклического вида, несмотря на то, что известен давно<ref name="IK">Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Главная редакция физико-математической литературы, 1985г. ,208 с.</ref>, обычно рассматривается как "недоделка" циклической редукции, а не самостоятельный параллельный алгоритм, в частности, из-за избыточных вычислений. Вместе с тем для большей сбалансированности и меньших простоев оборудования именно нециклическая редукция должна рассматриваться как предпочтительная<ref>А.В.Фролов "Нециклическая редукция - незаслуженно забытый метод?" // Параллельные вычислительные технологии (ПаВТ'2016): труды международной научной конференции (г. Архангельск, 28 марта - 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 800.</ref>.

===== Метод окаймления =====
[[Метод окаймления]] по своей идее восходит к применению принципа "разделяй и властвуй", аналоги для ленточных матриц появились ещё в 2006г.<ref>А.В.Попов. Решение задач линейной алгебры с разреженными симметричными матрицами на MIMD-компьютере // Искусственный интеллект (Донецк). — 2006, №4, с. 670-679</ref>, а, возможно, и ранее. Позже, при выходе публикации про [[Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками]] в ответ на замечание рецензента о схожести его схемы с методом окаймления автором было вставлено замечание о разных структурах образующихся разложений<ref name="FAV" />.

== References ==

<references />

[[Category:Started articles]]

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