2020
Journal article
Open Access
Computing performability measures in Markov chains by means of matrix functions
Masetti G., Robol L.
Availability Computational Mathematics Mathematics - Numerical Analysis Matrix functions FOS: Mathematics Markov chains Performance measures Reliability Applied Mathematics Numerical Analysis (math.NA)
We discuss the efficient computation of performance, reliability, and availability measures for Markov chains; these metrics - and the ones obtained by combining them, are often called performability measures. We show that this computational problem can be recasted as the evaluation of a bilinear form induced by appropriate matrix functions, and thus solved by leveraging the fast methods available for this task.
Source: Journal of computational and applied mathematics 368 (2020). doi:10.1016/j.cam.2019.112534
Publisher: Koninklijke Vlaamse Ingenieursvereniging, Amsterdam , Belgio
[1] Afanasjew, M., Eiermann, M., Ernst, O. G., Guttel, S., 2008. Implementation of a restarted Krylov subspace method for the evaluation of matrix functions. Linear Algebra Appl. 429 (10), 2293{2314.
[2] Al-Mohy, A. H., Higham, N. J., 2011. Computing the action of the matrix exponential, with an application to exponential integrators. SIAM J. Sci. Comput. 33 (2), 488{511.
[3] Avizienis, A., Laprie, J.-C., Randell, B., Landwehr, C., Jan. 2004. Basic concepts and taxonomy of dependable and secure computing. IEEE Trans. Dependable Secur. Comput. 1 (1), 11{33.
[4] Balsamo, S., Onvural, R. O., Persone, V. D. N., 2001. Analysis of Queueing Networks with Blocking. Kluwer Academic Publishers, Norwell, MA, USA.
[5] Barbaresco, F., 2009. New foundation of radar doppler signal processing based on advanced di erential geometry of symmetric spaces: Doppler matrix cfar and radar application. In: International Radar Conference. Vol. 82.
[6] Benzi, M., Boito, P., 2014. Decay properties for functions of matrices over C -algebras. Linear Algebra Appl. 456, 174{198.
[7] Bini, D. A., Massei, S., Robol, L., 2017. E cient cyclic reduction for quasibirth-death problems with rank structured blocks. Appl. Numer. Math. 116, 37{46.
[8] Bini, D. A., Massei, S., Robol, L., 2017. On the decay of the o -diagonal singular values in cyclic reduction. Linear Algebra Appl. 519, 27{53.
[9] Crouzeix, M., Palencia, C., 2017. The numerical range is a (1+p2)-spectral set. SIAM J. Matrix Anal. Appl. 38 (2), 649{655.
[10] Deavours, D. D., Clark, G., Courtney, T., Daly, D., Derisavi, S., Doyle, J. M., Sanders, W. H., Webster, P. G., 2002. The Mobius framework and its implementation. IEEE Trans. on Softw. Eng. 28 (10), 956{969.
[11] Estrada, E., Higham, D. J., 2010. Network properties revealed through matrix functions. SIAM Rev. 52 (4), 696{714.
[12] Fenu, C., Martin, D., Reichel, L., Rodriguez, G., 2013. Network analysis via partial spectral factorization and Gauss quadrature. SIAM J. Sci. Comput. 35 (4), A2046{A2068.
[13] Fletcher, P. T., Joshi, S., 2007. Riemannian geometry for the statistical analysis of di usion tensor data. Signal Process. 87 (2), 250{262.
[14] Frommer, A., Guttel, S., Schweitzer, M., 2014. E cient and stable Arnoldi restarts for matrix functions based on quadrature. SIAM J. Matrix Anal. Appl. 35 (2), 661{683.
[15] Gander, M. J., Guttel, S., 2013. PARAEXP: a parallel integrator for linear initial-value problems. SIAM J. Sci. Comput. 35 (2), C123{C142.
[16] Higham, N. J., 2008. Functions of matrices. Theory and computation. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA.
[17] Hillston, J., 1996. A Compositional Approach to Performance Modelling. Cambridge University Press, New York, NY, USA.
[18] Hochbruck, M., Lubich, C., Selhofer, H., 1998. Exponential integrators for large systems of di erential equations. SIAM J. Sci. Comput. 19 (5), 1552{ 1574.
[19] Martinez, J., Trivedi, K., Cheng, B., 2017. E cient computation of the mean time to security failure in cyber physical systems. In: Proceedings of the 10th EAI International Conference on Performance Evaluation Methodologies and Tools on 10th EAI International Conference on Performance Evaluation Methodologies and Tools. ICST, ICST, Brussels, Belgium, pp. 109{115.
[20] Massei, S., Robol, L., 2017. Decay bounds for the numerical quasiseparable preservation in matrix functions. Linear Algebra Appl. 516, 212{242.
[21] Meyer, J. F., 1980. On evaluating the performability of degradable computing systems. IEEE Transactions on computers (8), 720{731.
[22] Meyer, J. F., July 1982. Closed-Form Solutions of Performability. IEEE Transactions on Computers C-31 (7), 648{657.
[23] Plemmons, R. J., 1981. M -matrix characterizations. I. Nonsingular M - matrices. Yingyong Shuxue yu Jisuan Shuxue (2), 48{55, translated from the English by Jiong Sheng Li.
[24] Rathi, Y., Tannenbaum, A., Michailovich, O., 2007. Segmenting images on the tensor manifold. In: Computer Vision and Pattern Recognition, 2007. CVPR'07. IEEE Conference on. IEEE, pp. 1{8.
[25] Reibman, A., Smith, R., Trivedi, K., 1989. Markov and Markov reward model transient analysis: An overview of numerical approaches. European Journal of Operational Research 40 (2), 257 { 267.
[26] Reibman, A., Trivedi, K., 1989. Transient analysis of cumulative measures of markov model behavior. Communications in Statistics. Stochastic Models 5 (4), 683{710.
[27] Trivedi, K. S., 2002. Probability and Statistics with Reliability, Queuing and Computer Science Applications, 2nd Edition. John Wiley and Sons Ltd., Chichester, UK.
[28] Trivedi, K. S., Bobbio, A., 2017. Reliability and Availability Engineering: Modeling, Analysis, and Applications. Cambridge University Press.
[29] Varga, R. S., 2010. Gersgorin and his circles. Vol. 36. Springer Science & Business Media.
[30] Yang, Q., Turner, I., Liu, F., Ilic, M., 2011. Novel numerical methods for solving the time-space fractional di usion equation in two dimensions. SIAM J. Sci. Comp. 33 (3), 1159{1180.
[2] Al-Mohy, A. H., Higham, N. J., 2011. Computing the action of the matrix exponential, with an application to exponential integrators. SIAM J. Sci. Comput. 33 (2), 488{511.
[3] Avizienis, A., Laprie, J.-C., Randell, B., Landwehr, C., Jan. 2004. Basic concepts and taxonomy of dependable and secure computing. IEEE Trans. Dependable Secur. Comput. 1 (1), 11{33.
[4] Balsamo, S., Onvural, R. O., Persone, V. D. N., 2001. Analysis of Queueing Networks with Blocking. Kluwer Academic Publishers, Norwell, MA, USA.
[5] Barbaresco, F., 2009. New foundation of radar doppler signal processing based on advanced di erential geometry of symmetric spaces: Doppler matrix cfar and radar application. In: International Radar Conference. Vol. 82.
[6] Benzi, M., Boito, P., 2014. Decay properties for functions of matrices over C -algebras. Linear Algebra Appl. 456, 174{198.
[7] Bini, D. A., Massei, S., Robol, L., 2017. E cient cyclic reduction for quasibirth-death problems with rank structured blocks. Appl. Numer. Math. 116, 37{46.
[8] Bini, D. A., Massei, S., Robol, L., 2017. On the decay of the o -diagonal singular values in cyclic reduction. Linear Algebra Appl. 519, 27{53.
[9] Crouzeix, M., Palencia, C., 2017. The numerical range is a (1+p2)-spectral set. SIAM J. Matrix Anal. Appl. 38 (2), 649{655.
[10] Deavours, D. D., Clark, G., Courtney, T., Daly, D., Derisavi, S., Doyle, J. M., Sanders, W. H., Webster, P. G., 2002. The Mobius framework and its implementation. IEEE Trans. on Softw. Eng. 28 (10), 956{969.
[11] Estrada, E., Higham, D. J., 2010. Network properties revealed through matrix functions. SIAM Rev. 52 (4), 696{714.
[12] Fenu, C., Martin, D., Reichel, L., Rodriguez, G., 2013. Network analysis via partial spectral factorization and Gauss quadrature. SIAM J. Sci. Comput. 35 (4), A2046{A2068.
[13] Fletcher, P. T., Joshi, S., 2007. Riemannian geometry for the statistical analysis of di usion tensor data. Signal Process. 87 (2), 250{262.
[14] Frommer, A., Guttel, S., Schweitzer, M., 2014. E cient and stable Arnoldi restarts for matrix functions based on quadrature. SIAM J. Matrix Anal. Appl. 35 (2), 661{683.
[15] Gander, M. J., Guttel, S., 2013. PARAEXP: a parallel integrator for linear initial-value problems. SIAM J. Sci. Comput. 35 (2), C123{C142.
[16] Higham, N. J., 2008. Functions of matrices. Theory and computation. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA.
[17] Hillston, J., 1996. A Compositional Approach to Performance Modelling. Cambridge University Press, New York, NY, USA.
[18] Hochbruck, M., Lubich, C., Selhofer, H., 1998. Exponential integrators for large systems of di erential equations. SIAM J. Sci. Comput. 19 (5), 1552{ 1574.
[19] Martinez, J., Trivedi, K., Cheng, B., 2017. E cient computation of the mean time to security failure in cyber physical systems. In: Proceedings of the 10th EAI International Conference on Performance Evaluation Methodologies and Tools on 10th EAI International Conference on Performance Evaluation Methodologies and Tools. ICST, ICST, Brussels, Belgium, pp. 109{115.
[20] Massei, S., Robol, L., 2017. Decay bounds for the numerical quasiseparable preservation in matrix functions. Linear Algebra Appl. 516, 212{242.
[21] Meyer, J. F., 1980. On evaluating the performability of degradable computing systems. IEEE Transactions on computers (8), 720{731.
[22] Meyer, J. F., July 1982. Closed-Form Solutions of Performability. IEEE Transactions on Computers C-31 (7), 648{657.
[23] Plemmons, R. J., 1981. M -matrix characterizations. I. Nonsingular M - matrices. Yingyong Shuxue yu Jisuan Shuxue (2), 48{55, translated from the English by Jiong Sheng Li.
[24] Rathi, Y., Tannenbaum, A., Michailovich, O., 2007. Segmenting images on the tensor manifold. In: Computer Vision and Pattern Recognition, 2007. CVPR'07. IEEE Conference on. IEEE, pp. 1{8.
[25] Reibman, A., Smith, R., Trivedi, K., 1989. Markov and Markov reward model transient analysis: An overview of numerical approaches. European Journal of Operational Research 40 (2), 257 { 267.
[26] Reibman, A., Trivedi, K., 1989. Transient analysis of cumulative measures of markov model behavior. Communications in Statistics. Stochastic Models 5 (4), 683{710.
[27] Trivedi, K. S., 2002. Probability and Statistics with Reliability, Queuing and Computer Science Applications, 2nd Edition. John Wiley and Sons Ltd., Chichester, UK.
[28] Trivedi, K. S., Bobbio, A., 2017. Reliability and Availability Engineering: Modeling, Analysis, and Applications. Cambridge University Press.
[29] Varga, R. S., 2010. Gersgorin and his circles. Vol. 36. Springer Science & Business Media.
[30] Yang, Q., Turner, I., Liu, F., Ilic, M., 2011. Novel numerical methods for solving the time-space fractional di usion equation in two dimensions. SIAM J. Sci. Comp. 33 (3), 1159{1180.
Metrics
Back to previous page
BibTeX entry
@article{oai:it.cnr:prodotti:424806,
title = {Computing performability measures in Markov chains by means of matrix functions},
author = {Masetti G. and Robol L.},
publisher = {Koninklijke Vlaamse Ingenieursvereniging, Amsterdam , Belgio},
doi = {10.1016/j.cam.2019.112534 and 10.48550/arxiv.1803.06322},
journal = {Journal of computational and applied mathematics},
volume = {368},
year = {2020}
}
0000-0002-5165-275X
