Complexity of Memory-Efficient Kronecker Operations with Applications to the Solution of Markov Models

References

• Ajmone Marsan M., Balbo G., Conte G. A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems. ACM Trans. Comp. Syst. (1984) 2:93–122Crossref, Google Scholar
• Ajmone Marsan M., Balbo G., Conte G., Donatelli S., Franceschinis G.Modelling with Generalized Stochastic Petri Nets (1995) (Wiley, New York) Google Scholar
• Bause F., Buchholz P., Kemper P., Puigjaner R., Savino N., Serra B. A toolbox for functional and quantitative analysis of DEDS. Proc. 10th Int. Conf. on Modelling Techniques and Tools for Computer Performance Evaluation (1998) (Springer-Verlag, Berlin) 356–359lecture notes in Computer Science 1469Crossref, Google Scholar
• Buchholz P., Balbo G., Serazzi G. Numerical solution methods based on structured descriptions of Markovian models. Computer Performance Evaluation (1991) (Elsevier Science Publishers (North-Holland) Amsterdam)251–267Google Scholar
• Buchholz P. A class of hierarchical queueing networks and their analysis. Queueing Systems (1994) 15:59–80Crossref, Google Scholar
• Buchholz P. An aggregation/disaggregation algorithm for stochastic automata networks. Probability in the Engineering and Informational Sciences (1997a) 11:229–253Crossref, Google Scholar
• Buchholz P. Hierarchical structuring of superposed GSPNs. Proc. 7th Int. Workshop on Petri Nets and Performance Models (PNPM'97), St. Malo, France (1997b) (IEEE Comp. Soc. Press, New York) 81–90Crossref, Google Scholar
• Buchholz P. Structured analysis approaches for large Markov chains. Applied Numerical Mathematics (1999) 31:375–404Crossref, Google Scholar
• Ciardo G., Blakemore A., Chimento P.F.J., Muppala J.K., Trivedi K.S., Meyer C., Plemmons R.J. Automated generation and analysis of Markov reward models using stochastic reward nets. Linear Algebra, Markov Chains, and Queueing Models (1993) (Springer- Verlag, Berlin) 145–191IMA Volumes in Mathematics and its Applications 48Crossref, Google Scholar
• Ciardo G. A.S. Miner. SMART: simulation and Markovian analyzer for reliability and timing. Proc. IEEE International Computer Performance and Dependability Symposium (IPDS'96), Urbana- Champaign, IL (1996) (IEEE Comp. Soc. Press, New York) 60Crossref, Google Scholar
• Ciardo G., Miner A.S., Marie R., Plateau B., Calzarossa M., Rubino G. Storage alternatives for large structured state spaces. Proc. 9th Int. Conf. on Modelling Techniques and Tools for Computer Performance Evaluation, Lecture Notes in Computer Science 1245, St. Malo, France (1997) (Springer-Verlag, Berlin) 44–57Crossref, Google Scholar
• Ciardo G., Tilgner M. On the use of Kronecker operators for the solution of generalized stochastic Petri nets. (1996) (Institute for Computer Applications in Science and Engineering, Hampton, VA) . ICASE Report 96-35Google Scholar
• Davio M. Kronecker products and shuffle algebra. IEEE Trans. Comp. C-30 (1981) 116–125Crossref, Google Scholar
• Deavours D.D., Sanders W.H., Marie R., Plateau B., Calzarossa M., Rubino G. An efficient disk-based tool for solving very large Markov models. Proc. 9th Int. Conf. on Modelling Techniques and Tools for Computer Performance Evaluation, Lecture Notes in Computer Science 1245, St. Malo, France (1997a) (Springer-Verlag, Berlin) 58–71Crossref, Google Scholar
• Deavours D.D., Sanders W.H. “On-the-fly” solution techniques for stochastic Petri nets and extensions. Proc. 7th Int. Workshop on Petri Nets and Performance Models (PNPM'97), St. Malo, France (1997b) (IEEE Comp. Soc. Press, New York) 132–141Crossref, Google Scholar
• Donatelli S. Superposed stochastic automata: A class of stochastic Petri nets with parallel solution and distributed state space. Perf. Eval. (1993) 18:21–26Crossref, Google Scholar
• Donatelli S., Valette R. Superposed generalized stochastic Petri nets: Definition and efficient solution. Application and Theory of Petri Nets 1994 (Proc. 15th Int. Conf. on Applications and Theory of Petri Nets) Lecture Notes in Computer Science 815, Zaragoza, Spain (1994) (Springer-Verlag, Berlin) 258–277Crossref, Google Scholar
• Fernandes P., Plateau B., Stewart W.J. Numerical issue for stochastic automata networks. Proc. of the 4th Workshop on Process Algebra and Performance Modelling (PAPM) (1996) (University of Torino, Torino, Italy) . Technical ReportGoogle Scholar
• Fernandes P., Plateau B., Stewart W.J. Efficient descriptorvector multiplication in stochastic automata networks. Journal of the ACM (1998) 45:381–414Crossref, Google Scholar
• Howard R.A.Dynamic Probabilistic Systems, Volume II: Semi-Markov and Decision Processes (1971) (Wiley, New York) Google Scholar
• Kemper P. Numerical analysis of superposed GSPNs. IEEE Trans. Softw. Eng. (1996a) 22:615–628Crossref, Google Scholar
• Kemper P., Billington J., Reisig W. Reachability analysis based on structured representations. Application and Theory of Petri Nets 1996 (Proc. 17th Int. Conf. on Applications and Theory of Petri Nets, Osaka, Japan) (1996b) (Springer-Verlag, Berlin) 269–288lecture notes in Computer Science 1091Crossref, Google Scholar
• Kemper P. Superposition of generalized stochastic Petri nets and its impact on performance analysis. (1996c) (Universität Dortmund, Dortmund, Germany) . Ph.D. thesisGoogle Scholar
• Lubachevsky B., Mitra D. A chaotic asynchronous algorithm for computing the fixed point of nonnegative matrices with unit spectral radius. J. ACM (1986) 33:130–150Crossref, Google Scholar
• Plateau B. On the stochastic structure of parallelism and synchronisation models for distributed algorithms. Proc. 1985 ACM SIGMETRICS Conf. on Measurement and Modeling of Computer Systems, Austin, TX (1985) (ACM Sigmetrics, New York) 147–153Crossref, Google Scholar
• Plateau B., Atif K. Stochastic automata network for modeling parallel systems. IEEE Trans. Softw. Eng. (1991) 17:1093–1108Crossref, Google Scholar
• Plateau B., Fourneau J.-M. A methodology for solving Markov models of parallel systems. J. Par. and Distr. Comp. (1991) 12:370–387Crossref, Google Scholar
• Stewart W.J.Introduction to the Numerical Solution of Markov Chains (1994) (Princeton University Press, Princeton, NJ) Google Scholar
• Stewart W.J., Atif K., Plateau B. The numerical solution of stochastic automata networks. Eur. J. of Oper. Res. (1995) 86:503–525Crossref, Google Scholar
• Uysal E., Dayar T. Iterative methods based on splittings for stochastic automata networks. Eur. J. Op. Res. (1998) 110:166–186Crossref, Google Scholar