zbMATH — the first resource for mathematics

Iterative methods for queueing models with batch arrivals. (English) Zbl 0862.60087
Stewart, William J. (ed.), Computations with Markov chains. Proceedings of the 2nd international workshop on the numerical solution of Markov chains, Raleigh, NC, USA, January 16–18, 1995. Boston, MA: Kluwer Academic Publishers. 81-93 (1995).
Summary: We consider finding the stationary probability distribution vectors of Markovian queueing models having batch arrivals by using the preconditioned conjugate gradient (PCG) method. The preconditioners are constructed by exploiting the near-Toeplitz structure of the generator matrix of the model and are products of circulant matrices and band-Toeplitz matrices. We prove that if the number of servers \(s\) is fixed independent of the queue size \(n\), then for sufficiently large \(n\), the preconditioners are invertible and the preconditioned systems have singular values clustered around 1. Hence if the systems are solved by the preconditioned conjugate gradient method, we expect superlinear convergence. Our numerical results show that the PCG method with our preconditioner converges in finite number of steps independent of \(n\) and \(s\) whereas the numbers required by the Jacobi method or the PCG method without any preconditioner increase like \(O(n)\).
For the entire collection see [Zbl 0940.00042].

60K25 Queueing theory (aspects of probability theory)
15B52 Random matrices (algebraic aspects)
90B22 Queues and service in operations research