MONTE CARLO ALGORITHMS FOR ELLIPTIC DIFFERENTIAL EQUATIONS. DATA PARALLEL FUNCTIONAL APPROACH∗

∗Partial supported by RWTH Aachen, Lehrstuhl fur Informatik II and by Ministry of Science and Education of Bulgaria under Grants #I 210 and #MM 448

Abstract

Monte Carlo algorithms for solving boundary value problems for elliptic differential equations are studied. In particular two Monte Carlo numerical algorithms are considered. The first one is so-called grid-walk (GW) algorithm, white the second one is grid-free (GF) algorithm. The first algorithm uses a discretisation of the problem on a mesh and solves the linear algebraic system, which approximates the original problem. The second algorithm uses an integral representation for the problem. For the studied algorithms a new data parallel approach is applied. It is shown that the numerical solution of partial differential equations, can be efficiently addressed in a functional language. These algorithms have been implemented in parallel on a MIMD-machine with distributed memory. Experimental results that they behave well and that due to small amount of communication a linear speedup is possible.

The key point of our approach is to propose a new Monte Carlo approach and. to offer “unique” arrays and some operations on them which allow to handle their elements in parallel, including operations which exchange the partitions of an array between the processors.

KEY WORDS:

• Monte Carlo algorithms
• elliptic differential equation
• boundary value problem
• data parallelism

C.R. CATEGORIES:

• C.1.2
• F.2.1
• G.3

Notes

∗Partial supported by RWTH Aachen, Lehrstuhl fur Informatik II and by Ministry of Science and Education of Bulgaria under Grants #I 210 and #MM 448