Relaxations for the numerical solutions of some stochastic problems.

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. This paper presents results for the Gauss-Seidel relaxations which, first, estimate the rate of convergence and, second, aid the user in selecting the appropriate orderings from knowledge of the directions of flow in the underlying physical model.