Sprungmarken

Servicenavigation

Hauptnavigation

Sie sind hier:

Hauptinhalt

Publications

Compact Representation of Solution Vectors in Kronecker-based Markovian Analysis

Peter Buchholz, Tugrul Dayar, Jan Kriege, M. Can Orhan

Proc. of the 13th International Conference on Quantitative Evaluation of SysTems (QEST 2016), Springer, 2016.

 

Abstract

It is well known that the infinitesimal generator underlying a multi-dimensional Markov chain with a relatively large reachable state space can be represented compactly on a computer in the form of a block matrix in which each nonzero block is expressed as a sum of Kronecker products of smaller matrices. Nevertheless, solution vectors used in the analysis of such Kronecker-based Markovian representations still require memory proportional to the size of the reachable state space, and this becomes a bigger problem as the number of dimensions increases. The current paper shows that it is possible to use the hierarchical Tucker decomposition (HTD) to store the solution vectors during Kronecker-based Markovian analysis relatively compactly and still carry out the basic operation of vector-matrix multiplication in Kronecker form relatively efficiently. Numerical experiments on two different problems of varying sizes indicate that larger memory savings are obtained with the HTD approach as the number of dimensions increases.

 

Keywords
Markov chains, Kronecker products, Hierarchical Tucker decomposition, Reachable state space, Compact vectors

 

BibTeX
@InProceedings{BDK+16,
	 author="Buchholz, Peter and Dayar, Tu{\v{g}}rul and Kriege, Jan and Orhan, M. Can",
	 title={{Compact Representation of Solution Vectors in Kronecker-Based Markovian Analysis}},
	 booktitle="Proc. of the 13th International Conference Quantitative Evaluation of Systems (QEST 2016)",
	 year="2016",
	 isbn="978-3-319-43425-4",
	 doi="10.1007/978-3-319-43425-4_18",
	 url="http://dx.doi.org/10.1007/978-3-319-43425-4_18",
	 pages="260--276",
	 volume={9826},
	 series={Lecture Notes in Computer Science},
	 editor="Agha, Gul and Van Houdt, Benny",
	 publisher="Springer International Publishing"
}

 

Links