×

zbMATH — the first resource for mathematics

A numerical study of large sparse matrix exponentials arising in Markov chains. (English) Zbl 1042.65508
Summary: Krylov subspace techniques have been shown to yield robust methods for the numerical computation of large sparse matrix exponentials and especially the transient solutions of Markov Chains. The attractiveness of these methods results from the fact that they allow us to compute the action of a matrix exponential operator on an operand vector without having to compute, explicitly, the matrix exponential in isolation. In this paper we compare a Krylov-based method with some of the current approaches used for computing transient solutions of Markov chains. After a brief synthesis of the features of the methods used, wide-ranging numerical comparisons are performed on a power challenge array supercomputer on three different models.

MSC:
65C40 Numerical analysis or methods applied to Markov chains
Software:
Expokit; MARCA; RODAS; VODE
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abdallah, H.; Marie, R.: The uniformized power method for transient solutions of Markov processes. Comput. oper. Res. 20, No. 5, 515-526 (1993) · Zbl 0771.68030
[2] Brankin, R.W., Gladwell, I., Shampine, L.F., 1991. RKSUITE: A suite of Runge–Kutta codes for the initial value problem for ODEs, Softreport 91-1. Technical Report. Math. Dept., Southern Methodist University, Dallas, TX, USA.
[3] Brown, P. N.; Byrne, G. D.; Hindmarsh, A. C.: VODE: a variable-coefficient ODE solver. SIAM J. Sci. statist. Comp. 20, 1038-1051 (1989) · Zbl 0677.65075
[4] Burrage, K., 1995. Parallel and Sequential Methods for Ordinary Differential Equations. Oxford University Press, Oxford. · Zbl 0838.65073
[5] Fassino, C., 1993. Computation of matrix functions. Ph.D. Thesis, Università di Pisa, Genova-Udine, Italia.
[6] Gallopoulos, E.; Saad, Y.: Efficient solution of parabolic equations by Krylov approximation methods. SIAM J. Sci. statist. Comput. 13, No. 5, 1236-1264 (1992) · Zbl 0757.65101
[7] Golub, G.H., Van Loan, C.F., 1989. Matrix Computations, 2nd ed. Johns Hopkins University Press, Baltimore. · Zbl 0733.65016
[8] Grassmann, W.: Transient solutions in Markovian queueing systems. Comput. oper. Res. 4, 47-56 (1977)
[9] Gross, D.; Miller, D. R.: The randomization technique as modelling tool and solution procedure for transient Markov processes. Oper. res. 32, No. 2, 343-361 (1984) · Zbl 0536.60078
[10] Hairer, E., Nørsett, S.P., Wanner, G., 1987. Solving Ordinary Differential Equations I, Nonstiff Problems. Springer, Berlin. · Zbl 0638.65058
[11] Hairer, E., Wanner, G., 1991. Solving Ordinary Differential Equations II, Stiff and Differential algebraic Problems. Springer, Berlin. · Zbl 0729.65051
[12] Hochbruck, M.; Lubich, C.: On Krylov subspace approximation to the matrix exponential operator. SIAM J. Numer. anal. 34, No. 5, 1911-1925 (1997) · Zbl 0888.65032
[13] Horn, R.A., Johnson, C.R., 1991. Topics in Matrix Analysis. Cambridge University Press, Cambridge. · Zbl 0729.15001
[14] Moler, C.B., Van Loan, C.F., 1978. Nineteen dubious ways to compute the exponential of a matrix. SIAM Rev. 20(4), 801–836. · Zbl 0395.65012
[15] Philippe, B., Saad, Y., Stewart, W.J., 1992. Numerical methods in Markov chians modeling. Oper. Res. 40 (6). · Zbl 0764.65095
[16] Philippe, B., Sidje, R.B., 1995. Transient solutions of Markov processes by Krylov subspaces. In: Stewart, W.J. (Ed.), 2nd Int. Workshop on the Numerical Solution of Markov Chains, Raleigh, NC, USA. · Zbl 0862.60056
[17] Reibman, A.; Trivedi, K.: Transient analysis of cumulative measures of Markov model behavior. Commu. statist.-stochastic models 5, No. 4, 683-710 (1989) · Zbl 0684.60068
[18] Saad, Y.: Analysis of some Krylov subspace approximations to the matrix exponential operator. SIAM J. Numer. anal. 29, No. 1, 208-227 (1992) · Zbl 0749.65030
[19] Saad, Y., 1992. Numerical Methods for Large Eigenvalue Problems. Wiley, Manchester University Press, New York. · Zbl 0991.65039
[20] Shampine, L.F., Gordon, M.K., 1975. Solution of Ordinary Differential Equations – The Initial Value Problem. W.H. Freeman and Co., San Francisco. · Zbl 0347.65001
[21] Sidje, R.B., 1994. Parallel algorithms for large sparse matrix exponentials: application to numerical transient analysis of markov processes. Ph.D. Thesis, University of Rennes.
[22] Sidje, R.B., 1998. EXPOKIT. Software Package for Computing Matrix Exponentials. ACM-Trans. Mathematical Software, 24 (1) 130–156. · Zbl 0917.65063
[23] Stewart, W.J., MARCA: Markov chain analyser. A software package for Markov modelling. Department of Computer Science, N. Carolina State University, Raleigh, NC 27695-8206, 1988. Also: IEEE Computer Repository No. R76 232, 1976 and IRISA Publication Interne No. 45, Université de Rennes, France.
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.