×

Lumpable continuous-time stochastic automata networks. (English) Zbl 1035.90012

Summary: The generator matrix of a continuous-time stochastic automata network (SAN) is a sum of tensor products of smaller matrices, which may have entries that are functions of the global state space. This paper specifies easy to check conditions for a class of ordinarily lumpable partitionings of the generator of a continuous-time SAN in which aggregation is performed automaton by automaton. When there exists a lumpable partitioning induced by the tensor representation of the generator, it is shown that an efficient aggregation-iterative disaggregation algorithm may be employed to compute the steady-state distribution. The results of experiments with two SAN models show that the proposed algorithm performs better than the highly competitive block Gauss–Seidel in terms of both the number of iterations and the time to converge to the solution.

MSC:

90B15 Stochastic network models in operations research

Software:

MARCA; PEPS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Buchholz, P., Exact and ordinary lumpability in finite Markov chains, Journal of Applied Probability, 31, 59-75 (1994) · Zbl 0796.60073
[2] Buchholz, P., Hierarchical Markovian models: Symmetries and reduction, Performance Evaluation, 22, 93-110 (1995)
[3] Buchholz, P., Equivalence relations for stochastic automata networks, (Stewart, W. J., Computations with Markov Chains (1995), Kluwer: Kluwer Boston, MA), 197-215 · Zbl 0861.68004
[4] Buchholz, P., An aggregation⧹disaggregation algorithm for stochastic automata networks, Probability in the Engineering and Informational Sciences, 11, 229-253 (1997) · Zbl 1096.90512
[5] P. Buchholz, Projection methods for the analysis of stochastic automata networks, in: B. Plateau, W.J. Stewart, M. Silva, (Eds.), Proceedings of the 3rd International Workshop on the Numerical Solution of Markov Chains, Prensas Universitarias de Zaragoza, Spain, 1999, pp. 149-168; P. Buchholz, Projection methods for the analysis of stochastic automata networks, in: B. Plateau, W.J. Stewart, M. Silva, (Eds.), Proceedings of the 3rd International Workshop on the Numerical Solution of Markov Chains, Prensas Universitarias de Zaragoza, Spain, 1999, pp. 149-168
[6] Buchholz, P., Exact performance equivalence: An equivalence relation for stochastic automata, Theoretical Computer Science, 215, 263-287 (1999) · Zbl 0913.68141
[7] Buchholz, P.; Ciardo, G.; Donatelli, S.; Kemper, P., Complexity of memory-efficient Kronecker operations with applications to the solution of Markov models, INFORMS Journal on Computing, 12, 203-222 (2000) · Zbl 1040.65504
[8] Buchholz, P., Multilevel solutions for structured Markov chains, SIAM Journal on Matrix Analysis and Applications, 22, 342-357 (2000) · Zbl 0967.60075
[9] Chan, R. H.; Ching, W. K., Circulant preconditioners for stochastic automata networks, Numerische Mathematik, 87, 35-57 (2000) · Zbl 0964.65034
[10] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (1990), The MIT Press: The MIT Press Cambridge, MA · Zbl 1158.68538
[11] Davio, M., Kronecker products and shuffle algebra, IEEE Transactions on Computers, C-30, 116-125 (1981) · Zbl 0455.94050
[12] T. Dayar, O.I. Pentakalos, A.B. Stephens, Analytical modeling of robotic tape libraries using stochastic automata, Technical Report TR-97-189, CESDIS, NASA/GSFC, Greenbelt, Maryland, January 1997; T. Dayar, O.I. Pentakalos, A.B. Stephens, Analytical modeling of robotic tape libraries using stochastic automata, Technical Report TR-97-189, CESDIS, NASA/GSFC, Greenbelt, Maryland, January 1997
[13] Dayar, T.; Stewart, W. J., On the effects of using the Grassmann-Taksar-Heyman method in iterative aggregation-disaggregation, SIAM Journal on Scientific Computing, 17, 287-303 (1996) · Zbl 0840.60062
[14] Dayar, T.; Stewart, W. J., Comparison of partitioning techniques for two-level iterative solvers on large, sparse Markov chains, SIAM Journal on Scientific Computing, 21, 1691-1705 (2000) · Zbl 0957.60076
[15] Donatelli, S., Superposed stochastic automata: A class of stochastic Petri nets with parallel solution and distributed state space, Performance Evaluation, 18, 21-36 (1993) · Zbl 0795.68141
[16] Fernandes, P.; Plateau, B.; Stewart, W. J., Efficient descriptor-vector multiplications in stochastic automata networks, Journal of the ACM, 45, 381-414 (1998) · Zbl 1065.68578
[17] Fernandes, P.; Plateau, B.; Stewart, W. J., Optimizing tensor product computations in stochastic automata networks, RAIRO, Operations Research, 32, 3, 325-351 (1998)
[18] P. Fernandes, R.J. Hessel, B. Plateau, W.J. Stewart, PEPS-2000 user manual, June 2000; available online at http://www-apache.imag.fr/software/peps/PEPSman2000.ps.gz; P. Fernandes, R.J. Hessel, B. Plateau, W.J. Stewart, PEPS-2000 user manual, June 2000; available online at http://www-apache.imag.fr/software/peps/PEPSman2000.ps.gz
[19] Fourneau, J.-M.; Quessette, F., Graphs and stochastic automata networks, (Stewart, W. J., Computations with Markov Chains (1995), Kluwer: Kluwer Boston, MA), 217-235 · Zbl 0862.60058
[20] O. Gusak, T. Dayar, J.-M. Fourneau, Stochastic automata networks and near complete decomposability, Technical Report BU-CE-0016, Department of Computer Engineering, Bilkent University, Ankara, Turkey, October 2000; available online at ftp://ftp.cs.bilkent.edu.tr/pub/tech-reports/2000/BU-CE-0016.ps.z; O. Gusak, T. Dayar, J.-M. Fourneau, Stochastic automata networks and near complete decomposability, Technical Report BU-CE-0016, Department of Computer Engineering, Bilkent University, Ankara, Turkey, October 2000; available online at ftp://ftp.cs.bilkent.edu.tr/pub/tech-reports/2000/BU-CE-0016.ps.z · Zbl 0992.60078
[21] Gusak, O.; Dayar, T.; Fourneau, J.-M., Stochastic automata networks and near complete decomposability, SIAM Journal on Matrix Analysis and Applications, 23, 581-599 (2001) · Zbl 0992.60078
[22] O. Gusak, T. Dayar, J.-M. Fourneau, Iterative disaggregation for a class of lumpable discrete-time stochastic automata networks, Performance Evaluation (submitted for publication); O. Gusak, T. Dayar, J.-M. Fourneau, Iterative disaggregation for a class of lumpable discrete-time stochastic automata networks, Performance Evaluation (submitted for publication) · Zbl 1035.90012
[23] Kemeny, J. R.; Snell, J. L., Finite Markov Chains (1960), Van Nostrand: Van Nostrand New York · Zbl 0089.13704
[24] B. Plateau, On the stochastic structure of parallelism and synchronization models for distributed algorithms, in: Proceedings of the ACM SIGMETRICS Conference on Measurement and Modelling of Computer Systems, Austin, Texas, 1985, pp. 147-154; B. Plateau, On the stochastic structure of parallelism and synchronization models for distributed algorithms, in: Proceedings of the ACM SIGMETRICS Conference on Measurement and Modelling of Computer Systems, Austin, Texas, 1985, pp. 147-154
[25] Plateau, B.; Atif, K., Stochastic automata network for modeling parallel systems, IEEE Transactions on Software Engineering, 17, 1093-1108 (1991)
[26] B. Plateau, J.-M. Fourneau, K.-H. Lee, PEPS: A package for solving complex Markov models of parallel systems, in: R. Puigjaner, D. Ptier, (Eds.), Modeling Techniques and Tools for Computer Performance Evaluation, Spain, 1988, pp. 291-305; B. Plateau, J.-M. Fourneau, K.-H. Lee, PEPS: A package for solving complex Markov models of parallel systems, in: R. Puigjaner, D. Ptier, (Eds.), Modeling Techniques and Tools for Computer Performance Evaluation, Spain, 1988, pp. 291-305
[27] Plateau, B.; Fourneau, J.-M., A methodology for solving Markov models of parallel systems, Journal of Parallel and Distributed Computing, 12, 370-387 (1991)
[28] M. Siegle, Structured Markovian performance modeling with automatic symmetry exploitation, in: Short Papers and Tool Descriptions of the 7th International Conference on Modelling Techniques and Tools for Computer Performance Evaluation, Vienna, Austria, 1994, pp. 77-81; M. Siegle, Structured Markovian performance modeling with automatic symmetry exploitation, in: Short Papers and Tool Descriptions of the 7th International Conference on Modelling Techniques and Tools for Computer Performance Evaluation, Vienna, Austria, 1994, pp. 77-81
[29] G.W. Stewart, W.J. Stewart, D.F. McAllister, A two-stage iteration for solving nearly completely decomposable Markov chains, in: G.H. Golub, A. Greenbaum, M. Luskin, (Eds.), Recent Advances in Iterative Methods, IMA Vol. Math. Appl. 60, Springer-Verlag, New York, 1994, pp. 201-216; G.W. Stewart, W.J. Stewart, D.F. McAllister, A two-stage iteration for solving nearly completely decomposable Markov chains, in: G.H. Golub, A. Greenbaum, M. Luskin, (Eds.), Recent Advances in Iterative Methods, IMA Vol. Math. Appl. 60, Springer-Verlag, New York, 1994, pp. 201-216 · Zbl 0804.65148
[30] Stewart, W. J., Introduction to the Numerical Solution of Markov Chains (1994), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0821.65099
[31] Stewart, W. J.; Atif, K.; Plateau, B., The numerical solution of stochastic automata networks, European Journal of Operational Research, 86, 503-525 (1995) · Zbl 0914.90112
[32] Uysal, E.; Dayar, T., Iterative methods based on splittings for stochastic automata networks, European Journal of Operational Research, 110, 166-186 (1998) · Zbl 0934.93061
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.