Difference between revisions of "Methods for solving tridiagonal SLAEs"
| [unchecked revision] | [quality revision] |
| (26 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> | + | 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 ====== | ||
| − | [[Прогонка, точечный вариант|Monotone Thomas algorithm]]<ref name="setki"> | + | [[Прогонка, точечный вариант|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 ====== | ====== Two-sided Thomas algorithm ====== | ||
| Line 35: | Line 35: | ||
==== Method with the logarithmic execution time ==== | ==== Method with the logarithmic execution time ==== | ||
| − | ===== | + | ===== Stone doubling algorithm ===== |
| − | [[ | + | [[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 ==== |
| − | ===== | + | ===== 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 [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 === |
| − | + | 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 ===== |
| − | [[ | + | 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 ===== |
| − | [[ | + | 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 ===== |
| − | + | 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 ===== |
| − | [[ | + | 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: | + | [[Category:Finished articles]] |
[[Ru:Методы решения СЛАУ с трёхдиагональными матрицами]] | [[Ru:Методы решения СЛАУ с трёхдиагональными матрицами]] | ||
Latest revision as of 15:32, 9 November 2017
Contents
- 1 SLAEs with tri-diagonal matrices
- 2 Methods for solving SLAEs with tri-diagonal matrices
- 3 References
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
- ↑ Voevodin V.V. Computational foundations of linear algebra Moscow: Nauka, 1977.
- ↑ Voevodin V.V., Kuznetsov Yu.A. Matrices and computations, Moscow: Nauka, 1984.
- ↑ 3.0 3.1 3.2 A.A.Samarskij, E.S.Nikolaev. Numerical Methods for Grid Equations. Springer, 1989.
- ↑ 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.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.0 6.1 А.В.Фролов. Ещё один метод распараллеливания прогонки с использованием ассоциативности операций // Суперкомпьютерные дни в России: Труды международной конференции (28-29 сентября 2015 г., г. Москва). – М.: Изд-во МГУ, 2015. с. 151-162
- ↑ Buneman O. A Compact Non-iterative Poisson Solver // Rep. 294, Inst. for Plasma Res., Stanford U., Stanford, Calif., 1969.
- ↑ 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.
- ↑ 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
- ↑ Ilyin, V. P. and Kuznetsov, Yu. I.Tridiagonal matrices and their applications. Nauka, Moscow, 1985.
- ↑ А.В.Фролов "Нециклическая редукция - незаслуженно забытый метод?" // Параллельные вычислительные технологии (ПаВТ'2016): труды международной научной конференции (г. Архангельск, 28 марта - 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 800.
- ↑ A.V. Popov. Solution of linear algebra problems with sparse symmetric matrices on the MIMD-computer // Artificial Intelligence (Donetsk). - 2006, №4, p. 670-679
