TY - JOUR

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

AU - Czekster, R.M.

AU - Fernandes, P.

AU - Webber, T.

PY - 2011/12/1

Y1 - 2011/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-84964792096&partnerID=MN8TOARS

UR - https://dl.acm.org/doi/10.1145/2160803.2160805

U2 - 10.1145/2160803.2160805

DO - 10.1145/2160803.2160805

M3 - Article

VL - 39

SP - 2

EP - 9

IS - 3

ER -