Skip to Main content Skip to Navigation
Reports

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 :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00072328
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 8:24:53 PM
Last modification on : Tuesday, February 9, 2021 - 3:22:08 PM
Long-term archiving on: : Sunday, April 4, 2010 - 11:04:03 PM

Identifiers

  • HAL Id : inria-00072328, version 1

Collections

Citation

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

Share

Metrics

Record views

279

Files downloads

296