The numerical solution of stochastic automata networks

Stochastic Automata Networks (SANs) have recently received attention in the literature as an efficient means of modelling parallel systems such as communicating processes, concurrent processors, shared memory, etc. The advantage that the SAN approach has over generalized stochastic Petri nets, and indeed over any Markovian analysis that requires the generation of a transition matrix, is that its representation remains compact even as the number of states in the underlying Markov chain begins to explode. Our concern in this paper is with the numerical issues that are involved in solving SANs. We introduce stochastic automata and consider the numerical difficulties that result from their interaction. We examine how the product of a vector with a compact SAN descriptor may be formed, for this operation is the basis of all iterative solution methods. We describe possible solution methods, including the power method, the method of Arnoldi and GMRES, and show that the two latter methods greatly out-perform the power method – the method usually used in conjunction with stochastic automata networks. Finally, we consider one possible means of preconditioning, but conclude that further research is needed.