Efficient vector-descriptor product exploiting time-memory trade-offs

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)2-9
Number of pages8
JournalACM SIGMETRICS Performance Evaluation Review
Volume39
Issue number3
DOIs
Publication statusPublished - 21 Dec 2011
EventGreenMetrics 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

Fingerprint

Dive into the research topics of 'Efficient vector-descriptor product exploiting time-memory trade-offs'. Together they form a unique fingerprint.

Cite this