From: "Alberto Cherubini" Subject: integration multi-D: MOntecarlo vs grid Date: Tue, 11 May 1999 21:20:52 +0100 Newsgroups: sci.math.num-analysis Hallo, I need help with a doubt. Is it that uniform grid integration in high dimension slower to converge than Montecarlo? If that is the case, is there an intuitive explanation? The problem is to compute the integral of an unknown function in a d-dimensional domain, say the unit cube for simplicity [0,1]^d Let's also assume the function is reasonably well behaved and smooth, no singularity etc. Let's use a simple method, say trapezoid or similar, on a uniform grid with stepsize h ~ 1/n where n is the number of gridpoints per dimension, N = n^d is the total number of grid points and so also the number of function evaluations. h~N^(-1/d) The error per point is eps ~ f'' h^(2+d) ~ N^(-(1+2/d)) (i'll drop f'' ) The total error is E ~ N eps ~ O( N^(-2/d ) For d=1, we get the usual O(N^-2) but for d >4 , one gets less than N^(-1/2), i.e. worse than Montecarlo integration ! My intuition does not get it... Surely a uniform grid should be at least as good as a random one? If nothing else, it can be construed as just one of the possible random samples? Thanks, Alberto Cherubini ============================================================================== From: ptitjean@ccr.jussieu.fr (Michel PETITJEAN) Subject: Re: integration multi-D: MOntecarlo vs grid Date: 12 May 1999 10:43:46 +0200 Newsgroups: sci.math.num-analysis Subject: Re: integration multi-D: MOntecarlo vs grid In article <7ha3lc$93o$1@news5.svr.pol.co.uk> "Alberto Cherubini" wrote: >Hallo, > I need help with a doubt. >Is it that uniform grid integration in high dimension >slower to converge than Montecarlo? > ... Monte-Carlo is good in high dimension because the precision is bettered by 10 for a cpu cost multiplied by 100 and because it does not require derivatives, but of course it assumes that the function is known at random locations. It should be compared to grid methods working on simplices (conical product, Grundmann & Moller, ...) rather than rectangular grids. Michel Petitjean, Email: petitjean@itodys.jussieu.fr ITODYS (CNRS, ESA 7086) ptitjean@ccr.jussieu.fr ============================================================================== From: ptitjean@ccr.jussieu.fr (Michel PETITJEAN) Subject: Re: integration multi-D: MOntecarlo vs grid Date: 14 May 1999 10:00:58 +0200 Newsgroups: sci.math.num-analysis References: <7hbf02$2pga@moka.ccr.jussieu.fr> In article <3739C6EC.6F3078CF@cherubini.freeserve.co.uk> Alberto Cherubini wrote: >of course the finction can be computed at any given location, >by "unknown" I meant not known a priori. >I still don't understand why the montecarlo should do better than a regular >grid: >(I know that it goes as sqrt(cpu): in the original post I expressed it as >N^-1/2) Here is an example: consider a domain in R3 at the union of intersecting ellipses, polyhedrons, cylinders, and many objects for which it is easy to know whether a point is inside or outside. Now you ask for the volume of the union. The function is the indicator of the domain, i.e. 1 inside and 0 outside. Monte-Carlo with N nodes is N**(-1/2). The rectangular grid is N**(-1/3): precision is bettered by 10 when the number of nodes is 10*10*10 times larger. Michel Petitjean, Email: petitjean@itodys.jussieu.fr ITODYS (CNRS, ESA 7086) ptitjean@ccr.jussieu.fr ============================================================================== From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) Subject: Re: multidimensional integrals Date: 3 Dec 1999 12:54:38 GMT Newsgroups: sci.math.num-analysis Keywords: best methods for computation of integrals over R^n In article <8264st$4jn$1@acebo.sdi.uam.es>, "carlos" writes: |> Hi, |> |> I need to calculate a multidimensional integral of type: |> |> \int_{-\infty}^{\infty}dx1···\int-{-\infty}^{\infty}dxn L(x1,..xn) |> exp(-x1^2-x2^2-...-xn^2) |> |> where L(x1,..xn) is a likelihood function. That is, a multidimensional |> integral of a likelihood function with an independent normal kernel. |> In a one dimensional problem I can use the Gauss-Hermite quadrature formula |> but I want to know if there is a more efficient algorithm for |> multidimensional problems. depends on n . for n=2,3 special rules exist., but in general Monte Carlo integration is best. What I found in my notices: From: Joseph Traub Date: Sun, 29 Mar 98 14:17:17 EST Subject: Numerical Tests on High Dimensional Integrals NUMERICAL TESTS ON A HIGH DIMENSIONAL INTEGRAL FROM PHYSICS In a series of papers our research group has shown that quasi-Monte Carlo methods using low discrepancy sequences are superior to Monte Carlo methods for the high dimensional integrals arising in mathematical finance. A possible explanation may be that these problems are non-isotropic; see I. A. Sloan and H. Wozniakowski, "When are Quasi-Monte Carlo Algorithms Efficient for High Dimensional Integrals?", Journal of Complexity, March, 1998, 1-33. In a recent paper ("Faster Evaluation of Multidimensional Integrals" by A. Papageorgiou and J. F. Traub, Computers in Physics, 11(6), 1997, 574-578), we tested a high-dimensional model problem proposed by the physicist B.D. Keister. This problem is isotropic. We found that quasi-Monte Carlo converged as 1/n while Monte Carlo converged as 1/sqrt(n). Quasi-Monte Carlo was also greatly superior to several quadrature rules tested by Keister. You may obtain our recent paper as well as papers reporting test :results from mathematical finance at www.cs.columbia.edu/~traub Numerous test results using our FINDER software system may also be found at this site. from another source comes this: The first choice, Monte Carlo routines from Numerical Recipes, which are based on the VEGAS codes, produced typical results, but which were not accurate enough, around the 1% level. Our experience with ADHRE, TOMS 764, has been very disappointing as it cannot seem to handle surfaces which are not perpendicular to one of the coordinate directions - it fails to converge and ultimately the estimate is worthless even in the simplest example at the lowest dimension. The next choice could be the Number theoretic algorithms, based on Korobov points, as found in Comp. Phys. Comm. 14, 299 (1978) Comp. Phys. Comm. 31, 1 (1984) although we haven't tried these yet. hope that helps peter ============================================================================== From: spellucci@mathematik.tu-darmstadt.de (Peter Spellucci) Subject: Re: N dim integration with fixed rule Date: 8 Mar 1999 13:43:13 GMT Newsgroups: sci.math.num-analysis In article <7bpndp$gau$1@winter.news.rcn.net>, "Antoine Conze" writes: |> Does anyone know of a good N dimension non-adaptive quadrature |> routine with fixed abscissae and weights ? what about N? For N>3 , say, Monte carlo integration is the method of choice. For N=2,3 see Stoud; approximate calculation of mutliple integrals, prentice hall publ. In principle these rules also apply to arbitrary N, but the effort is so tremendous that the O(1/sqrt(n)) precision, n=number of function values, of Monte Carlo methods outperforms systematic rules. hope this helps peter