Complexity of Kronecker Operations on Sparse Matrices with Applications to the Solution of Markov Models
Peter Buchholz, Gianfranco Ciardo, and P Kemper · NASA Technical Reports Server (NASA) · 1997
. We present a systematic discussion of algorithms to multiply a vector by a matrix expressed as the Kronecker product of sparse matrices, extending previous work in a unified notational framework. Then, we use our results to define new algorithms for the solution of large structured Markov models. In addition to a comprehensive overview of existing approaches, we give new results with respect to: (1) managing certain types of state-dependent behavior without incurring extra cost; (2) supporting both Jacobi-style and Gauss-Seidel-style methods by appropriate multiplication algorithms; (3) speeding up algorithms that consider probability vectors of size equal to the "actual" state space instead of the "potential" state space. Key words. Kronecker algebra, Markov chains, vector-matrix multiplication Subject classification. Computer Science 1. Introduction. Continuous time Markov chains (CTMCs) are an established technique to analyze the performance, reliability, or performability of d...