Efficient Solution for a Class of Markov Chain Models of Tandem Queueing Networks

We present a new numerical method for the computation of the steady-state solution of Markov chains. Theoretical analyses show that the proposed method, with a contraction factor α, converges to the one-dimensional null space of singular linear systems of the form Ax = 0. Numerical experiments are used to illustrate the effectiveness of the proposed method, with applications to a class of interesting models in the domain of tandem queueing networks.

• Chun Wen
• Tingzhu Huang

• Markov chains
• tandem queueing networks
• convergence
• effectiveness.

[1] E. Seneta, Non-Negative Matrices, John Wiley, New York, 1973.
[2] H. De Sterck, T.A. Manteuffel, S.F. McCormick, K. Miller, J. Pearson,
J. Ruge, and G. Sanders, Smoothed aggregation multigrid for Markov
chains, SIAM J. Sci. Comput., 2010, 32 (1): 40-61.
[3] G. Latouche, V. Ramaswami, Introduction to Matrix Analytic Methods
in Stochastic Modeling, ASA-SIAM series on statistics and applied
probability, 1999.
[4] S.D. Kamvar, T.H. Haveliwala, C.D. Manning, G.H. Golub, Extrapolation
methods for accelerating PageRank computations, Proceedings of the
Twelfth International World Wide Web Conference, 2003, pp. 261-270.
[5] B. Philippe, Y. Saad, W.J. Stewart, Numerical methods in Markov Chain
modeling, Operations Research, 1992, 40 (6): 1156-1179.
[6] Z.-Z. Bai, G.H. Golub, L.-Z. Lu, J.F. Yin, Block triangular and skew-
Hermitian splitting methods for positive-definite linear systems, SIAM J.
Sci. Comput., 2005, 26 (3): 844-863.
[7] Z.-Z. Bai, G.H. Golub, M.K. Ng, Hermitian and skew-Hermitian splitting
methods for non-Hermitian positive definite linear systems, SIAM J.
Matrix Anal. Appl., 2003, 24 (3): 603-626.
[8] A. Berman, R.J. Plemmons, Nonnegative Matrices in the Mathematics
Science, Classics Allp. Math. 9, SIAM, Philadelphia, 1994.