Search our Site
 
Sequential Monte Carlo Techniques for Solving
Large Linear and NonLinear Problems
The Problem
Largescale problems in science, engineering, economics, logistics,
etc., very often take the form of linear or nonlinear 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 problemsolving 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 socalled
"pseudorandom" or "quasirandom" 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 multicomputers to
further accelerate these computations. In addition, we explore the
development of better and more versatile techniques to solve a wide
range of largescale problems, and we also investigate the random
generators (especially quasirandom 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
