Semi-numerical transient analysis of Markov models

TitleSemi-numerical transient analysis of Markov models
Publication TypeJournal Article
Year of Publication1995
AuthorsAV Ramesh, and K Trivedi
JournalProceedings of the Annual Southeast Conference
Start Page13
Pagination13 - 23
Date Published01/1995
Abstract

We present a new O(n3) algorithm for seminumerical transient analysis of continuous time Markov chains with n states. The algorithm is based on spectral decomposition of the transition rate matrix in combination with partial fraction expansion based on Laplace transforms. The algorithm acknowledges the inherent numerical difficulties associated with illconditioned problems and finite machine precision by incorporating a realistic assessment of the condition and sensitivity of the problem. It is more efficient and provides more accurate solutions in the face of round-off error when compared to similar algorithms in the literature. We demonstrate the performance of the algorithm on many ill-conditioned applications.

DOI10.1145/1122018.1122021
Short TitleProceedings of the Annual Southeast Conference