Search Advanced

AIMS Mathematics

2025, Volume 10, Issue 3: 6546-6559. doi: 10.3934/math.2025299
Previous Article Next Article
Research article Special Issues

Fast algorithms for a linear system with infinitesimal generator structure of a Markovian queueing model

  • 1.
    School of Mathematics and Statistics, Linyi University, Linyi 276000, China
  • 2.
    School of Automation and Electrical Engineering, Linyi University, Linyi 276000, China
  • Received: 29 December 2024 Revised: 07 March 2025 Accepted: 17 March 2025 Published: 24 March 2025

  • MSC : 15A05, 15B05, 65T50

  • In this paper, we focused on solving the perturbed four-banded linear system derived from the traffic process associated with a Markovian queueing model. Utilizing the spectral decomposition of circulant and skew circulant matrices, we computed the product of Toeplitz inversion and a vector, leading to a decomposition algorithm for perturbed four-banded linear systems. This decomposed Toeplitz system features multiple right-hand terms, significantly reducing computational complexity through Toeplitz inversion. Additionally, we introduced an algorithm based on banded LU decomposition, resulting in a banded linear system with multiple right-hand terms, where the sparsity of the banded LU decomposition is pivotal. To evaluate the algorithm's performance, we presented two examples in numerical simulations.

    Citation: Jiaqi Qu, Yunlan Wei, Yanpeng Zheng, Zhaolin Jiang. Fast algorithms for a linear system with infinitesimal generator structure of a Markovian queueing model[J]. AIMS Mathematics, 2025, 10(3): 6546-6559. doi: 10.3934/math.2025299

    Related Papers:

  • In this paper, we focused on solving the perturbed four-banded linear system derived from the traffic process associated with a Markovian queueing model. Utilizing the spectral decomposition of circulant and skew circulant matrices, we computed the product of Toeplitz inversion and a vector, leading to a decomposition algorithm for perturbed four-banded linear systems. This decomposed Toeplitz system features multiple right-hand terms, significantly reducing computational complexity through Toeplitz inversion. Additionally, we introduced an algorithm based on banded LU decomposition, resulting in a banded linear system with multiple right-hand terms, where the sparsity of the banded LU decomposition is pivotal. To evaluate the algorithm's performance, we presented two examples in numerical simulations.



    加载中


    [1] G. Giambene, Queuing theory and telecommunications networks and applications, 2 Eds., New York: Springer, 2005. http://dx.doi.org/10.1007/978-1-4614-4084-0
    [2] T. Oda, Moment analysis for traffic associated with Markovian queueing systems, IEEE T. Commun., 39 (1991), 737–746. http://dx.doi.org/10.1109/26.87164 doi: 10.1109/26.87164
    [3] M. Fumiaki, An infinitely many server queue having Markov renewal arrivals and hyperexponential service times, J. Oper. Res. Soc. Jpn., 29 (2017), 338–351. http://dx.doi.org/10.2307/2582311 doi: 10.2307/2582311
    [4] C. Wen, T. Z. Huang, X. M. Gu, Z. L. Shen, H. F. Zhang, C. Liu, Multipreconditioned GMRES for simulating stochastic automata networks, Open Math., 16 (2018), 986–998. http://dx.doi.org/10.1515/math-2018-0083 doi: 10.1515/math-2018-0083
    [5] D. A. Bini, B. Meini, Effective methods for solving banded Toeplitz systems, SIAM J. Numer. Anal., 20 (1999), 700–719. http://dx.doi.org/10.1137/S0895479897324585 doi: 10.1137/S0895479897324585
    [6] D. Fischer, G. Golub, O. Hald, C. Leiva, O. Widlund, On Fourier-Toeplitz methods for separable elliptic problems, Math. Comput., 28 (1974), 349–368. http://dx.doi.org/10.2307/2005913 doi: 10.2307/2005913
    [7] A. N. Malyshev, M. Sadkane, Fast solution of unsymmetric banded Toeplitz systems by means of spectral factorizations and Woodbury's formula, Numer. Linear Algebra Appl., 21 (2014), 13–23. https://doi.org/10.1002/nla.1853 doi: 10.1002/nla.1853
    [8] Y. L. Zhao, P. Y. Zhu, X. M. Gu, X. L. Zhao, J. Cao, A limited-memory block bi-diagonal Toeplitz preconditioner for block lower triangular Toeplitz system from time-space fractional diffusion equation, J. Comput. Appl. Math., 362 (2019), 99–115. http://dx.doi.org/10.1016/j.cam.2019.05.019 doi: 10.1016/j.cam.2019.05.019
    [9] S. Serra-Capizzano, C. Tablino-Possio, Multigrid methods for multilevel circulant matrices, SIAM J. Sci. Comput., 26 (2004), 55–85. http://dx.doi.org/10.1137/S1064827501388509 doi: 10.1137/S1064827501388509
    [10] M. A. Jandron, A. A. Ruffa, J. Baglama, An asynchronous direct solver for banded linear systems, Numer. Algorithms, 76 (2017), 211–235. http://doi.org/10.1007/s11075-016-0251-3 doi: 10.1007/s11075-016-0251-3
    [11] Y. R. Fu, X. Y. Jiang, Z. L. Jiang, S. Jhang, Fast algorithms for finding the solution of CUPL-Toeplitz linear system from Markov chain, Appl. Math. Comput., 396 (2021), 125859. http://doi.org/10.1016/j.amc.2020.125859 doi: 10.1016/j.amc.2020.125859
    [12] X. Zhang, X. Y. Jiang, Z. L. Jiang, H. Byun, An improvement of methods for solving the CUPL-Toeplitz linear system, Appl. Math. Comput., 421 (2022), 126932. http://doi.org/10.1016/j.amc.2022.126932 doi: 10.1016/j.amc.2022.126932
    [13] X. Zhang, Y. P. Zheng, Z. L. Jiang, H. Byun, Numerical algorithms for corner-modified symmetric Toeplitz linear system with applications to image encryption and decryption, J. Appl. Math. Comput., 69 (2023), 1967–1987. http://doi.org/10.1007/s12190-022-01819-7 doi: 10.1007/s12190-022-01819-7
    [14] X. Zhang, Y. P. Zheng, Z. L. Jiang, H. Byun, Fast algorithms for perturbed Toeplitz-plus-Hankel system based on discrete cosine transform and their applications, Jpn. J. Ind. Appl. Math., 41 (2024), 567–583. http://doi.org/10.1007/s13160-023-00616-4 doi: 10.1007/s13160-023-00616-4
    [15] X. Zhang, Y. P. Zheng, Z. L. Jiang, Fast algorithms for the solution of perturbed symmetric Toeplitz linear system and its applications, Comput. Appl. Math., 43 (2024), 252. http://dx.doi.org/10.1007/s40314-024-02773-9 doi: 10.1007/s40314-024-02773-9
    [16] J. T. Jia, S. M. Li, On the inverse and determinant of general bordered tridiagonal matrices, Comput. Math. Appl., 69 (2015), 503–509. http://dx.doi.org/10.1016/j.camwa.2015.01.012 doi: 10.1016/j.camwa.2015.01.012
    [17] J. T. Jia, T. Sogabe, S. M. Li, A generalized symbolic Thomas algorithm for the solution of opposite-bordered tridiagonal linear systems, J. Comput. Appl. Math., 290 (2015), 423–432. http://dx.doi.org/10.1016/j.cam.2015.05.026 doi: 10.1016/j.cam.2015.05.026
    [18] J. A. Marrero, A numerical solver for general bordered tridiagonal matrix equations, Comput. Math. Appl., 72 (2016), 2731–2740. http://dx.doi.org/10.1016/j.camwa.2016.09.025 doi: 10.1016/j.camwa.2016.09.025
    [19] A. Martin, I. D. Boyd, Variant of the Thomas Algorithm for opposite-bordered tridiagonal systems of equations, Int. J. Numer. Meth. Bio., 26 (2010), 752–759. http://dx.doi.org/10.1002/CNM.1172 doi: 10.1002/CNM.1172
    [20] L. Du, T. Sogabe, S. L. Zhang, A fast algorithm for solving tridiagonal quasi-Toeplitz linear systems, Appl. Math. Lett., 75 (2018), 74–81. http://dx.doi.org/10.1016/j.aml.2017.06.016 doi: 10.1016/j.aml.2017.06.016
    [21] Y. L. Wei, Y. P. Zheng, Z. L. Jiang, S. Shon, A study of determinants and inverses for periodic tridiagonal Toeplitz matrices with perturbed corners involving Mersenne numbers, Mathematics, 7 (2019), 893. http://dx.doi.org/10.3390/math7100893 doi: 10.3390/math7100893
    [22] Y. L. Wei, X. Y. Jiang, Z. L. Jiang, S. Shon, Determinants and inverses of perturbed periodic tridiagonal Toeplitz matrices, Adv. Differ. Equ., 2019 (2019), 410. http://dx.doi.org/10.1186/s13662-019-2335-6 doi: 10.1186/s13662-019-2335-6
    [23] Y. L. Wei, X. Y. Jiang, Z. L. Jiang, S. Shon, On inverses and eigenpairs of periodic tridiagonal Toeplitz matrices with perturbed corners, J. Appl. Anal. Comput., 10 (2020), 178–191. http://dx.doi.org/10.11948/20190105 doi: 10.11948/20190105
    [24] T. Sogabe, Numerical algorithms for solving comrade linear systems based on tridiagonal solvers, Appl. Math. Comput., 198 (2008), 117–122. http://dx.doi.org/10.1016/j.amc.2007.08.029 doi: 10.1016/j.amc.2007.08.029
    [25] J. T. Jia, S. M. Li, New algorithms for numerically solving a class of bordered tridiagonal systems of linear equations, Comput. Math. Appl., 78 (2019), 144–151. http://dx.doi.org/10.1016/j.camwa.2019.02.028 doi: 10.1016/j.camwa.2019.02.028
    [26] G. Golub, C. Van Loan, Matrix computations, 3 Eds., Baltimore and London: Johns Hopkins University Press, 1996.
    [27] C. Garoni, S. Serra-Capizzano, Generalized locally Toeplitz sequences: Theory and applications, Cham: Springer, 2017.
    [28] A. Böttcher, S. M. Grudsky, Spectral properties of banded Toeplitz matrices, Philadelphia: SIAM, 2005.
    [29] M. Bogoya, S. M. Grudsky, S. Serra-Capizzano, Fast non-Hermitian Toeplitz eigenvalue computations, joining matrixless algorithms and FDE approximation matrices, SIAM J. Matrix Anal. Appl., 45 (2024), 284–305. http://doi.org/10.1137/22M1529920 doi: 10.1137/22M1529920
    [30] S. Serra-Capizzano, P. Tilli, Extreme singular values and eigenvalues of non-Hermitian block Toeplitz matrices, J. Comput. Appl. Math., 108 (1999), 113–130. http://dx.doi.org/10.1016/S0377-0427(99)00104-1 doi: 10.1016/S0377-0427(99)00104-1
    [31] M. Batista, A. A. Karawia, The use of the Sherman-Morrison-Woodbury formula to solve cyclic block tri-diagonal and cyclic block penta-diagonal linear systems of equations, Appl. Math. Comput., 210 (2009), 558–563. http://dx.doi.org/10.1016/j.amc.2009.01.003 doi: 10.1016/j.amc.2009.01.003
    [32] R. H. Chan, X. Q. Jin, An introduction to iterative Toeplitz solvers, Philadelphia: SIAM, 2007. http://dx.doi.org/10.1137/1.9780898718850
    [33] X. Q. Jin, Preconditioning techniques for Toeplitz systems, Beijing: Higher Education Press, 2010.
    [34] M. K. Ng, Iterative methods for Toeplitz systems, New York: Oxford University Press, 2004.
    [35] S. L. Lei, Y. C. Huang, Fast algorithms for high-order numerical methods for space fractional diffusion equations, Int. J. Comput. Math., 94 (2017), 1062–1078. http://dx.doi.org/10.1080/00207160.2016.1149579 doi: 10.1080/00207160.2016.1149579
    [36] R. H. Chan, A. M. Yip, M. K. Ng, The best circulant preconditioners for Hermitian Toeplitz systems, SIAM J. Numer. Anal., 38 (2000), 876–896. http://dx.doi.org/10.1137/s0036142999354083 doi: 10.1137/s0036142999354083
    [37] I. Gohberg, V. Olshevsky, Circulants, displacements and decompositions of matrices, Integr. Equat. Oper. Th., 15 (1992), 730–743. http://dx.doi.org/10.1007/BF01200697 doi: 10.1007/BF01200697
    [38] R. H. Chan, M. K. Ng, Conjugate gradient methods for Toeplitz systems, SIAM Rev., 38 (1996), 427–482. http://dx.doi.org/10.1137/S0036144594276474 doi: 10.1137/S0036144594276474
  • Reader Comments
  • © 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索
AIMS Mathematics
1.8 3.1

Metrics

Article views(923) PDF downloads(47) Cited by(0)

Preview PDF
Download XML
Export Citation
Article outline

Figures and Tables

Tables(2)

Other Articles By Authors

Related pages

Tools

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog