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: | Ciardo Gianfranco, Buchholz Peter, Donatelli Susanna, Kemper Peter |
Keywords: | computational analysis |
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.