MAM 2006: Markov Anniversary Meeting  

TITLE: Analyzing Markov Chains Based on Kronecker Products  

AUTHOR: Tugrul Dayar  

ABSTRACT:  Kronecker products are used to define the underlying Markov chain (MC)  
in various modeling formalisms, including compositional Markovian models, 
hierarchical Markovian models, and stochastic process algebras. The motivation 
behind using a Kronecker structured representation rather than a flat one is to 
alleviate the storage requirements associated with the MC. With this approach, 
systems that are an order of magnitude larger can be analyzed on the same platform. 
The developments in the solution of such MCs are reviewed from an algebraic point 
of view and possible areas for further research are indicated with an emphasis on 
preprocessing using reordering, grouping, and lumping and numerical analysis using  
block iterative, multilevel, and preconditioned projection methods.  

KEY WORDS: Markov chains, Kronecker products, reordering, grouping, lumping, block 
iterative methods, multilevel methods, preconditioned projection methods