×

Numerical methods for structured Markov chains. (English) Zbl 1076.60002

Numerical Mathematics and Scientific Computation. Oxford: Oxford University Press (ISBN 0-19-852768-3/hbk). xi, 327 p. (2005).
The book intersects two large research fields – numerical analysis and queueing theory, it deals with the numerical solution of structured Markov chains which are widely used in applied probability theory and stochastic modelling including M/G/1 and G/M/1 type Markov chains, quasi-birth-death (QBD) processes, non-skip-free queues and tree-like stochastic processes. The results from the current literature are given in a unifying language and new results are obtained concerning the convergence of some methods. It is shown that the Ramaswami formula is the canonical factorization of a matrix power series, and the FFT-based algorithms allow to implement this formula in a way much faster than the customary implementation.
The book contains three parts: Tools, Structured Markov chains and Algorithms. The first part consists of three chapters. Chapter 1 describes the fundamental concepts of Markov chains. Chapter 2 contains a systematic treatment of needed structured matrix tools like finite Toeplitz and circulant matrices, displacement operators and fast Fourier transform (FFT). Chapter 3 presents matrix power series, the infinite block Toeplitz matrices, the problems of solving matrix equations and canonical factorizations.
The second part deals with the description and analysis of structured Markov chains. In Chapter 4, M/G/1 type Markov chains are examined, the reduction to the solution of nonlinear matrix equation and the role of canonical factorizations are shown. Chapter 5 considers G/M/1 type queues; non-skip-free, QBD and tree-like processes are analyzed.
The third part deals with solution algorithms. Chapter 6 describes and compares functional iteration techniques for solving nonlinear matrix equations: fixed point iterations, linearly convergent iterations and Newton’s iterations are considered. Chapter 7 concerns quadratically convergent algorithms: logarithmic reduction and the cyclic reduction technique for QBDs and their extension to M/G/1 and G/M/1 processes. Chapter 8 deals with some alternative approaches, it gives a general technique for the acceleration of iterative methods. In Chapter 9, some specialized structures are investigated and different algorithms are introduced.
Each chapter is completed with bibliographic notes, the appendix collects the main general concepts and results of the book. Each solution method is given in detailed algorithmic form, so it can easily be translated into a program code. The book is useful for researchers and PhD students both in the field of applied probability and numerical analysis, it can be used by specialists dealing with telecommunication and computer systems.

MSC:

60-02 Research exposition (monographs, survey articles) pertaining to probability theory
60K25 Queueing theory (aspects of probability theory)
65C40 Numerical analysis or methods applied to Markov chains

Software:

na12; FFTW; SLICOT
PDFBibTeX XMLCite
Full Text: DOI