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.
Cite this paper
M. El-Mikkawy and F. Atlan, "Algorithms for Solving Linear Systems of Equations of Tridiagonal Type via Transformations," Applied Mathematics, Vol. 5 No. 3, 2014, pp. 413-422. doi: 10.4236/am.2014.53042.
M. El-Mikkawy and F. Atlan, "Algorithms for Solving Linear Systems of Equations of Tridiagonal Type via Transformations," Applied Mathematics, Vol. 5 No. 3, 2014, pp. 413-422. doi: 10.4236/am.2014.53042.
References
[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
[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