PERFORMANCE EVALUATION, VOL.70, NO.9, PP.663-681, 2013.


TITLE: On the Numerical Solution of Kronecker-based Infinite Level-dependent 
QBD Processes


AUTHORS: Hendrik Baumann, Tugrul Dayar, M. Can Orhan, and Werner Sandmann


ABSTRACT: Infinite level-dependent quasi-birth-and-death (LDQBD) processes 
can be used to model Markovian systems with countably infinite multidimensional 
state spaces. Recently it has been shown that sums of Kronecker products can be 
used to represent the nonzero blocks of the transition rate matrix underlying 
an LDQBD process for models from stochastic chemical kinetics. This paper 
extends the form of the transition rates used recently so that a larger class 
of models including those of call centers can be analyzed for their steady-state.
The challenge in the matrix analytic solution then is to compute conditional 
expected sojourn time matrices of the LDQBD model under low memory and time 
requirements after truncating its countably infinite state space judiciously. 
Results of numerical experiments are presented using a Kronecker-based 
matrix-analytic solution on models with two or more countably infinite dimensions 
and rules of thumb regarding better implementations are derived. In doing this, 
a more recent approach that reduces memory requirements further by enabling the 
computation of steady-state expectations without having to obtain the 
steady-state distribution is also considered.


KEY WORDS: Markov chain; Level-dependent QBD process; Kronecker product;
Matrix analytic method; Steady-state expectation; Call center.