ELECTRONIC TRANSACTIONS ON NUMERICAL ANALYSIS, VOL.31, PP.271-294, 2008.  

TITLE: Decompositional analysis of Kronecker structured Markov chains   

AUTHORS: Yujuan Bao, Ilker N. Bozkurt, Tugrul Dayar, Xiaobai Sun, and  
Kishor S. Trivedi  

ABSTRACT: This contribution proposes a decompositional iterative method 
with low memory requirements for the steady-state analysis of Kronecker 
structured  Markov chains. The Markovian system is formed by a 
composition of subsystems  using the Kronecker sum operator for local 
transitions and the Kronecker product operator for synchronized 
transitions. Even though the interactions among subsystems, which are 
captured by synchronized transitions, need not be weak, numerical 
experiments indicate that the solver benefits considerably from weak 
interactions among subsystems, and is to be recommended specifically 
in this case.    

KEY WORDS: Markov chain; Kronecker representation; decomposition; 
iterative  method; multigrid; aggregation; disaggregation