Abstract
Monte Carlo Method (MCM) is the only viable method for many high-dimensional problems since its convergence is independent of the dimension. In this paper we develop an adaptive Monte Carlo method based on the ideas and results of the importance separation, a method that combines the idea of separation of the domain into uniformly small subdomains with the Kahn approach of importance sampling. We analyze the error and compare the results with crude Monte Carlo and importance sampling which is the most widely used variance reduction Monte Carlo method. We also propose efficient parallelizations of the importance separation method and the studied adaptive Monte Carlo method. Numerical tests implemented on PowerPC cluster using MPI are provided.
Supported by Center of Excellence BIS-21 Grant ICA1-2000-70016 and by the Ministry of Education and Science of Bulgaria under Grants I-1201/02 and MM-902/99
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bahvalov, N. S.: On the optimal estimations of convergence of the quadrature processes and integration methods. Numerical Methods for Solving Differential and Integral Equations, Nauka, Moscow (1964) 5–63 (in Russian).
Berntsen, J., Espelid, T. O., and Genz, A.: An adaptive algorithm for the approximate calculation of multiple integrals. ACM Trans. Math. Softw., 17 (1991) 437–451.
Bull, J. M. and Freeman, T. L.: Parallel globally adaptive quadrature on the KSR-1. Advances in Comp. Mathematics, 2 (1994) 357–373.
Bull, J. M. and Freeman, T. L.: Parallel algorithms for multi-dimensional integration. Parallel and Distributed Computing Practices, 1(1) (1998) 89–102.
Caflisch, R. E.: Monte Carlo and quasi-Monte Carlo methods. Acta Numerica, 7 (1998) 1–49.
van Dooren, P. and de Ridder, L.: An adaptive algorithm for numerical integration over an N-dimensional cube. Journal of Computational and Applied Mathematics, 2 (1976) 207–217.
Freeman, T. L. and Bull, J. M.: A comparison of parallel adaptive algorithms for multi-dimensional integration. Proceedings of 8th SIAM Conference on Parallel Processing for Scientificc Computing (1997)
Hesterberg, T.: Weighted average importance sampling and defensive mixture distributions. Technometrics, 37(2) (1995) 185–194.
Karaivanova, A.: Adaptive Monte Carlo methods for numerical integration. Mathematica Balkanica, 11 (1997) 391–406.
Karaivanova, A. and Dimov, I.: Error analysis of an adaptive Monte Carlo method for numerical integration. Mathematics and Computers in Simulation, 47 (1998) 201–213.
Owen, A. and Zhou, Y.: Safe and effiective importance sampling. Technical report, Stanford University, Statistics Department (1999)
Sobol', I. M.: Monte Carlo Numerical Methods. Nauka, Moscow (1973) (in Russian).
Veach, E. and Guibas, L. J.: Optimally combining sampling techniques for Monte Carlo rendering. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH’ 95 (1995) 419–428.
Veach, E.: Robust Monte Carlo Methods for Light Transport Simulation. Ph.D. dissertation, Stanford Universty (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dimov, I., Karaivanova, A., Georgieva, R., Ivanovska, S. (2003). Parallel Importance Separation and Adaptive Monte Carlo Algorithms for Multiple Integrals. In: Dimov, I., Lirkov, I., Margenov, S., Zlatev, Z. (eds) Numerical Methods and Applications. NMA 2002. Lecture Notes in Computer Science, vol 2542. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-36487-0_10
Download citation
DOI: https://doi.org/10.1007/3-540-36487-0_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-00608-4
Online ISBN: 978-3-540-36487-0
eBook Packages: Springer Book Archive