A novel computational method for solving finite qbd processes
Authors:
- 1 January 2000
- journal article
- research article
- Published by Taylor & Francis in Communications in Statistics. Stochastic Models
- Vol. 16 (2) , 273-311
Abstract
We present a novel numerical method that exploits invariant subspace computations for finding the stationary probability distribution of a finite QBD process. Assuming that the QBD state space is defined in two dimensions with m phases and K+1 levels, the solution vector π k for level , is known to be expressible in the mixed matrix-geometric form , where R 1and R 2are certain solutions to two quadratic matrix equations, and v 1and v 2are vectors to be determined using the boundary conditions. We show that the matrix-geometric factors R 1and R 2can be simultaneously obtained irrespective of K via finding arbitrary bases for the left-and right-invariant subspaces of a certain real matrix of size 2m To find these bases, we employ either Schur decomposition or a matrix-sign function iteration with quadratic convergence rate. The vectors v 1and v 2are obtained by solving a linear matrix equation, which is constructed with a time complexity of . Therefore, the effect of the number of levels on the overall complexity is minimal. Besides its numerical efficiency, the proposed method is numerically stable, and in the limiting case of , it is shown to yield the well-known matrix-geometric solution for infinite QBD processes. We also extend the method to the cases of level-dependent and non-canonical transitions, and provide a numerical example to demonstrate its computational features in comparison with other well-known methodsKeywords
This publication has 26 references indexed in Scilit:
- Matrix-geometric solutions of M/G/1-type Markov chains: a unifying generalized state-space approachIEEE Journal on Selected Areas in Communications, 1998
- An invariant subspace approach in m/g/l and g/m/l type markov chainsCommunications in Statistics. Stochastic Models, 1997
- On the Solution of a Nonlinear Matrix Equation Arising in Queueing ProblemsSIAM Journal on Matrix Analysis and Applications, 1996
- Calculating the equilibrium distribution in level dependent quasi-birth-and-death processesCommunications in Statistics. Stochastic Models, 1995
- Solutions of the basic matrix equation for M/G/l AND G/M/1 type markov chainsCommunications in Statistics. Stochastic Models, 1994
- Experimental results on matrix-analytical solution techniques–extensions and comparisonsCommunications in Statistics. Stochastic Models, 1989
- Rank revealing QR factorizationsLinear Algebra and its Applications, 1987
- Solving the algebraic Riccati equation with the matrix sign functionLinear Algebra and its Applications, 1987
- A generalization of the matrix-sign-function solution for algebraic Riccati equationsInternational Journal of Control, 1986
- Accelerated convergence of the matrix sign function method of solving Lyapunov, Riccati and other matrix equationsInternational Journal of Control, 1980