Problem level

Difference between revisions of "Methods for solving tridiagonal SLAEs"

From Algowiki
Jump to navigation Jump to search
[unchecked revision][quality revision]
 
(38 intermediate revisions by 2 users not shown)
Line 2: Line 2:
 
== SLAEs with tri-diagonal matrices ==
 
== 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  
+
Numerous mathematical models of one-dimensional phenomena can be reduced to solving systems of linear algebraic equations (SLAEs) <ref>Voevodin V.V. Computational foundations of linear algebra Moscow: Nauka, 1977.</ref><ref>Voevodin V.V., Kuznetsov Yu.A. Matrices and computations, Moscow: Nauka, 1984.</ref> <math>Ax = b</math> with tri-diagonal matrices  
 
:<math>
 
:<math>
 
A = \begin{bmatrix}
 
A = \begin{bmatrix}
Line 27: Line 27:
 
====== Monotone Thomas algorithm ======
 
====== Monotone Thomas algorithm ======
  
−
[[Прогонка, точечный вариант|Монотонная прогонка]]<ref name="setki">Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.</ref> – последовательный алгоритм решения трёхдиагональной СЛАУ – является частным случаем общего метода исключения неизвестных, однако получила специальное название из-за распространённости задач такого типа в прикладных исследованиях. В математической литературе<ref name="setki" /> указано, что применение метода прогонки эквивалентно последовательному решению двух задач: <math>LU</math>-разложению трёхдиагональной матрицы <math>A</math> на две двухдиагональные с помощью [[Компактная схема метода Гаусса для трёхдиагональной матрицы, последовательный вариант|компактной схемы метода Гаусса]] и затем решению двух СЛАУ с двухдиагональными матрицами с помощью обычной [[Прямая и обратная подстановка в СЛАУ с двухдиагональной матрицей|подстановки]]. Метод почти последователен (исключением является то, что решение первой из двухдиагональных СЛАУ можно выполнять почти параллельно с разложением трёхдиагональной матрицы). При повторении прогонки для новой СЛАУ с той же матрицей алгоритм [[Повторная прогонка, точечный вариант|повторной прогонки]] полностью последователен.
+
[[Прогонка, точечный вариант|Monotone Thomas algorithm]]<ref name="setki">A.A.Samarskij, E.S.Nikolaev. Numerical Methods for Grid Equations. Springer, 1989.</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]]. 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.
  
−
====== Встречная прогонка ======
+
====== Two-sided Thomas algorithm ======
  
−
[[Встречная прогонка, точечный вариант|Встречная прогонка]]<ref name="setki" /> - тоже является частным случаем общего метода исключения неизвестных. Получена из алгоритмов монотонной прогонки за счёт идеи встречного (откуда и её название) исключения неизвестных в уравнениях "с начала" и "с конца" СЛАУ.
+
[[Встречная прогонка, точечный вариант|Two-sided Thomas algorithm ]]<ref name="setki" /> 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).
  
−
==== Метод с логарифмическим временем вычислений ====
+
==== Method with the logarithmic execution time ====
  
−
===== Метод сдваивания Стоуна =====
+
===== Stone doubling algorithm =====
  
−
[[Метод сдваивания Стоуна]]<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-разложения трёхдиагональной матрицы]] и  [[Метод сдваивания Стоуна для решения двудиагональных СЛАУ|метода сдваивания Стоуна для решения двудиагональных СЛАУ]]. По ряду причин, изложенных на соответствующих страницах, первый из них не применяется на практике, а второй - малораспространён.
+
[[Stone doubling algorithm]]<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> 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 [[Алгоритм сдваивания Стоуна для LU-разложения трёхдиагональной матрицы|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.
  
−
==== Метод с временем вычислений меньше линейного ====
+
==== Method with a sub-linear execution time ====
−
===== Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с ''LU''-разложением и обратными подстановками =====
+
===== Serial-parallel variant for solving tri-diagonal SLAEs via the ''LU''-decomposition and the substitution process =====
−
[[Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками]] предложен [http://russianscdays.org/node/28 в 2015 г.]<ref name="FAV">А.В.Фролов. Ещё один метод распараллеливания прогонки с использованием ассоциативности операций // Суперкомпьютерные дни в России: Труды международной конференции (28-29 сентября 2015 г., г. Москва). – М.: Изд-во МГУ, 2015. с. 151-162</ref> в качестве альтернативы другим параллельным алгоритмам решения трёхдиагональных СЛАУ. Как и метод Стоуна, основан на <math>LU</math>-разложении матрицы исходной СЛАУ с использованием ассоциативности операции матричного умножения и состоит из двух существенно различных по свойствам частей: [[Последовательно-параллельный алгоритм для LU-разложения трёхдиагональной матрицы|последовательно-параллельного алгоритма для LU-разложения трёхдиагональной матрицы]] и [[Последовательно-параллельный вариант обратной подстановки|последовательно-параллельного варианта обратной подстановки]]. Первая из частей метода спроектирована с использованием нормировки, что делает область устойчивости метода гораздо шире, чем у рекурсивного сдваивания Стоуна. В то же время строгое исследование области устойчивости пока не проведено. Как и алгоритм Стоуна, имеет ограниченную применимость для блочно-трёхдиагональной реализации.
+
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.
  
−
=== Другие методы ===
+
=== Other methods ===
  
−
Эта часть методов не основана на LU-разложении исходной матрицы системы. Тем не менее, в каждом из методов есть такая (особенная для каждого метода) часть, которая зависит только от элементов матрицы систем. Её при повторных решениях СЛАУ с той же матрицей можно использовать уже ранее вычисленную. Это делает повторные решения довольно экономичными.   
+
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.   
  
−
==== Методы с логарифмическим или полулогарифмическим временем решения ====
+
==== Methods with logarithmic or semi-logarithmic execution time ====
  
−
===== Метод циклической редукции =====
+
===== Cyclic reduction method =====
−
[[Метод циклической редукции]] впервые появился в разных вариациях на рубеже 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" /> и до настоящего времени является, пожалуй, самым популярным из параллельных замен метода прогонки. Несмотря на то, что для распараллеливания в нём использованы избыточные по сравнению с прогонкой вычисления, пригоден как для решения одиночных СЛАУ, так и для многих СЛАУ с одной и той же матрицей. Диапазон устойчивости находится в тех же границах, что и у классической прогонки; существует и блочный аналог метода.
+
Diverse versions of the [[Cyclic reduction method]] originate at the turn of the 60's and 70's of the XX century <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" />. Until now, the method seems to be the most popular one among parallel substitutes of the Thomas algorithm. Despite the fact that additional calculations are used compared to the Thomas algorithm, the method can be applied to solving both individual SLAEs and numerous SLAEs with the same coefficient matrix. The range of stability is the same as that of the classical Thomas algorithm. There also exist block versions of the method.
  
−
===== Метод дихотомии =====
+
===== Dichotomy method =====
−
[[Метод дихотомии]] предложен в 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)'' выполняется при подготовительной работе на каждом из процессоров.
+
The [[dichotomy method]] was proposed in 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>. The method is mainly intended for solving multiple SLAEs with the same tri-diagonal coefficient matrix. It is too laborious for solving individual tri-diagonal SLAEs because ''O(n)'' operations must be performed by each processor at the preparatory stage of the method.
  
−
==== Методы с меньшим линейного временем решения ====
+
==== Methods with a sub-linear execution time ====
  
−
===== Метод редукции =====
+
===== Reduction method =====
  
−
[[Метод редукции]] нециклического вида, несмотря на то, что известен давно<ref name="IK">Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Главная редакция физико-математической литературы, 1985г. ,208 с.</ref>, обычно рассматривается как "недоделка" циклической редукции, а не самостоятельный параллельный алгоритм, в частности, из-за избыточных вычислений. Вместе с тем для большей сбалансированности и меньших простоев оборудования именно нециклическая редукция должна рассматриваться как предпочтительная<ref>А.В.Фролов "Нециклическая редукция - незаслуженно забытый метод?" // Параллельные вычислительные технологии (ПаВТ'2016): труды международной научной конференции (г. Архангельск, 28 марта - 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 800.</ref>.
+
Although long known <ref name="IK">Ilyin, V. P. and Kuznetsov, Yu. I.Tridiagonal matrices and their applications. Nauka, Moscow, 1985.</ref>, the noncyclic [[reduction method]] is usually regarded as a deficient version of the cyclic reduction rather than a separate parallel algorithm. One of the reasons is the presence of some extra calculations. Meanwhile, it is the noncyclic reduction that should be considered as a preferable method if the goal is to achieve better balance and lesser idleness time. <ref>А.В.Фролов "Нециклическая редукция - незаслуженно забытый метод?" // Параллельные вычислительные технологии (ПаВТ'2016): труды международной научной конференции (г. Архангельск, 28 марта - 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 800.</ref>.
  
−
===== Метод окаймления =====
+
===== Bordering method =====
−
[[Метод окаймления]] по своей идее восходит к применению принципа "разделяй и властвуй", аналоги для ленточных матриц появились ещё в 2006г.<ref>А.В.Попов. Решение задач линейной алгебры с разреженными симметричными матрицами на MIMD-компьютере // Искусственный интеллект (Донецк). — 2006, №4, с. 670-679</ref>, а, возможно, и ранее. Позже, при выходе публикации про [[Последовательно-параллельный вариант решения трёхдиагональной СЛАУ с LU-разложением и обратными подстановками]] в ответ на замечание рецензента о схожести его схемы с методом окаймления автором было вставлено замечание о разных структурах образующихся разложений<ref name="FAV" />.
+
The idea of the [[bordering method]] originates from the "divide and conquer" principle. Versions of this method designed for band matrices emerge in 2006 <ref>A.V. Popov. Solution of linear algebra problems with sparse symmetric matrices on the MIMD-computer // Artificial Intelligence (Donetsk). - 2006, №4, p. 670-679</ref> and, possibly, even earlier. When the text [[Serial-parallel variant of solving tri-diagonal SLAEs via the LU-decomposition and the substitution process]] was published, the reviewer noted the similarity between the proposed scheme and the bordering method. In <ref name="FAV" />, the author replied that the decompositions constructed by these two methods have different structures.
  
 
== References ==
 
== References ==
Line 68: Line 68:
 
<references />
 
<references />
  
−
[[Category:Started articles]]
+
[[Category:Finished articles]]
  
 
[[Ru:Методы решения СЛАУ с трёхдиагональными матрицами]]
 
[[Ru:Методы решения СЛАУ с трёхдиагональными матрицами]]

Latest revision as of 15:32, 9 November 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 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 [7][8][5]. Until now, the method seems to be the most popular one among parallel substitutes of the Thomas algorithm. Despite the fact that additional calculations are used compared to the Thomas algorithm, the method can be applied to solving both individual SLAEs and numerous SLAEs with the same coefficient matrix. The range of stability is the same as that of the classical Thomas algorithm. There also exist block versions of the method.

2.2.1.2 Dichotomy method

The dichotomy method was proposed in 2010 [9]. The method is mainly intended for solving multiple SLAEs with the same tri-diagonal coefficient matrix. It is too laborious for solving individual tri-diagonal SLAEs because O(n) operations must be performed by each processor at the preparatory stage of the method.

2.2.2 Methods with a sub-linear execution time

2.2.2.1 Reduction method

Although long known [10], the noncyclic reduction method is usually regarded as a deficient version of the cyclic reduction rather than a separate parallel algorithm. One of the reasons is the presence of some extra calculations. Meanwhile, it is the noncyclic reduction that should be considered as a preferable method if the goal is to achieve better balance and lesser idleness time. [11].

2.2.2.2 Bordering method

The idea of the bordering method originates from the "divide and conquer" principle. Versions of this method designed for band matrices emerge in 2006 [12] and, possibly, even earlier. When the text Serial-parallel variant of solving tri-diagonal SLAEs via the LU-decomposition and the substitution process was published, the reviewer noted the similarity between the proposed scheme and the bordering method. In [6], the author replied that the decompositions constructed by these two methods have different structures.

3 References

  1. ↑ Voevodin V.V. Computational foundations of linear algebra Moscow: Nauka, 1977.
  2. ↑ Voevodin V.V., Kuznetsov Yu.A. Matrices and computations, Moscow: Nauka, 1984.
  3. ↑ 3.0 3.1 3.2 A.A.Samarskij, E.S.Nikolaev. Numerical Methods for Grid Equations. Springer, 1989.
  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. ↑ Ilyin, V. P. and Kuznetsov, Yu. I.Tridiagonal matrices and their applications. Nauka, Moscow, 1985.
  11. ↑ А.В.Фролов "Нециклическая редукция - незаслуженно забытый метод?" // Параллельные вычислительные технологии (ПаВТ'2016): труды международной научной конференции (г. Архангельск, 28 марта - 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 800.
  12. ↑ A.V. Popov. Solution of linear algebra problems with sparse symmetric matrices on the MIMD-computer // Artificial Intelligence (Donetsk). - 2006, №4, p. 670-679
Retrieved from "https://algowiki-project.org/algowiki/en/index.php?title=Methods_for_solving_tridiagonal_SLAEs&oldid=1031"