HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Memory Efficient Iterative Methods for Stochastic Automata Networks

Anne Benoit 1 Brigitte Plateau 2 William J. Stewart 2
2 APACHE - Parallel algorithms and load sharing
ID-IMAG - Informatique et Distribution, Inria Grenoble - Rhône-Alpes, UJF - Université Joseph Fourier - Grenoble 1
Abstract : We present new algorithms for computing the solution of large Markov chain models whose generators can be represented in the form of a generalized tensor algebra, such as networks of stochastic automata. The tensorial structure implies to work on a product space. Inside this product space, the reachable state space can be much smaller. For these cases, we propose two improvements of the standard numerical algorithm (based on tensor products), called «shuffle algorithm», that take as input-output only data structures of the size of the reachable state space. One of the improveme- nts allows a gain on the computation time, and the other one on the memory requirements. With those contributions, the numerical algorithms based on tensor products can deal with larger models.
Document type :
Complete list of metadata

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 8:24:53 PM
Last modification on : Friday, February 4, 2022 - 3:12:38 AM
Long-term archiving on: : Sunday, April 4, 2010 - 11:04:03 PM


  • HAL Id : inria-00072328, version 1



Anne Benoit, Brigitte Plateau, William J. Stewart. Memory Efficient Iterative Methods for Stochastic Automata Networks. [Research Report] RR-4259, INRIA. 2001. ⟨inria-00072328⟩



Record views


Files downloads