Abstract
The description of large state spaces through stochastic structured modeling formalisms like stochastic Petri nets, stochastic automata networks and performance evaluation process algebra usually represent the infinitesimal generator of the underlying Markov chain as a Kronecker descriptor instead of a single large sparse matrix. The best known algorithms used to compute iterative solutions of such structured models are: the pure sparse solution approach, an algorithm that can be very time efficient, and almost always memory prohibitive; the Shuffle algorithm which performs the product of a descriptor by a probability vector with a very impressive memory efficiency; and a newer option that offers a trade-off between time and memory savings, the Split algorithm. This paper presents a comparison of these algorithms solving some examples of structured Kronecker represented models in order to numerically illustrate the gains achieved considering each model's characteristics.
Original language | English |
---|---|
Pages (from-to) | 2-9 |
Number of pages | 8 |
Journal | ACM SIGMETRICS Performance Evaluation Review |
Volume | 39 |
Issue number | 3 |
DOIs | |
Publication status | Published - 21 Dec 2011 |
Event | GreenMetrics Workshop 2011 - San Jose, United States Duration: 7 Jun 2011 → … |
Bibliographical note
Funding Information:Paulo Fernandes is partially funded by CNPq grant 307284/2010-7.
Keywords
- Kronecker products
- Numerical methods
- Optimization of iterative methods