Please use this identifier to cite or link to this item: doi:10.22028/D291-25951
Title: Reduction of acyclic phase-type representations
Author(s): Pulungan, Muhammad Reza
Language: English
Year of Publication: 2009
SWD key words: Matrix <Mathematik>
Dreiecksmatrix
Algorithmus
Reduktion
Stochastisches Modell
Free key words: Azyklische Phasentypverteilung
Matrixdarstellung
Prozess-Kalkül
acyclic phase-type distributiuon
matrix
triangular matrix
algorithm
reduction
stochastic model
process calculus
DDC notations: 004 Computer science, internet
Publikation type: Doctoral Thesis
Abstract: Acyclic phase-type distributions are phase-type distributions with triangular matrix representations. They constitute a versatile modelling tool, since they (1) can serve as approximations to any continuous probability distribution, and (2) exhibit special properties and characteristics that usually make their analysis easier. The size of the matrix representations has a strong effect on the computational efforts needed in analyzing these distributions. These representations, however, are not unique, and two representations of the same distribution can differ drastically in size. This thesis proposes an effective algorithm to reduce the size of the matrix representations without altering their associated distributions. The algorithm produces significantly better reductions than existing methods. Furthermore, the algorithm consists in only standard numerical computations, and therefore is straightforward to implement. We identify three operations on acyclic phase-type representations that arise often in stochastic models. Around these operations we develop a simple stochastic process calculus, which provides a framework for stochastic modelling and analysis. We prove that the representations produced by the three operations are "almost surely" minimal, and the reduction algorithm can be used to obtain these almost surely minimal representations. The applicability of these contributions is exhibited on a variety of case studies.
Azyklische Phasentypverteilungen sind Phasentypverteilungen, deren Matrixdarstellung eine Dreiecksmatrix ist. Sie stellen ein vielseitiges Modellierungswerkzeug dar, da sie einerseits als Approximationen jeder beliebigen kontinuierlichen Wahrscheinlichkeitsverteilung dienen können, und andererseits spezielle Eigenschaften und Charakteristiken aufweisen, die ihre Analyse vereinfachen. Die Größe der Matrixdarstellung hat dabei einen starken Einfluss auf den Berechnungsaufwand, der zur Analyse solcher Verteilungen nötig ist. Die Matrixdarstellung ist jedoch nicht eindeutig, und zwei verschiedene Darstellungen ein und derselben Verteilung können sich drastisch in ihrer Größe unterscheiden. In dieser Arbeit wird ein effektiver Algorithmus zur Verkleinerung der Matrixdarstellung vorgeschlagen, der die mit der Darstellung assoziierte Verteilung nicht verändert. Dieser Algorithmus verkleinert die Matrizen dabei beträchtlich stärker als bereits existierende Methoden. Darüberhinaus bedient er sich nur numerischer Standardverfahren, wodurch er einfach zu implementieren ist. Wir identifizieren drei Operationen auf azyklischen Phasentypdarstellung, die in stochastischen Modellen häufig anzutreffen sind. Von diesen Operationen ausgehend entwickeln wir einen einfachen stochastischen Prozess-Kalkül, der eine grundlegende Struktur für stochastische Modellierung und Analyse darstellt. Wir zeigen, dass die durch die drei Operationen erzeugten Darstellungen "beinahe gewiss" minimal sind und dass der Reduktionsalgorithmus benutzt werden kann, um diese beinahe gewiss minimalen Darstellungen zu erzeugen. Die Anwendbarkeit dieser Beiträge wird an einer Reihe von Fallstudien exemplifiziert.
Link to this record: urn:nbn:de:bsz:291-scidok-24316
hdl:20.500.11880/26007
http://dx.doi.org/10.22028/D291-25951
Advisor: Hermanns, Holger
Date of oral examination: 27-May-2009
Date of registration: 22-Sep-2009
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
Dissertation_9766_Muha_Pulu_2009.pdf1,5 MBAdobe PDFView/Open


Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.