Efficient vector-descriptor product exploiting timememory trade-offs

The description of large state spaces through stochastic struc-tured modeling formalisms like stochastic Petri nets, stochastic au-tomata networks and performance evaluation process algebra usu-ally represent the infinitesimal generator of the underlying Markov chain as a Kronecker descriptor instead of a single large sparse ma-trix. 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 mem-ory prohibitive; the Shuffle algorithm which performs the product of a descriptor by a probability vector with a very impressive mem-ory 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 struc-tured Kronecker represented models in order to numerically illus-trate the gains achieved considering each model’s characteristics