The Problem
Large-scale problems in science, engineering, economics, logistics, etc., very often take the form of linear or non-linear algebraic, differential, and/or integral equations. When the number of variables and parameters grows beyond a few hundred, the computational difficulties become major obstacles and the usual methods begin to fail. It is at this point that Monte Carlo (MC) methods emerge as important problem-solving tools. Such methods are not limited to problems of a statistical nature, nor do they amount to straightforward simulation of scientific models. Their range of application is very broad, and there is a variety of efficient techniques, some of considerable subtlety.

The Challenge
The Monte Carlo method consists of creating a statistical situation (probability space) in which a required answer is the expected value of some random variable; the answer is then estimated by sufficient sampling of this random variable to ensure adequate accuracy. This is typically done using a programmed computer model with so-called "pseudo-random" or "quasi-random" generators. In the case of linear algebraic problems, the solution is obtained by computing an estimate obtained from a "random walk" in a suitable space.

The Approach
This project centers on sequential (SMC) techniques, which adaptively modify the sampling scheme as it yields information about the problem. There are various ways to do this, and the increase of efficiency from plain MC is quite spectacular. (For instance, a test problem that took some 2,000,000 random steps to compute an adequate answer by plain MC took only about 60 random steps by SMC.) We seek to obtain further information about SMC techniques: when they work best, which schemes are best, and the parameters of the techniques (quantitative rates of convergence and computing requirements). We also seek to use parallel and multi-computers to further accelerate these computations. In addition, we explore the development of better and more versatile techniques to solve a wide range of large-scale problems, and we also investigate the random generators (especially quasi-random generators of sequences of numbers and sets of numbers, and parallelizable generators--"random trees") that are used, with a view to improving and to analyzing their efficiency.

Project Leader
John H. Halton, professor

For More Information
http://www.cs.unc.edu/~halton