A modification of Thomas algorithm for solving system of linear equations on graph
DOI:
https://doi.org/10.17721/2706-9699.2025.1.04Keywords:
system of linear equations, Thomas method, mathematical modelling, graphsAbstract
The aim of the article is to construct and analyze a direct numerical method for solving systems of linear equations which are formed during numerical simulations of mass transfer process on graph.
Research methodology. Proposed modification of Thomas method is based on the recursive removal of paths and cycles from the graph using the Thomas method and the cyclic Thomas method, respectively. Analysis of obtained numerical method is based on proving the main characteristics of numerical methods, such as correctness, stability, and asymptotic estimation of evaluating time.
Results of the research. A direct numerical method for solving the system of linear equations on graph based on Thomas method and cyclic Thomas method is constructed. The correctness of the proposed modification is proven. A stability result for this numerical method is obtained. Asymptotic estimates of the execution time and the amount of additional memory depending on the number of graph vertices are obtained.
Practical significance. Computational experiments indicate the superiority of the proposed algorithm over iterative numerical methods, so its application will positively affect the efficiency of numerical modeling of the mass transfer process on graphs.
References
Hageman L.A., Young D.M. Applied Iterative Methods. Academic Press. 1981. 386 p.
Quarteroni A., Sacco R., Saleri F. Numerical Mathematics, second edition. Springer. 2007. 657 p. https://doi.org/10.1007/b98885.
Ilyin V.P., Kuznetsov Y.I. Tridiagonal Matrices and Their Applications. M: Nauka.1985. 208 p. (in Russian)
Higham N.J. Accuracy and Stability of Numerical Algorithms, second edition. SIAM. 2002. 680 p.
Amodio P., Mazzia F. Backward Error Analysis of Cyclic Reduction for the Solution of Tridiagonal Systems. Mathematics of Computation.1994. Vol. 62. No. 206. P. 601-617. https://doi.org/10.2307/2153526.
Abramov A.A., Andreev V.B. On the Application of the Sweep Method to Finding Periodic Solutions of Differential and Difference Equations. Journal of numerical mathematics and mathematical physics.1963. Vol. 3. No. 2. P. 377–381. (in Russian)
Farthing M.W., Ogden F.L. Numerical Solution of Richards’ Equation: A Review of Advances and Challenges. Soil Science Society of Amer. Journal. 2017. Vol. 81. No. 6. P. 1257–1269. https://doi.org/10.2136/sssaj2017.02.0058.
Zha Y., Yang J., Zeng J., Tso C.-H. M., Zeng W., Shi L. Review of numerical solution of Richardson–Richards equation for variably saturated flow in soils. WIREs Water. 2019. Vol. 6. P. e1364. https://doi.org/10.1002/wat2.1364.
Kolesnykov V.A. Development of a Software Complex for Modeling Mass Transfer Process in Porous Media. PhD Dissertation, Taras Shevchenko National University of Kyiv. 2024. 137 p. (in Ukrainian)
