TECHNICAL REPORT BU-CE-1206, BILKENT UNIVERSITY, 
DEPARTMENT OF COMPUTER ENGINEERING

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

AUTHORS: Hendrik Baumann, Tugrul Dayar, Muhsin 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.