Finite and infinite QBD chains: a simple and unifying algorithmic approach

In this paper, we present a novel algorithmic approach, the hybrid matrix geometric/invariant subspace method, for finding the stationary probability distribution of the finite quasi-birth-death (QBD) process which arises in performance analysis of computer and communication systems. Assuming that the QBD state space is defined in two dimensions with m phases and K+1 levels, the solution vector for level k, π_k, 0⩽k⩽K is shown to be in a modified matrix geometric form π_k=υ₁R₁^k +υ₂R₂^K-k where R₁ and R₂ are certain solutions to two nonlinear matrix equations and υ₁ and υ₂ are vectors to be determined using the boundary conditions. We show that the matrix geometric factors R₁ and R₂ can simultaneously be obtained independently of K via finding the sign function of a real matrix by an iterative algorithm with quadratic convergence rates. The time complexity of obtaining the coefficient vectors υ₁ and υ₂ is shown to be O(m³ log₂ K) which indicates that the contribution of the number of levels on the overall algorithm is minimal. Besides the numerical efficiency, the proposed method is numerically stable and in the limiting case of K→∞, it is shown to yield the well-known matrix geometric solution π_k=π₀R₁^k for infinite QBD chain