×

On cyclic reduction applied to a class of Toeplitz-like matrices arising in queueing problems. (English) Zbl 0862.60085

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. 21-38 (1995).
Summary: We observe that the cyclic reduction algorithm leaves unchanged the structure of a block Toeplitz matrix in block Hessenberg form. Based on this fact, we devise a fast algorithm for computing the probability invariant vector of stochastic matrices of a wide class of Toeplitz-like matrices arising in queueing problems. We prove that for any block Toeplitz matrix \(H\) in block Hessenberg form it is possible to carry out the cyclic reduction algorithm with \(O(k^3n+k^2n\log n)\) arithmetic operations, where \(k\) is the size of the blocks and \(n\) is the number of blocks in each row and column of \(H\). The probability invariant vector is computed within the same cost. This substantially improves the \(O(k^3n^2)\) arithmetic cost of the known methods based on Gaussian elimination. The algorithm, based on the FFT, is numerically weakly stable. In the case of semi-infinite matrices the cyclic reduction algorithm is rephrased in functional form by means of the concept of generating functions and a convergence result is proved.
For the entire collection see [Zbl 0940.00042].

MSC:

60K25 Queueing theory (aspects of probability theory)
90B22 Queues and service in operations research
PDFBibTeX XMLCite