Complexity of Monte Carlo algorithms for a class of integral equations

Dimov, I. and Georgieva, R. (2007) Complexity of Monte Carlo algorithms for a class of integral equations. Lecture Notes in Computer Science, 4487. pp. 731-738. ISSN 0302-9743 978-3-540-72583-1

Abstract/Summary

In this work we study the computational complexity of a class of grid Monte Carlo algorithms for integral equations. The idea of the algorithms consists in an approximation of the integral equation by a system of algebraic equations. Then the Markov chain iterative Monte Carlo is used to solve the system. The assumption here is that the corresponding Neumann series for the iterative matrix does not necessarily converge or converges slowly. We use a special technique to accelerate the convergence. An estimate of the computational complexity of Monte Carlo algorithm using the considered approach is obtained. The estimate of the complexity is compared with the corresponding quantity for the complexity of the grid-free Monte Carlo algorithm. The conditions under which the class of grid Monte Carlo algorithms is more efficient are given.