Structured analysis approaches for large Markov chains (Q1807701)

The aim of the paper is to give an overview of structural analysis techniques for iterative numerical analysis of continuous time Markov chains (CTMCs), as an important modern tool to extend the size of analizable state spaces significantly compared with conventional approaches. Two different forms of structured representations, viz. the composed automata approach and a hierarchical two-level approach are presented into a simple structured framework. Tensor algebra is introduced as the basic concept to represent generator matrices in a compact form. Thus generator matrices of large CTMCs can be represented in a very compact form using tensor products/sums, and this representation can be profitably exploited in numerical solution techniques. Different structured solution algorithms, their implementation, new forms of aggregation/disaggregation and new preconditioners are introduced and examined.