Complexity of memory-efficient Kronecker operations with applications to the solution of Markov models

Complexity of memory-efficient Kronecker operations with applications to the solution of Markov models

0.00 Avg rating0 Votes
Article ID: iaor20012918
Country: United States
Volume: 12
Issue: 3
Start Page Number: 203
End Page Number: 222
Publication Date: Jun 2000
Journal: INFORMS Journal On Computing
Authors: , , ,
Keywords: computational analysis
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.