THE NUMERICAL-SOLUTION OF STOCHASTIC AUTOMATA NETWORKS

Stochastic Automata Networks (SAN's) 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 stochas tic Petri nets, and indeed over any Markovian analysis that requires t he generation of a transition matrix, is that its representation remai ns compact even as the number of states in the underlying Markov chain begins to explode. Our concern in this paper is with the numerical is sues that are involved in solving SAN networks. We introduce stochasti c automata and consider the numerical difficulties that result from th eir 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, inc luding the power method, the method of Arnoldi and GMRES, and show tha t the two latter methods greatly out-perform the power method - the me thod usually used in conjunction with stochastic automata networks. Fi nally, we consider one possible means of preconditioning, but conclude that further research is needed.