Semi-numerical transient analysis of Markov models

ABSTRACT

We present a new O(n³) 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.

REFERENCES

• 1: Meera Balakrishnan, Reliability evaluation of fault-tolerant computing systems and networks, University of Southern California, Los Angeles, CA, 1992
• 2: M. Balakrishnan , C. S. Raghavendra, On Reliability Modeling of Closed Fault-Tolerant Computer Systems, IEEE Transactions on Computers, v.39 n.4, p.571-575, April 1990 [doi>10.1109/12.54852 ]
• 3: C. Bavely and G. Stewart. An Algorithm for Computing Reducing Subspaces by Block Diagonalization. SIAM. J. Numer. Anal., Vol. 16, No. 2: 359--367, April 1979.
• 4: G. Golub and C. Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, MD, 1983.
• 5: G. Golub and J. Wilkinson. Illconditioned Eigensystems and The Computation of The Jordan Canonical Form. SIAM Review, Vol. 18, No. 4: 578--619, Oct. 1976.
• 6: Bo Kågström , Axel Ruhe, An Algorithm for Numerical Computation of the Jordan Normal Form of a Complex Matrix, ACM Transactions on Mathematical Software (TOMS), v.6 n.3, p.398-419, Sept. 1980 [doi>10.1145/355900.355912]
• 7: W. Ledermann and G. E. H. Reuter. Spectral Theory for the Differential Equations of Simple Birth and Death Processes. Phil. Trans. Royal Society, Series A, 246: 321--369, 1954.
• 8: Raymond A. Marie , Andrew L. Reibman , Kishor S. Trivedi, Transient analysis of acyclic markov chains, Performance Evaluation, v.7 n.3, p.175-194, August 1, 1987 [doi>10.1016/0166-5316(87)90039-3]
• 9: J. Muppala, M. Malhotra and K. Trivedi. Stiffness-Tolerant Methods for Transient Analysis of Stiff Markov Chains. Microelectronics and Reliability, Vol 34, No 11 pp 1825--1841, 1994.
• 10: Y. Ng and A. Avizienis. A Unified Reliability Model for Fault-Tolerant Computers. IEEE Trans. on Computers, Vol. C-29, No. 11, Nov. 1980.
• 11: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 12: A. V. Ramesh and K. Trivedi. Semi-Numerical Transient Analysis of Markov Models. Technical Report, Dept. of Electrical Engineering, Duke University, Durham, NC.
• 13: R. Sahner and K. Trivedi. Reliability Modeling Using SHARPE. IEEE Trans. on Reliability, Vol. R-36, No. 2: 186--193, June 1987.
• 14: R A Sahner, A hybrid, combinatorial-Markov method of solving performance and reliability models, Duke University, Durham, NC, 1986
• 15: J. Sjogren. Closed-Form Solution of Decomposable Stochastic Models. Computers Math. Applic., Vol. 23, No. 12: 43--67, 1992.
• 16: B. Smith, J. Boyle, J. Dongarra, B. Garbow, Y. Ikebe, V. Klema, and C. Moler. Matrix Eigensystem Routines: EISPACK Guide. Springer-Verlag, New York, 2 edition, 1971.
• 17: R. M. Smith , Kishor S. Trivedi , A. V. Ramesh, Performability Analysis: Measures, an Algorithm, and a Case Study, IEEE Transactions on Computers, v.37 n.4, p.406-417, April 1988 [doi>10.1109/12.2184 ]
• 18: H. Tardif, K. Trivedi, and A. V. Ramesh. Closed-Form Transient Analysis of Markov Chains. Technical Report CS-1988, Dept. of Computer Science, Duke University, Durham, NC, June 1988.
• 19: Kishar Shridharbhai Trivedi, Probability and Statistics with Reliability, Queuing and Computer Science Applications, Prentice Hall PTR, Upper Saddle River, NJ, 1982
• 20: Kishor Trivedi , Joanne Bechta Dugan , Robert Geist , Mark Smotherman, Hybrid reliability modeling of fault-tolerant computer systems, Computers and Electrical Engineering, v.11 n.2-3, p.87-108, 1984 [doi>10.1016/0045-7906(84)90004-1 ]
• 21: W. Whitt. Untold Horrors of the Waiting Room: What the Equilibruim Distribution Will Never Tell About The Queue-Length Process. Management Science, Vol. 5, No. 4: 395--408, April 1983.
• 22: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988