EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, VOL.148, NO.2, PP.436-451, 2003.

TITLE: Lumpable Continuous-Time Stochastic Automata Networks

AUTHORS: Oleg Gusak, Tugrul Dayar, and Jean-Michel Fourneau

ABSTRACT: The generator matrix of a continuous-time stochastic automata
network (SAN) is a sum of tensor products of smaller matrices, which may
have entries that are functions of the global state space. This paper
specifies easy to check conditions for a class of ordinarily lumpable
partitionings of the generator of a continuous-time SAN in which
aggregation is performed automaton by automaton. When there exists a
lumpable partitioning induced by the tensor representation of the
generator, it is shown that an efficient aggregation-iterative
disaggregation algorithm may be employed to compute the steady state
distribution. The results of experiments with two SAN models show that
the proposed algorithm performs better than the highly competitive block
Gauss-Seidel in terms of both the number of iterations and the time to
converge to the solution.

KEY WORDS: Markov processes; Stochastic automata networks; Ordinary
lumpability; Aggregation with iterative disaggregation.