MCQMC Algorithms for Solving some Classes of Equations

The Monte-Carlo method is known to be used for solving problems of very different nature. Equation solving constitutes one of the very important classes of problems. A stochastic process which can be effectively simulated by computer is usually associated with the equation under consideration. Then some functional of process trajectories is constructed in order to obtain an unbiased estimation of the required value which can be either solution of the equation or some functional of the solution. And finally, one of the laws of large numbers or limit theorems is used. Stochastic methods usually permit to apply a simple software implementation, they are easily adapted for parallel computer systems and can also effectively use a priori information about the exact problem’s solution (i.e. methods of variance reduction). The well-known disadvantage of the stochastic methods is a comparatively low speed of the error decrease as the number of independent process realizations grows. There are a lot of works aimed at overcoming this disadvantage. The works concerning application of the deterministic methods in computational schemes (Quasi Monte-Carlo Method — QMC) are among them. It is important to notice that the QMC methods preserve the parallel structure of classical stochastic algorithms. It seems that the parallelism of algorithms is one of the most important problems in the modern theory of the Monte-Carlo methods. Another important problem is in comparison of computational complexities of stochastic algorithms and similar deterministic algorithms. Investigations in these fields of MC theory might be important to find out the structure of modern computational systems. This article includes a brief revue of the author’s and his colleague’s investigations in these and related fields. Generalizations of some results and their analysis from the point of view of parallelism are presented for the first time.