Split: a flexible and efficient algorithm to vector-descriptor product

Ricardo M. Czekster, Paulo Fernandes, Jean Marc Vincent, Thais Webber*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish
Title of host publicationSMCTOOLS 2007 - 1st International ICST Workshop on Tools for Solving Structured Markov Chains
EditorsPeter Buchholz, Tugrul Dayar
PublisherACM
ISBN (Electronic)9789639799004
Publication statusPublished - 2007
Event1st International ICST Workshop on Tools for Solving Structured Markov Chains, SMCTOOLS 2007 - Nantes, France
Duration: 26 Oct 2007 → …

Publication series

NameACM International Conference Proceeding Series

Conference

Conference1st International ICST Workshop on Tools for Solving Structured Markov Chains, SMCTOOLS 2007
Country/TerritoryFrance
CityNantes
Period26/10/07 → …

Keywords

  • Kronecker Products
  • Numerical Methods
  • Performance Evaluation
  • Tensor Algebra

Fingerprint

Dive into the research topics of 'Split: a flexible and efficient algorithm to vector-descriptor product'. Together they form a unique fingerprint.

Cite this