Relaxations for the numerical solutions of some stochastic problems
- 1 January 1988
- journal article
- research article
- Published by Taylor & Francis in Communications in Statistics. Stochastic Models
- Vol. 4 (3) , 387-419
- https://doi.org/10.1080/15326348808807087
Abstract
This paper is concerned with the systematic design of efficient Jacobi and Gauss-Seidel relaxations, and their over-relaxed variants, for the computation of the stationary distributions of continuous-time Markov processes. An important factor in the design of Gauss-Seidel relaxations is the order in which the states of the Markov process is scanned in each iteration; proper designs outperform other relaxations many times over. The analysis shows that in essence each relaxation evolves identically in law with an explicitly identified discrete-time Markov chain, and its convergence rate is given by the ergodic coefficient of the chain. The ergodic coefficient is in turn determined by the connectivity of the graph of a random walk, which is considerably influenced by the ordering selected. Woven into the general theory is the specific analysis of a tandem connection of several machines with finite buffers in which each machine is subject to blocking. Examples of orderings for this system and their salient, comparative properties are given. We report on extensive numerical investigations on various relaxations. The largest system solved has over a million states. We delineate an important class of large problems, which we call “rapidly converging,rdquo; which are tractable by relaxations in the sense that the time constant of the relaxations is 0(log|S|) as |S|→ ∞, where |S| is the number of states in the Markov process. We give evidence that one of the Gauss-Seidel relaxations for the production line with many machines is rapidly converging.Keywords
This publication has 20 references indexed in Scilit:
- Iterative Bounds on the Equilibrium Distribution of a Finite Markov ChainProbability in the Engineering and Informational Sciences, 1987
- Convergent Iterations for Computing Stationary Distributions of Markov ChainsSIAM Journal on Algebraic Discrete Methods, 1986
- Incomplete Factorization of Singular M-MatricesSIAM Journal on Algebraic Discrete Methods, 1986
- Theorems on M-splittings of a singular M-matrix which depend on graph structureLinear Algebra and its Applications, 1984
- Convergent Regular Splittings for Singular M-MatricesSIAM Journal on Algebraic Discrete Methods, 1984
- A Combined Direct-Iterative Method for Certain M-Matrix Linear SystemsSIAM Journal on Algebraic Discrete Methods, 1984
- Matrix Methods for Queuing ProblemsSIAM Journal on Scientific and Statistical Computing, 1983
- Theorems of Stein-Rosenberg type. III. The singular caseLinear Algebra and its Applications, 1982
- Solution of Homogeneous Systems of Linear Equations Arising from Compartmental ModelsSIAM Journal on Scientific and Statistical Computing, 1981
- Finite Queues in Series with Exponential or Erlang Service Times—A Numerical ApproachOperations Research, 1967