Volume 31, pp. 271-294, 2008.

Decompositional analysis of Kronecker structured Markov chains

Yujuan Bao, İlker N. Bozkurt, Tugrul Dayar, Xiaobai Sun, and Kishor S. Trivedi


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.

Full Text (PDF) [249 KB]

Key words

Markov chain, Kronecker representation, decomposition, iterative method, multigrid, aggregation, disaggregation.

AMS subject classifications

60J27, 15A72, 65F10, 65F50, 65B99.

< Back