zbMATH — the first resource for mathematics

Implicit ODE solvers with good local error control for the transient analysis of Markov models. (English) Zbl 1411.65092
Summary: Obtaining the transient probability distribution vector of a continuous-time Markov chain (CTMC) using an implicit ordinary differential equation (ODE) solver tends to be advantageous in terms of run-time computational cost when the product of the maximum output rate of the CTMC and the largest time of interest is large. In this paper, we show that when applied to the transient analysis of CTMCs, many implicit ODE solvers are such that the linear systems involved in their steps can be solved by using iterative methods with strict control of the 1-norm of the error. This allows the development of implementations of those ODE solvers for the transient analysis of CTMCs that can be more efficient and more accurate than more standard implementations.
65L05 Numerical methods for initial value problems
60J27 Continuous-time Markov processes on discrete state spaces
65C40 Numerical analysis or methods applied to Markov chains
Full Text: DOI
[1] Grassmann, W. K., Transient solutions in Markovian queueing systems, Comput. Oper. Res., 4, 1, 47-53, (1977)
[2] Gross, D.; Miller, D. R., The randomization technique as a modeling tool and solution procedure for transient Markov processes, Oper. Res., 32, 2, 343-361, (1984) · Zbl 0536.60078
[3] van Moorsel, A. P.A.; Sanders, W. H., Adaptive uniformization, Stoch. Models, 10, 3, 619-647, (1994) · Zbl 0804.60061
[4] Van Moorsel, A. P.A.; Sanders, W. H., Transient solution of Markov models by combining adaptive and standard uniformization, IEEE Trans. Reliab., 46, 3, 430-440, (1997)
[5] Sidje, R. B.; Burrage, K.; MacNamara, S., Inexact uniformization method for computing transient distributions of Markov chains, SIAM J. Sci. Comput., 29, 6, 2562-2580, (2007) · Zbl 1154.65300
[6] Sidje, R. B., Expokit: a software package for computing matrix exponentials, ACM Trans. Math. Softw., 24, 1, 130-156, (1998) · Zbl 0917.65063
[7] Gershgorin, S. A., Uber die abgrenzung der eigenwerte einer matrix, Bull. Russ. Acad. Sci. Math. Ser., 6, 749-754, (1931) · JFM 57.1340.06
[8] Reibman, A.; Trivedi, K., Numerical transient analysis of Markov models, Comput. Oper. Res., 15, 1, 19-36, (1988) · Zbl 0642.60097
[9] Dahlquist, G. G., A special stability problem for linear multistep methods, BIT Numer. Math., 3, 1, 27-43, (1963) · Zbl 0123.11703
[10] Malhotra, M.; Muppala, J. K.; Trivedi, K. S., Stiffness-tolerant methods for transient analysis of stiff Markov chains, Microelectron. Reliab., 34, 11, 1825-1841, (1994)
[11] Dunkel, J.; Stahl, H., On the transient analysis of stiff Markov chains, Dependable Computing for Critical Applications 3, 137-160, (1993), Springer
[12] Lindemann, C.; Malhotra, M.; Trivedi, K. S., Numerical methods for reliability evaluation of Markov closed fault-tolerant systems, IEEE Trans. Reliab., 44, 4, 694-704, (1995)
[13] Malhotra, M., A computationally efficient technique for transient analysis of repairable Markovian systems, Perform. Eval., 24, 311-331, (1995) · Zbl 0876.60073
[14] Tombuyses, B.; Devoogth, J., Solving Markovian systems of O.D.E. for availability and reliability calculations, Reliab. Eng. Syst. Saf., 48, 47-55, (1995)
[15] Malhotra, M., An efficient stiffness-insensitive method for transient analysis of Markov availability models, IEEE Trans. Reliab., 45, 3, 426-428, (1996)
[16] Sidje, R. B.; Stewart, W. J., A numerical study of large sparse matrix exponentials arising in Markov chains, Comput. Stat. Data Anal., 29, 3, 345-368, (1999) · Zbl 1042.65508
[17] Bank, R. E.; Coughran, W. M.; Fichtner, W.; Grosse, E. H.; Rose, D. J.; Smith, R. K., Transient simulation of silicon devices and circuits, IEEE Trans. Comput. Aided Des. Integr. Circ. Syst., 4, 4, 436-451, (1985)
[18] Ehle, B. L., On Padé approximations to the exponential function and A-stable methods for the numerical solution of initial value problems, Tech. Rep. CSRR 2010, (1969), Dept. AACS Univ. of Waterloo
[19] Fehlberg, E., Klassische Runge-Kutta-formeln vierter und niedrigerer ordnung mit schrittweiten-kontrolle und ihre anwendung auf wrmeleitungsprobleme, Computing, 6, 1-2, 61-71, (1970) · Zbl 0217.53001
[20] Curtois, P. J., Decomposability: Queueing and Computer System Applications, (1977), Academic Press
[21] Maire, R. A.; Reibman, A. L.; Trivedi, K. S., Transient analysis of acyclic Markov chains, Perform. Eval., 7, 3, 175-194, (1987) · Zbl 0643.60072
[22] Hairer, E.; Wanner, G., Solving Ordinary Differential Equations II: Stiff and Differential-Algebraic Problems, 2nd revised edition, (1996), Springer · Zbl 0859.65067
[23] Axelsson, O., A class of A-stable methods, BIT Numer. Math., 9, 3, 185-199, (1969) · Zbl 0208.41504
[24] Butcher, J. C., Implicit Runge-Kutta processes, Math. Comput., 18, 85, 50-64, (1964) · Zbl 0123.11701
[25] Byrne, G. D., Pragmatic experiments with Krylov methods in the stiff ODE setting, (Cash, J. R.; Gladwell, I., (1992), Oxford University Press), 323-356 · Zbl 0769.65038
[26] Varga, R. S., Matrix iterative analysis, Springer Series in Computational Mathematics, 27, (2009), Springer · Zbl 1216.65042
[27] Saad, Y.; Schultz, M. H., GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 3, 856-869, (1986) · Zbl 0599.65018
[28] Sonneveld, P., CGS, a fast Lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 10, 1, 36-52, (1989) · Zbl 0666.65029
[29] Barrett, R.; Berry, M.; Chan, T. F.; Demmel, J.; Donato, J.; Dongarra, J., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd Edition, (1994), SIAM Philadelphia, PA
[30] van der, V. H.A., Bi-CGSTAB: A fast and smoothly converging variant of bi-CG for the solution of nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 13, 2, 631-644, (1992) · Zbl 0761.65023
[31] Ahlberg, J. H.; Nilson, E. N., Convergence properties of the spline fit, J. Soc. Ind. Appl. Math., 11, 1, 95-104, (1963) · Zbl 0196.48701
[32] Varah, J. M., A lower bound for the smallest singular value of a matrix, Linear Algebra Appl., 11, 3-5, (1975) · Zbl 0312.65028
[33] Varga, R. S., On recurring theorems on diagonal dominance, Linear Algebra Appl., 13, 1, 1-9, (1976) · Zbl 0336.15007
[34] Bagnara, R., A unified proof for the convergence of Jacobi and Gauss-Seidel methods, SIAM Rev., 37, 1, 93-97, (1995) · Zbl 0824.65013
[35] Hosea, M. E.; Shampine, L. F., Analysis and implementation of TR-BDF2, Appl. Numer. Math., 20, 1, 21-37, (1996) · Zbl 0859.65076
[36] Byrne, G. D.; Hindmarsh, A. C., A polyalgorithm for the numerical solution of ordinary differential equations, ACM Trans. Math. Softw., 1, 1, 71-96, (1975) · Zbl 0311.65049
[37] Gear, C. W., Numerical Initial Value Problems in Ordinary Differential Equations, (1971), Prentice Hall · Zbl 1145.65316
[38] Jackson, K. R.; Sacks-Davis, R., An alternative implementation of variable step-size multistep formulas for stiff odes, ACM Trans. Math. Softw., 6, 3, 295-318, (1980) · Zbl 0434.65046
[39] Saad, Y., ILUT: A dual threshold incomplete LU factorization, Numer. Linear Algebra Appl., 1, 4, 387-402, (1994) · Zbl 0838.65026
[40] Hindmarsh, A. C.; Brown, P. N.; Grant, K. E.; Lee, S. L.; Serban, R.; Shumaker, D. E., SUNDIALS: suite of nonlinear and differential/algebraic equation solvers, ACM Trans. Math. Softw., 31, 3, 363-396, (2004) · Zbl 1136.65329
[41] Stallman, R. M., The GCC Developer Community, Using the GNU Compiler Collection. For GCC version 4.4.7, (2012), Free Software Foundation
[42] IEEEStd 754-1985 Standard for Binary Floating-Point Arithmetic, IEEE Comput. Soc., 1985.
[43] Maple 15, Maplesoft, a division of Waterloo Maple Inc., Waterloo, Ontario, 2011.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.