Generalized triangular and symmetric splitting method for steady state probability vector of stochastic matrices. (English) Zbl 07907351
Summary: To find the steady state probability vector of homogenous linear system \(\pi Q= 0\) of stochastic rate matrix \(Q\), generalized triangular and symmetric (GTS) splitting method is presented. Convergence analysis and choice of parameters are given when the regularized matrix \(A=Q^T+\epsilon I\) of the regularized linear system \(Ax=b\) is positive definite. Analysis shows that the iterative solution of GTS method converges unconditionally to the unique solution of the regularized linear system. From the numerical results, it is clear that the solution of proposed method converges rapidly when compared to the existing methods.
MSC:
| 65F15 | Numerical computation of eigenvalues and eigenvectors of matrices |
| 65F35 | Numerical computation of matrix norms, conditioning, scaling |
| 65F10 | Iterative numerical methods for linear systems |
| 45C05 | Eigenvalue problems for integral equations |
| 15B51 | Stochastic matrices |
Keywords:
stochastic matrices; steady state probability vector; GTS method; convergence analysis; relative and absolute errorReferences:
| [1] | W. E. LELAND, M. S. TAQQU, W. WILLINGER and W. V. WILSON, On the Self-Similar Nature of Ethernet Traffic (Extended version), IEEE / ACM Trans. Networking., 2 (1994), No. 1, Article 1, [Online: https://ieeexplore.ieee.org/document/282603]. |
| [2] | A. ANDERSEN and B. NIELSEN, A Markovian approach for modeling packet traffic with long-range dependence, IEEE Journal on Selected Areas in Communications, 16 (1998), No. 5, [Online: https://ieeexplore.ieee.org/document/700908]. |
| [3] | P. BUCHHOLZ, A class of hierarchical queueing networks and their analysis, Queue-ing Syst., 15 (1994), [Online: https://link.springer.com/article/10.1007/ BF01189232]. · Zbl 0789.60067 · doi:10.1007/BF01189232 |
| [4] | S. K. SHAO, P. MALLA REDDY, M. G. TSAI, H. W. TSAO and JINGSHOWN WU, Gen-eralized variance-based Markovian fitting for self-similar traffic modeling, IEICE Trans. Com-mun.,, E88-B (2005), No.4, [Online: https://journals.flvc.org/ietcom-b/ article/view/18094]. |
| [5] | H. MICHIEL and K. LAEVENS, Telegraphic engineering in a broad -band era, Proc. of the IEEE, 85 (1997), pp. 2007-2033. |
| [6] | P. MALLA REDDY, CHIH-HOW CHANG, SHOU-KUO SHAO, and JINGSHOWN WU, An Ef-ficient Approximate Markovian Model for Optical Packet Switches Employing Partial Buffer Shar-ing Mechanism under Self-Similar Traffic Input, Proc. of IEEE HPSR (2007), pp.1-7. |
| [7] | S. KASAHARA, Internet Traffic Modelling: Markovian Approach to Self-Similar Traffic and Prediction of Loss Probability for Finite Queues,Special Issue on Internet Technology, IEICE Trans. Commun., E84-B, l (2001), No.8, [Online: https://search.ieice.org/bin/ summary.php?id=e84-b_8_2134&category=B&year=2001&lang=E]. |
| [8] | C. BLONDIA, The N/G/l finite capacity queue, Commum. Statist.-Stochastic Models, 5 (1989), No.2, [Online: https://www.tandfonline.com/doi/pdf/10.1080/ 15326348908807110]. · Zbl 0673.60102 · doi:10.1080/15326348908807110 |
| [9] | M. F. NEUTS, Matrix-Geometric Solutions in Stochastic Models: An Algorithmic Approach, Dover Publications, New York, 1994. |
| [10] | Z. Z. BAI, G. H. GOLUB, L. Z. LU and J. F. YIN, Block triangular and skew-Hermitian splitting methods for positive-definite linear systems, SIAM J. Sci. Com-put, 26, (2005), No.2, [Online: https://epubs.siam.org/doi/abs/10.1137/ S1064827503428114?journalCode=sjoce3]. · Zbl 1079.65028 · doi:10.1137/S1064827503428114?journalCode=sjoce3 |
| [11] | Z. Z. BAI, G. H. GOLUB, and M. K. NG, Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems, SIAM J. Matrix Anal. Appl. , 24 (2003), No.3, [Online: https://epubs.siam.org/doi/10.1137/S0895479801395458]. · Zbl 1036.65032 · doi:10.1137/S0895479801395458 |
| [12] | J. B. DIAZ and F. T. METCALF, A complementary triangle inequality in Hilbert and Banach spaces, Proc. Amer. Math. Soc., 17 (1966), pp. 88-97. · Zbl 0173.41202 |
| [13] | A. BERMAN and R. PLEMMONS, Nonnegative Matrices in Mathematical Sciences, SIAM, USA, 1994. · Zbl 0815.15016 |
| [14] | M.BENZI and V. KUHLEMANN, Restricted additive methods for Markov chains, Numer. Lin-ear Algebra Appl., 18 (2011), No. 6, [Online: https://onlinelibrary.wiley.com/ doi/abs/10.1002/nla.821]. · Zbl 1265.60146 · doi:10.1002/nla.821 |
| [15] | M. BENZI and B. UCAR, Product preconditioning for Markov chain problems, Proc. of the Markov Anniversary Meeting, (2006), pp. 239-256. |
| [16] | M. BENZI and B. UCAR, Block triangular preconditioners for M-matrices and Markov chains, Electron. Trans. Numer. Anal., 26 (2007), [Online: https://www.researchgate. net/publication/228771534_Block_triangular_preconditioners_for_M-matrices_and_Markov_chains]. · Zbl 1171.65388 |
| [17] | K. BUTLER, BRIAN SIEGEL and H. PAUL, Sharp bounds on the spectral radius of nonnegative matrices and digraphs, Linear Algebra and Its Applications, 439 (2013), No. 5, [Online: https://www.sciencedirect.com/science/article/pii/ S0024379513003054]. · Zbl 1282.05097 |
| [18] | R. BRU, F. PEDROCHE and D. B. SZYLD, Additive Schwarz iterations for Markov chains, SIAM J. Matrix Anal. Appl., 27 (2005), No.2, [Online: https://epubs.siam.org/ doi/abs/10.1137/040616541?journalCode=sjmael]. · Zbl 1097.65047 · doi:10.1137/040616541?journalCode=sjmael |
| [19] | R. BRU, R. CANTO and J. J. CLIMENT, On M-multisplittings of singular M-matrices and Markov chains, Numer. Linear Algebra Appl., 5 (1998), No.4, [Online: https://doi.org/10. 1002/(SICI)1099-1506(199807/08)5:4<299::AID-NLA103>3.0.CO;2-V]. · Zbl 0937.65038 · doi:10.1002/(SICI)1099-1506(199807/08)5:4<299::AID-NLA103>3.0.CO;2-V |
| [20] | P. BROWN and H. F. WALKER, GMRES on (nearly) singular systems, SIAM J. Matrix Anal. Appl., 18 (1997), No.1, [Online: https://epubs.siam.org/doi/abs/10.1137/ S0895479894262339]. · Zbl 0876.65019 · doi:10.1137/S0895479894262339 |
| [21] | W. CHUN, H. TING-ZHU and W. CHAO,Triangular and skew-symmetric splitting meth-ods for numerical solutions of Markov chains, Comp. and Math. With App.,, 62 (2011), No. 11, [Online: https://www.sciencedirect.com/science/article/pii/ S0898122111008091]. · Zbl 1236.65009 |
| [22] | K. HAYAMI, On the behaviour of the conjugate residual method for singular systems,in: Z.-C. SHI, H. KAWARADA (Eds.), Proc. of Fifth China-Japan Seminar on Numerical Mathematics, Shanghai, 1 (2000), pp. 117-126. |
| [23] | L. A. KRUKIER, T. S. MARTYNOVA and Z.-Z. BAI, Product-type skew-Hermitian triangular splitting iteration methods for strongly non-Hermitian positive definite linear systems, J. Com-put. Appl. Math., 232 (2009), No. 1, [Online: https://www.sciencedirect.com/ science/article/pii/S0377042708005414]. · Zbl 1184.65038 |
| [24] | H. MINC, Nonnegative Matrices, Wiyley, Newyork, 1988. · Zbl 0638.15008 |
| [25] | B. PHILIPPE, Y. SAAD and W. J. STEWART, Numerical methods in Markov chain model-ing, Oper. Res., 40 (1992), 232 (2009), No. 6, [Online: https://www.jstor.org/ stable/171728]. |
| [26] | D. RAJAIAH, L. P. RAJ KUMAR and P. MALLA REDDY, Steady state probability vector of positive definite regularized linear systems of circulant stochastic matrices, Linear and Multilinear Algebra, 65 (2017), No. 1, [Online: https://www.tandfonline.com/doi/full/ 10.1080/03081087.2016.1176984]. · Zbl 1360.65099 · doi:10.1080/03081087.2016.1176984 |
| [27] | D. RAJAIAH and P. MALLA REDDY, Loss Behavior of an Internet Router with Self-Similar Input Traffic via Fractal Point Process, Proc. of IEEE ICON-2013 held at Singapore, December 11-13, 978-1-4799-2084-6/13(2013), 2013. |
| [28] | D. RANADHEER, D. RAJAIAH and P. MALLA REDDY, Block triangular and skew sym-metric splitting method for steady state vector of linear system of erogodic block circulant Markov chains, International Journal of Computing Science and Mathematics, 8 (2017), No. 4, [Online: https://www.inderscienceonline.com/doi/abs/10.1504/ IJCSM.2017.085853]. · Zbl 1459.60148 · doi:10.1504/IJCSM.2017.085853 |
| [29] | Y. SAAD, Iterative Methods for Sparse Linear Systems, SIAM, Philadelphia, 2003. · Zbl 1031.65046 |
| [30] | W. J. STEWART, Introduction to Numerical Solution of Markov Chains, Princeton University Press, Princeton, 1994. · Zbl 0821.65099 |
| [31] | P. SONNEVELD, CGS, A Fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 10 1989, No. 1, [Online: https://epubs.siam.org/doi/10.1137/ 0910004]. · Zbl 0666.65029 · doi:10.1137/0910004 |
| [32] | K. TANABE, The conjugate gradient method for computing all the extremal stationary probabil-ity vectors of a stochastic matrix, Ann. Inst. Statist. Math.Part B, 37 (1985), No. 1, [Online: https://link.springer.com/article/10.1007/BF02481090]. · Zbl 0569.60069 · doi:10.1007/BF02481090 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
