On Cyclic Reduction Applied to a Class of Toeplitz-Like Matrices Arising in Queueing Problems

Dario Bini and Beatrice Meini
Additional contact information
Dario Bini: Università di Pisa, Dipartimento di Matematica
Beatrice Meini: Università di Pisa, Dipartimento di Matematica

Chapter 2 in Computations with Markov Chains, 1995, pp 21-38 from Springer

Abstract: Abstract 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 3 n + k 2 n 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 3 n 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 function and a convergence result is proved.

Keywords: Stochastic Matrice; Block Column; Cyclic Reduction; Triangular Block; Block Toeplitz Matrix (search for similar items in EconPapers)
Date: 1995
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-1-4615-2241-6_2

Ordering information: This item can be ordered from
http://www.springer.com/9781461522416

DOI: 10.1007/978-1-4615-2241-6_2

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().