1995 International Meeeting on
Computations with Markov Chains.
Raleigh, NC, USA.

Proceedings published by Kluwer Acaedmic Publishers.

``Computations with Markov Chains''

Edited by

William J. Stewart

Billy's Home Page

COMPUTATIONS WITH MARKOV CHAINS: Proceedings of the 2nd International Workshop on the Numerical Solution of Markov Chains is a collection of peer-reviewed articles presented at the Workshop on Numerical Solutions of Markov Chains which was held January 15 to January 18, 1995 in Raleigh, North Carolina. These papers provide an authoritative overview of the field, including coverage of recent developments, current status of ongoing research, and projections for future directions in the field.


Kluwer Academic Publishers
101 Philip Drive
Assinippi Park
Norwell, Massachusetts 02061, USA
ISBN 0-7923-9550-6

Table of Contents

  1. Detecting Block GI/M/1 and Block M/G/1 Matrices from Model Specifications.
    S. Berson and R. Muntz ... 1

  2. On Cyclic Reduction Applied to a Class of Toeplitz-like Matrices Arising in Queueing Problems.
    D. Bini and B. Meini ... 21

  3. A Markov Modulated, Nearly Completely Decomposable M/M/1 Queue.
    G. Latouche and P.J. Schweitzer ... 39

  4. Preconditioned Krylov Subspace Methods for the Numerical Solution of Markov Chains.
    Y. Saad ... 49

  5. A Parallel Block Projection Method of the Cimmino Type for Finite Markov Chains.
    M. Benzi, F. Sgallari and G. Spaletta ... 65

  6. Iterative Methods for Queueing Models with Batch Arrivals.
    R.H. Chan and W-K. Ching ... 81

  7. Transient Solutions of Markov Processes by Krylov Subspaces.
    R.B. Sidje and B. Philippe ... 95

  8. Exact Methods for the Transient Analysis of Nonhomogeneous Continuous Time Markov Chains.
    A. Rindos, S. Woolet, I. Viniotis, and K. Trivedi ... 121

  9. Time-Dependent behavior of Redundant Systems with Deterministic Repair.
    D. Logothetis and K. Trivedi ... 135

  10. What is Fundamental for Markov Chains: First Passage Times, Fundamental Matrices, and Group Generalized Inverses.
    D.P. Heyman and D.P. O'Leary ... 151

  11. Immediate Events in Markov Chains.
    Winfried K. Grassmann Yuru Wang ... 163

  12. Compositional Markovian Modelling Using a Process Algebra.
    J. Hillston ... 177

  13. Equivalence Relations for Stochastic Automata Networks.
    P. Buchholz ... 197

  14. Graphs and Stochastic Automata Networks.
    J-M. Fourneau and F. Quessette ... 217

  15. Analyzing Sample Path Data from Markov Chain Sampling Experiments.
    G. Fishman ... 237

  16. Resource Sharing Models with State-Dependent Arrivals of Batches.
    G.L. Choudhury, K.K. Leung and W. Whitt ... 255

  17. Implementable Policies: Discounted Cost Case.
    V.G. Kulkarni and Y. Serin ... 283

  18. Two Bounding Schemes for the Steady-State Solution of Markov Chains.
    P. Semal ... 307

  19. The Power-Series Algorithm for Markovian Queueing Networks.
    W.B. van den Hout and J.P.C. Blanc ... 321

  20. Discrete-Time Markovian Stochastic Petri Nets.
    G. Ciardo ... 339

  21. Concurrent Generalized Petri Nets.
    V. Catania, A. Puliafito, M. Scarpa and L. Vita. ... 359

  22. Exploiting Isomorphisms and Special Structures in the Analysis of Markov Regenerative Stochastic Petri Nets.
    C. Lindemann ... 383

  23. Numerical Solution of Large Finite Markov Chains by Algebraic Multigrid Techniques.
    U.R. Krieger ... 403

  24. On the Utility of the Multi-Level Algorithm for the Solution of Nearly Completely Decomposable Markov Chains.
    S.T. Leutenegger and G. Horton ... 425

  25. A Computationally Efficient Algorithm for Characterizing the Superposition of Multiple Heterogeneous Interrupted Bernoulli Processes.
    K.M. Elsayed and H.G. Perros ... 443

  26. Generalized Folding Algorithm for Transient Analysis of Finite QBD Processes and its Queueing Applications.
    S-Q. Li and H-D. Sheng ... 463

  27. Efficient Solutions for a Class of Non-Markovian Models.
    E. de Souza e Silva, H.R. Gail and R.R. Muntz ... 483

  28. Markovian Arrival and Service Communication Systems: Spectral Expansions, Separability and Kronecker-Product Forms.
    A. Elwalid and D. Mitra ... 507

  29. Empirical Comparison of Uniformization Methods for Continuous-Time Markov Chains.
    J.D. Diener and W.H. Sanders ... 547

  30. Numerical Methods for M/G/1 Type Queues.
    G. Latouche and G.W. Stewart ... 571

  31. Closing the Gap between Classical and Tensor Based Iteration Techniques.
    P. Kemper ... 582

  32. Adaptive Relaxation for the Steady-State Analysis of Markov Chains
    G. Horton ... 585

  33. State Space Decomposition for Large Markov Chains.
    M. Rieders ... 587

  34. Aggregation/Disaggregation Method on Parallel Computer.
    Y. Takahashi and K.Fujimoto ... 591

  35. Parallel Implementation of the GTH Algorithm for Markov Chains.
    D.M. Cohen, D.P. Heyman, A. Rabinovitch, and D. Brown ... 594

  36. A Parallel Implementation of the Block-GTH Algorithm.
    Y-J.J. Wu ... 597

  37. Approximate Computation of Sojourn Time Distribution in Open Queueing Networks.
    V. Mainkar, K.S. Trivedi and A.J. Rindos ... 599

Billy's Home Page