@inproceedings{d385554ce7af48fd87bb39f0fd6a9b00,
title = "Split: a flexible and efficient algorithm to vector-descriptor product",
abstract = "Many Markovian stochastic structured modeling formalisms like Petri nets, automata networks and process algebra represent the infinitesimal generator of the underlying Markov chain as a descriptor instead of a traditional sparse matrix. A descriptor is a compact and structured storage based on a sum of tensor (Kronecker) products of small matrices that can be handled by many algorithms allowing affordable stationary and transient solutions even for very large Markovian models. One of the most efficient algorithms used to compute iterative solutions of descriptors is the Shuffle algorithm which is used to perform the multiplication by a probability vector. In this paper we propose an alternative algorithm called Split, since it offers a flexible solution between the pure sparse matrix approach and the Shuffle algorithm using a hybrid solution. The Split algorithm puts the Shuffle approach in perspective by presenting a faster execution time for many cases and at least the same efficiency for the worst cases. The Split algorithm is applied to solve two SAN models based on real problems showing the practical contribution of this paper.",
keywords = "Kronecker Products, Numerical Methods, Performance Evaluation, Tensor Algebra",
author = "Czekster, {Ricardo M.} and Paulo Fernandes and Vincent, {Jean Marc} and Thais Webber",
note = "Funding Information: Performance Evaluation, Numerical Methods, Tensor Algebra, Kronecker Products ∗This work is partially supported by the brazilian government (CAPES), FINEP project STGSD grant nb. 4284/05 and SMS Project (France). Authors Ricardo M. Czekster and Thais Webber are invited by the Project MESCAL-INRIA. †Corresponding author. The order of authors is merely alphabetical. Publisher Copyright: Copyright 2007 ICST.; 1st International ICST Workshop on Tools for Solving Structured Markov Chains, SMCTOOLS 2007 ; Conference date: 26-10-2007",
year = "2007",
language = "English",
series = "ACM International Conference Proceeding Series",
publisher = "ACM",
editor = "Peter Buchholz and Tugrul Dayar",
booktitle = "SMCTOOLS 2007 - 1st International ICST Workshop on Tools for Solving Structured Markov Chains",
address = "United States",
}