Efficient Transient Analysis of Markovian Models Using a Block Reduction Approach

One of the most widely used techniques to obtain transient measures is the uniformization method. However, although uniformization has many advantages, the computational cost required to calculate transient probabilities is very large for stiff models. We study efficient solutions that can be applied to an approximate method developed for calculating transient state probabilities of Markov models and cumulative expected reward measures over a finite interval. Our work is based on a method that approximates the state probabilities at time t by the state probabilities calculated at a random time with Erlangian distribution. The original method requires an inversion of a matrix obtained from the state transition rate matrix that destroys special structures such as sparseness and banded matrices. This precludes the use of the technique for large models. In our work we propose efficient solutions that can take advantage of special structures. Finally, we present examples that show that the proposed technique is computationally very efficient for stiff models when compared with uniformization.