تقرير
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 |
الوصف غير متاح. |