Department of 
Computer Science

Search our Site


  Sequential Monte Carlo Techniques for Solving Large Linear and Non-Linear Problems

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

Horizontal Line
Department of Computer Science
Campus Box 3175, Sitterson Hall
College of Arts & Sciences
The University of North Carolina at Chapel Hill
Chapel Hill, NC 27599-3175 USA
Phone: (919) 962-1700
Fax: (919) 962-1799

Content Manager:
Server Manager:
Last Content Review: 12 November 2001