Multilevel solutions for structured Markov chains

In this paper, a new analysis approach for continuous time Markov chains ( CTMCs) with a multidimensional structure is introduced. The presented solut ion technique employs the multidimensional structure to de ne aggregated CT MCs that can be analyzed more efficiently. Generator matrices of aggregated CTMCs are described in a compact form by exploiting the Kronecker structur e of the generator matrix of a structured CTMC. The solution of aggregated systems is used to improve the solution of the original system. This idea o f a multilevel solution is motivated by multigrid methods, which are effici ent solvers for partial differential equations. The technique can be combin ed with different iterative solution techniques. It usually improves the co nvergence of these techniques significantly. Numerical results are given to illustrate that the new solution technique allows the fast and accurate an alysis of very large CTMCs.