تقرير
An algorithm for estimating volumes and other integrals in $n$ dimensions
| العنوان: | An algorithm for estimating volumes and other integrals in $n$ dimensions |
|---|---|
| المؤلفون: | I., Arun, Venkatapathi, Murugesan |
| سنة النشر: | 2020 |
| المجموعة: | Computer Science Mathematics Physics (Other) |
| مصطلحات موضوعية: | Mathematics - Numerical Analysis, Physics - Data Analysis, Statistics and Probability |
| الوصف: | The computational cost in evaluation of the volume of a body using numerical integration grows exponentially with dimension of the space $n$. The most generally applicable algorithms for estimating $n$-volumes and integrals are based on Markov Chain Monte Carlo (MCMC) methods, and they are suited for convex domains. We analyze a less known alternate method used for estimating $n$-dimensional volumes, that is agnostic to the convexity and roughness of the body. It results due to the possible decomposition of an arbitrary $n$-volume into an integral of statistically weighted volumes of $n$-spheres. We establish its dimensional scaling, and extend it for evaluation of arbitrary integrals over non-convex domains. Our results also show that this method is significantly more efficient than the MCMC approach even when restricted to convex domains, for $n$ $\sim <$ 100. An importance sampling may extend this advantage to larger dimensions. |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2007.06808 |
| رقم الأكسشن: | edsarx.2007.06808 |
| قاعدة البيانات: | arXiv |
كن أول من يترك تعليقا!