This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Buchholz, P. Articles by Kemper, P. Search for Related Content

Complexity of Memory-Efficient Kronecker Operations with Applications to the Solution of Markov Models

Department of Computer Science, Dresden University of Technology, D-01062 Dresden, Germany
Department of Computer Science, College of William and Mary, Williamsburg, VA 23187-8795
Dipartimento di Informatica, Universitá di Torino, Corso Svizzera 185, 10149 Torino, Italy
Informatik IV, Universität Dortmund, D-44221 Dortmund, Germany
p.buchholz{at}inf.tu-dresden.de, http://iis141.inf.tu-dresden.de/ms/pb/pb-engl.html
ciardo{at}cs.wm.edu, http://ww.cs.wm.eduA/~ciardo/
susi{at}di.unito.it
kemper{at}ls4.informatik.uni-dortmund.de, http://ls4-www.informatik.uni-dortmund.de/QM/MA/pk/pie.html

We present new algorithms for the solution of large structured Markov models whose infinitesimal generator can be expressed as a Kronecker expression of sparse matrices. We then compare them with the shuffle-based method commonly used in this context and show how our new algorithms can be advantageous in dealing with very sparse matrices and in supporting both Jacobi-style and Gauss-Seidel-style methods with appropriate multiplication algorithms. Our main contribution is to show how solution algorithms based on Kronecker expression can be modified to consider probability vectors of size equal to the "actual" state space instead of the "potential" state space, thus providing space and time savings. The complexity of our algorithms is compared under different sparsity assumptions. A nontrivial example is studied to illustrate the complexity of the implemented algorithms.

Key words: kronecker algebra; sparse matrices
History: received August 1997; revised May 1999; accepted February 2000.

This article has been cited by other articles:

				M.-Y. Chung and G. Ciardo Speculative Image Computation for Distributed Symbolic Reachability Analysis J Logic Computation, February 20, 2009; (2009) exp005v1. [Abstract] [PDF]

				A. N. Langville and W. J. Stewart Testing the Nearest Kronecker Product Preconditioner on Markov Chains and Stochastic Automata Networks INFORMS Journal on Computing, January 1, 2004; 16(3): 300 - 315. [Abstract] [PDF]