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 -