A novel computational method for solving finite qbd processes

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 methods