Aggregation of stochastic automata networks with replicas (Q1434417)

So far known approaches for computing the solution of Markov chain models present lumpability conditions in order to reduce large state spaces. This paper aims at the presentation of an equivalent technique which can be used to efficiently aggregate stochastic automata networks (SAN) whose generators can be represented in the form of a generalized tensor algebra. Many large systems include a number of replications of identical components. This paper exploits replication by aggregating similar components. This leads to a significant state space reduction, based on lumpability. SAN with replicas are defined and analyzed, and it is shown how such SAN models can be strongly aggregated, taking functional rates into account. A tensor representation of the matrix of the aggregated Markov chain is proposed, allowing to store this chain in a compact manner and to handle larger models with replicas more efficiently. A theorem is proved to answer how strong aggregation can be performed. Examples and numerical results are presented to illustrate the reduction in state space and, consequently, an impressive memory and CPU time reduction. However, the application of SAN is limited by the product state space size.