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.