Quicker convergence for iterative numerical solutions to stochastic problems: Probabilistic interpretations, ordering heuristics, and parallel processing

Albert G. Greenberg, Robert J. Vanderbei

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)493-521
Number of pages29
JournalProbability in the Engineering and Informational Sciences
Volume4
Issue number4
DOIs
StatePublished - Jan 1 1990
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering

Fingerprint Dive into the research topics of 'Quicker convergence for iterative numerical solutions to stochastic problems: Probabilistic interpretations, ordering heuristics, and parallel processing'. Together they form a unique fingerprint.

Cite this