Estimates of the computational complexity of iterative Monte Carlo algorithm based on Green's function approach1Supported by the Ministry of Education, Science and Technology of Bulgaria under grants no. MM 449/94 and I 501/95 as well as by EC under INCO-Copernicus project no. 960237 – STABLE.1

In this work an iterative Monte Carlo algorithm for solving elliptic boundary value problems is studied. The algorithm uses the local integral presentation by Green's function. The integral transformation kernel is obtained applying the adjoint operator on Levy's function. Such a kernel can be used as a transition density function of a Markov process for estimating the solution. The studied approach leads to a random process, which is called a ball process. The corresponding Monte Carlo algorithm is presented. This algorithm is similar to the well-known grid-free spherical process used for solving simple elliptic problems, however instead of moving to a random point on the sphere, a move is made to a point into a maximal ball, which is located “not far from the boundary of the ball”. The selection Monte Carlo algorithm for solving the above mentioned problem is described. An estimation for the efficiency of the selection Monte Carlo algorithm is obtained. The estimate of the averaged number of moves for reaching the ϵ-strip of the boundary of the domain for the studied random process is obtained. It is proved that the algorithm efficiency depends on the radius of the maximal ball, lying inside the domain Ω in which the problem is defined and on the parameters of the operator under consideration. Some numerical examples are performed. The results show that the obtained theoretical estimates can be used for a wide class of elliptic boundary value problems.