Approximating stationary measures of structured continuous-time Markov models using matrix diagrams

ABSTRACT

We consider the stationary solution of large ergodic continuous-time Markov chains (CTMCs) with a finite state space S, i.e., the computation of π as solution of π · Q = 0 subject to ∑_iεsπ[i] = 1, where Q coincides with transition rate matrix R except in its diagonal elements, Q[i, i] = - ∑_jεs R [i, j].

REFERENCES

• 1: V. Amoia, G. De Micheli, and M. Santomauro. Computer-oriented formulation of transition-rate matrices via Kronecker algebra. IEEE Trans. Rel., 30:123--132, June 1981.
• 2: Peter Buchholz , Gianfranco Ciardo , Susanna Donatelli , Peter Kemper, Complexity of Memory-Efficient Kronecker Operations with Applications to the Solution of Markov Models, INFORMS Journal on Computing, v.12 n.3, p.203-222, July 2000 [doi>10.1287/ijoc.12.3.203.12634]
• 3: G. Ciardo , R. L. Jones, III , A. S. Miner , R. I. Siminiceanu, Logic and stochastic modeling with SMART, Performance Evaluation, v.63 n.6, p.578-608, June 2006 [doi>10.1016/j.peva.2005.06.001]
• 4: Gianfranco Ciardo , Andrew S. Miner, A Data Structure for the Efficient Kronecker Solution of GSPNs, Proceedings of the The 8th International Workshop on Petri Nets and Performance Models, p.22, September 08-10, 1999
• 5: Paulo Fernandes , Brigitte Plateau , William J. Stewart, Efficient descriptor-vector multiplications in stochastic automata networks, Journal of the ACM (JACM), v.45 n.3, p.381-414, May 1998 [doi>10.1145/278298.278303]
• 6: Andrew S. Miner, Efficient Solution of GSPNs Using Canonical Matrix Diagrams, Proceedings of the 9th international Workshop on Petri Nets and Performance Models (PNPM'01), p.101, September 11-14, 2001
• 7: Andrew S. Miner , Gianfranco Ciardo , Susanna Donatelli, Using the exact state space of a Markov model to compute approximate stationary measures, Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.207-216, June 18-21, 2000, Santa Clara, California, United States
• 8: A. Srinivasan, T. Kam, S. Malik, and R. K. Bray-ton. Algorithms for discrete function manipulation. In Int. Conference on CAD, pages 92--95. IEEE Comp. Soc. Press, 1990.
• 9: W. J. Stewart. Introduction to the Numerical Solution of Markov Chains. Princeton University Press, 1994.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Markov processes

General Terms:
Algorithms, Design, Theory