Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-27T06:52:59.019Z Has data issue: false hasContentIssue false
  • English
  • Français

Quicker Convergence for Iterative Numerical Solutions to Stochastic Problems: Probabilistic Interpretations, Ordering Heuristics, and Parallel Processing

Published online by Cambridge University Press:  27 July 2009

Albert G. Greenberg  and
Robert J. Vanderbei
Albert G. Greenberg
Affiliation:
AT&T Bell Laboratories, Murray Hill, New Jersey
Robert J. Vanderbei
Affiliation:
AT&T Bell Laboratories, Murray Hill, New Jersey
Get access Rights & Permissions [Opens in a new window]

Abstract

Gauss-Seidel is a general method for solving a system of equations (possibly nonlinear). It makes repeated sweeps through the variables; within a sweep as each new estimate for a variable is computed, the current estimate for that variable is replaced with the new estimate immediately, instead of on completion of the sweep. The idea is to use new data as soon as it is computed. Gauss- Seidel is often efficient for computing the invariant measure of a Markov chain (especially if the transition matrix is sparse), and for computing the value function in optimal control problems. In many applications the computation can be significantly improved by appropriately ordering the variables within each sweep. A simple heuristic is presented here for computing an ordering that quickens convergence. In parallel processing, several variables must be computed simultaneously, which appears to work against Gauss-Seidel. Simple asynchronous parallel Gauss-Seidel methods are presented here. Experiments indicate that the methods retain the benefit of a good ordering, while further speeding up convergence by a factor of P if P processors participate.

In this paper, we focus on the optimal stopping problem. A probabilistic interpretation of the Gauss-Seidel (and the Jacobi) method for computing the value function is given, which motivates our ordering heuristic. However, the ordering heuristic and parallel processing methods apply in a broader context, in particular, to the important problem of computing the invariant measure of a Markov chain.

Type
Articles
Information
Probability in the Engineering and Informational Sciences , Volume 4 , Issue 4 , October 1990 , pp. 493 - 521
Copyright
Copyright © Cambridge University Press 1990

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Aho, A., Hopcroft, J., & Ullman, J. (1974). The design and analysis of computer algorithms. New York: Addison Wesley.Google Scholar
Baudet, G.M. (1978). Asynchronous iterative methods for multiprocessors. Journal of the ACM 25, 2: 226–244.CrossRefGoogle Scholar
Bertsekas, D. (1982). Distributed dynamic programming. IEEE Transactions on Automatic Control AC-27, 3: 610–616.CrossRefGoogle Scholar
Chazan, D. & Miranker, W. (1969). Chaotic relaxation. Linear Algebra and Its Applications 2: 199–222.CrossRefGoogle Scholar
Dynkin, E.B. & Yushkevich, A.A. (1969). Markov processes, theorems and problems. New York: Plenum Press.CrossRefGoogle Scholar
Goodman, J. & Madras, N. (1987). Random walk interpretations of classical iteration methods. Preprint. New York: Mathematics Department, New York University.Google Scholar
Gottlieb, A., Lubachevsky, B.D., & Rudolph, L. (1983). Basic techniques for the efficient coordination of very large numbers of cooperating sequential processors. ACM Transactions on Programming Languages and Systems 5, 2: 164–189.CrossRefGoogle Scholar
Gottlieb, A., Grishman, R., Kruskal, C.P., McAuliffe, K.P., Rudolph, L., & Snir, M. (1983). The NYU ultracomputer-designing a MIMD shared memory parallel machine. IEEE Transactions on Computers C-32, 2.CrossRefGoogle Scholar
Lubachevsky, B.D. (1984). An approach to automating the verification of compact parallel coordination programs I. Acta Informatica, 21: 125–169.CrossRefGoogle Scholar
Lubachevsky, B.D. & Mitra, D. (1987). A chaotic asynchronous algorithm for computing the fixed point of a nonnegative matrix of unit spectral radius. Journal of the ACM 33, 1: 130–150.CrossRefGoogle Scholar
Mitra, D. & Tsoucas, P. (1988). Relaxations for the numerical solutions of some stochastic problems. Communications in Statistics: Stochastic Models 4(3): 387–419.Google Scholar
Rudolph, L. (1981). Software structures for ultraparallel computing. Ph.D. Thesis, Courant Institute, New York University.Google Scholar
Seneta, E. (1981). Non-negative matrices and Markov chains, 2nd ed.New York: Springer- Verlag.CrossRefGoogle Scholar
Tijms, H.C. (1986). Stochastic modelling and analysis, a computational approach. New York: Wiley.Google Scholar
Varga, R. (1962). Matrix iterative analysis. Englewood Cliffs, N.J.: Prentice Hall.Google Scholar
van der Wal, J. & Schweitzer, P.J. (1987). Iterative bounds on the equilibrium distribution of a finite Markov chain. Probability in the Engineering and Information Sciences 1: 117–131.Google Scholar
van Nunen, J. & Wessels, J. (1981). Solving linear systems by methods based on a probabilistic interpretation. Computing 26: 209–225.CrossRefGoogle Scholar