Algorithms for Solving Linear Systems of Equations of Tridiagonal Type via Transformations

Abstract

Numeric algorithms for solving the linear systems of tridiagonal type have already existed. The well-known Thomas algorithm is an example of such algorithms. The current paper is mainly devoted to constructing symbolic algorithms for solving tridiagonal linear systems of equations via transformations. The new symbolic algorithms remove the cases where the numeric algorithms fail. The computational cost of these algorithms is given. MAPLE procedures based on these algorithms are presented. Some illustrative examples are given.

Share and Cite:

El-Mikkawy, M. and Atlan, F. (2014) Algorithms for Solving Linear Systems of Equations of Tridiagonal Type via Transformations. Applied Mathematics, 5, 413-422. doi: 10.4236/am.2014.53042.

1. Introduction

Linear systems of equations of tridiagonal type arise in solving problems in a wide variety of disciplines including physics [1,2], mathematics [3-8], engineering [9,10] and others. Many researchers have been devoted to dealing with such systems (see [11-27]). When a system of linear equations has a coefficient matrix of special structure, it is recommended to use a tailor-made algorithm for such systems of equations. The tailor-made algorithms are not only more efficient in terms of computational time and computer memory, but also accumulate smaller round-off errors. As a matter of fact, many problems arising in practice lead to the solution of linear system of equations with special coefficient matrices. The current paper is mainly devoted to developing new algorithms for solving linear system of equations of tridiagonal type of the form:

(1)

where

(2)

and

The coefficient matrix in (2) can be stored in memory locations by using three vectors:

and with This is always a good habit in computation in order to save memory space.

Of course, the non-singularity of the coefficient matrix should be checked firstly to make sure that the system (1) has a non-trivial solution. The DETGTRI algorithm [28] can be used efficiently for this purpose.

Definition 1.1 [29]. The symmetric matrix is called positive definite if and only if

Theorem 1.2 [29]. The symmetric matrix is positive definite if and only if any of the following conditions is satisfied:

1) has only positive eigenvalues.

2)

In particular, the author in [30] proved that for the tridiagonal matrix (2), it is true that provided that Thus the tridiagonal matrix (2) is positive definite if and only if This is an easy way to check weather a tridiagonal matrix is positive definite or not.

3) can be written as: for a non-singular matrix

Definition 1.3 [29]. An matrix is called diagonally dominant if

and strictly diagonally dominant if

The current paper is organized as follows. In Section 2, new algorithms for solving linear systems of equations of tridiagonal type via transformations are given. In Section 3, concluding remarks are given. MAPLE procedures are given in Section 4. Illustrative examples are presented in Section 5.

Throughout this paper, the word “simplify” means simplifying the expression under consideration to its simplest rational form.

2. Main Results

In this Section, we are going to consider the derivation of new algorithms for solving linear systems of equations of tridiagonal type (1) via transformations. For this purpose it is convenient to introduce three vectors and where

(3)

By using the vectors c, y and z, together with the suitable elementary row operations (ERO’s), we see that the system (1) may be transformed to the equivalent linear system:

(4)

The transformed system (4) is easy to solve by backward substitution. Consequently, the linear system (1) can be solved using the following algorithm:

The Algorithm 2.1, will be referred to as TRANSTRI-I algorithm. The cost of the algorithm is multiplications/divisions and additions/subtractions.

Note that the algorithm TRANSTRI-I works properly only if for all

At this point, it should be mentioned that if the coefficient matrix, of the system (1) is positive definite or diagonally dominant, then the numeric algorithm TRANSTRI-I will never fail.

The following symbolic version algorithm is developed in order to remove the cases where the numeric algorithm TRANSTRI-I fails. The parameter “s” in the algorithm is just a symbolic name. It is a dummy argument and its actual value is zero.

The Algorithm 2.2, will be referred to as TRANSTRI-II algorithm.

In a similar manner, we may consider three vectors and where

(5)

in order to develop a new algorithm.

We are going to focus on the symbolic version only. As in Algorithm 2.1, by using the vectors e, Y and Z, together with the suitable ERO’s, we see that the system (1) may be transformed to the equivalent linear system:

(6)

The transformed system (6) is easy to solve using forward substitution. Therefore the linear system (1) can be solved using the following algorithm:

The Algorithm 2.3, will be referred to as TRANSTRI-III algorithm.

Corollary 2.1. Let be the backward matrix of the tridiagonal matrix in (2), and given by:

(7)

Then the backward tridiagonal linear system

(8)

has the solution: where is the floor function of k and is the solution vector of the linear system (1).

Proof. Consider the permutation matrix defined by:

(9)

For this matrix, we have:

(10)

Since

(11)

Then using (10) and (11), the result follows.

Corollary 2.2. The determinants of the coefficient matrices and in (2) and (7) are given respectively by:

(12)

and

(13)

where and satisfy (3) and (5).

3. Conclusions

There are many numeric algorithms in current use for solving linear systems of tridiagonal type. The Thomas algorithm is the well known numeric algorithm for solving such systems. However, all Thomas and Thomas-like numeric algorithms including the TRANSTRI-I algorithm of the current paper, fail to solve the tridiagonal linear system if for any For example, all these numeric algorithms fail to solve the linear system:

since although its coefficient matrix is invertible and its inverse is the following matrix

The symbolic algorithms TRANSTRI-II and TRANSTRI-III of the current paper are constructed in order to remove the cases where the numeric algorithms fail. These are the only symbolic algorithms for solving linear systems of tridiagonal type. Consequently, we are not going to compare them with numeric algorithms.

4. Computer Programs

In this Section, we are going to introduce MAPLE procedures for solving linear system of tridiagonal type (1). These procedures are based on the algorithms DETGTRI, TRANSTRI-II and TRANSTRI-III. The procedure of Program 1, alters the contents of the vectors and Eventually, the contents of the vectors and are stored in and respectively. The procedure of Program 2, alters the contents of the vectors and Eventually, the contents of the vectors and are stored in and respectively.

5. Illustrative Examples

All results in this section are obtained by executing the MAPLE procedures of Program 1 and Program 2 presented in the previous section.

Example 5.1. Solve the tridiagonal linear system

(14)

Solution: We have

and

By applying the TRANSTRI-I algorithm, we get

• The solution vector is given by:.

Note that the coefficient matrix in (14) is positive definite.

By applying the algorithms TRANSTRI-II and TRANSTRI-III, we obtain the same solution vector.

Example 5.2. Solve the tridiagonal linear system

Solution: Here, we have

and

By applying the TRANSTRI-I algorithm, we get

• The solution vector is given by:.

By using the algorithms TRANSTRI-II and TRANSTRI-III, we obtain the same solution vector.

Example 5.3. Solve the tridiagonal linear system

(15)

Solution: Here, we have

and

The numeric algorithm TRANSTRI-I fails to solve the linear system (15) since Applying the TRANSTRI-II algorithm, it gives:

• The solution vector is given by:

Using the TRANSTRI-III algorithm, it gives the same solution vector.

Acknowledgements

The authors wish to thank anonymous referees and the editorial board for useful comments that enhanced the quality of this paper.

Conflicts of Interest

The authors declare no conflicts of interest.

 [1] G. Y. Hu and R. F. O’Connell, “Analytical Inversion of Symmetric Tridiagonal Matrices,” Journal of Physics A, Vol. 29, No. 7, 1996, pp. 1511-1513. [2] I. Mazilu, D. A. Mazilu and H. T. Williams, “Applications of Tridiagonal Matrices in Non-Equilibrium Statistical Physics,” Electronic Journal of Linear Algebra, Vol. 24, 2012, pp. 7-17. [3] J. A. Marrero, M. Rachidi and V. Tomeo, “Non-Symbolic Algorithms for the Inversion of Tridiagonal Matrices,” Journal of Computational and Applied Mathematics, Vol. 252, 2013, pp. 3-11. http://dx.doi.org/10.1016/j.cam.2012.05.003 [4] Q. Al-Hassan, “On Powers of Tridiagonal Matrices with Nonnegative Entries,” Journal of Applied Mathematical Sciences, Vol. 6, No. 48, 2012, pp. 2357-2368. [5] C. M. da Fonseca and J. Petronilho, “Explicit Inverses of Some Tridiagonal Matrices,” Linear Algebra and Its Applications, Vol. 325, No. 1-3, 2001, pp. 7-21. http://dx.doi.org/10.1016/S0024-3795(00)00289-5 [6] Y. Huang and W. F. McColl, “Analytic Inversion of General Tridiagonal Matrices,” Journal of Physics A, Vol. 30, No. 22, 1997, pp. 7919-7933. http://dx.doi.org/10.1088/0305-4470/30/22/026 [7] A. Kavcic and J. M. F. Moura, “Matrices with Banded Inverses: Inversion Algorithms and Factorization of Gauss-Markov Processes,” IEEE Transactions on Information Theory, Vol. 46, No. 4, 2000, pp. 1495-1509. http://dx.doi.org/10.1109/18.954748 [8] H.-B. Li, T.-Z. Huang, X.-P. Liu and H. Li, “On the Inverses of General Tridiagonal Matrices,” Linear Algebra and Its Applications, Vol. 433, No. 5, 2010, pp. 965-983. http://dx.doi.org/10.1016/j.laa.2010.04.042 [9] A. Martin and I. D. Boyd, “Variant of the Thomas Algorithm for Opposite-Bordered Tridiagonal Systems of Equations,” International Journal for Numerical Methods in Biomedical Engineering, Vol. 26, No. 6, 2010, pp. 752-759. [10] E. Olcayto, “Recursive Formulae for Ladder Network Optimization,” Electronics Letters, Vol. 15, No. 9, 1979, pp. 249-250. http://dx.doi.org/10.1049/el:19790176 [11] T. M. Austin, M. Berndt and J. D. Moulton, “A Memory Efficient Parallel Line Solver,” Submitted to SISC, 2004. [12] J.-J. Climent, L. Tortosa and A. Zamora, “A Note on the Recursive Decoupling Method for Solving Tridiagonal Linear Systems,” Applied Mathematics and Computation, Vol. 140, No. 1, 2003, pp. 159-164. http://dx.doi.org/10.1016/S0096-3003(02)00218-7 [13] O. Egecioglu, C. K. Koc and A. J. Laub, “A Recursive Doubling Algorithm for Solution of Tridiagonal Systems on Hypercube Multiprocessors,” Journal of Computational and Applied Mathematics, Vol. 27, No. 1-2, 1989, pp. 95-108. http://dx.doi.org/10.1016/0377-0427(89)90362-2 [14] M. E. A. El-Mikkawy, “An Algorithm for Solving Tridiagonal Systems,” Journal of Institute of Mathematics and Computer Science Computer Science Series, Vol. 4, No. 2, 1991, pp. 205-210. [15] M. E. A. El-Mikkawy, “On the Inverse of a General Tridiagonal Matrix,” Applied Mathematics and Computation, Vol. 150, No. 3, 2004, pp. 669-679. http://dx.doi.org/10.1016/S0096-3003(03)00298-4 [16] M. E. A. El-Mikkawy, “A New Computational Algorithm for Solving Periodic Tri-Diagonal Linear Systems,” Applied Mathematics and Computation, Vol. 161, No. 2, 2005, pp. 691-696. http://dx.doi.org/10.1016/j.amc.2003.12.114 [17] M. E. A. El-Mikkawy and A. Karawia, “Inversion of General Tridiagonal Matrices,” Applied Mathematics Letters, Vol. 19, No. 8, 2006, pp. 712-720. http://dx.doi.org/10.1016/j.aml.2005.11.012 [18] M. E. A. El-Mikkawy and E.-D. Rahmo, “A New Recursive Algorithm for Inverting General Tridiagonal and Anti-Tridiagonal Matrices,” Applied Mathematics and Computation, Vol. 204, No. 1, 2008, pp. 368-372. http://dx.doi.org/10.1016/j.amc.2008.06.053 [19] M. E. A. El-Mikkawy, “A Generalized Symbolic Thomas Algorithm,” Applied Mathematics, Vol. 3, No. 4, 2012, pp. 342-345. http://dx.doi.org/10.4236/am.2012.34052 [20] D. Fanache, “A Parallel Solution of Tridiagonal Linear Systems by Continued Fractions,” Journal of Arts & Sciences, Vol. 11, No. 1, 2011, pp. 21-30. [21] R. K. Mallik, “The Inverse of a Tridiagonal Matrix,” Linear Algebra and Its Applications, Vol. 325, No. 1-3, 2001, pp. 109-139. http://dx.doi.org/10.1016/S0024-3795(00)00262-7 [22] B. V. Minchev, “Some Algorithms for Solving Special Tridiagonal Block Toeplitz Linear Systems,” Journal of Computational and Applied Mathematics, Vol. 156, No. 1, 2003, pp. 179-200. http://dx.doi.org/10.1016/S0377-0427(02)00911-1 [23] T. Sogabe, “On a Two-Term Recurrence for the Determinant of a General Matrix,” Applied Mathematics and Computation, Vol. 187, No. 2, 2007, pp. 785-788. http://dx.doi.org/10.1016/j.amc.2006.08.156 [24] T. Sugimoto, “On an Inverse Formula of a Tridiagonal Matrix,” Operators and Matrices, Vol. 6, No. 3, 2012, pp. 465-480. http://dx.doi.org/10.7153/oam-06-30 [25] R. Usmani, “Inversion of a Tridiagonal Jacobi Matrix,” Linear Algebra and Its Applications, Vol. 212-213, 1994, pp. 413-414. http://dx.doi.org/10.1016/0024-3795(94)90414-6 [26] T. Yamamoto and Y. Ikebe, “Inversion of Band Matrices,” Linear Algebra and Its Applications, Vol. 24, 1979, pp. 105-111. http://dx.doi.org/10.1016/0024-3795(79)90151-4 [27] Y. Zhang, J. Cohen and J. D. Owens, “Fast Tridiagonal Solvers on the GPU,” Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP 2010), Bangalore, 9-14 January 2010, pp. 127-136. [28] M. E. A. El-Mikkawy, “A Fast Algorithm for Evaluating nth Order Tri-Diagonal Determinants,” Applied Mathematics and Computation, Vol. 202, No. 1, 2008, pp. 210-215. http://dx.doi.org/10.1016/j.amc.2008.01.032 [29] J. W. Demmel, “Applied Numerical Linear Algebra,” Society for Industrial and Applied Mathematics, Philadelphia, 1997. http://dx.doi.org/10.1137/1.9781611971446 [30] M. E. A. El-Mikkawy, “A Note on a Three-Term Recurrence for a Tridiagonal Matrix,” Applied Mathematics and Computation, Vol. 139, No. 2-3, 2003, pp. 503-511. http://dx.doi.org/10.1016/S0096-3003(02)00212-6