10
$\begingroup$

I've heard that in greater than three dimensions, it's more efficient to solve a second-order parabolic PDE using a Monte-Carlo method based on the Feynman-Kac formula that it is to use finite difference/finite element methods.

I want to refer to this fact in an article I'm writing, but I don't know of any books or papers that I could use as a reference. Does anyone know of such a text? I'm specifically looking for something that mentions $d=3$ as the break-even point.

Many thanks.

$\endgroup$
1
  • 1
    $\begingroup$ When you say "efficient", do you mean as a numerical computation? Maybe in that case you want to add the numerical-methods tag. Good question, BTW. $\endgroup$
    – Willie Wong
    Jul 5, 2011 at 18:48

1 Answer 1

Reset to default
12
$\begingroup$

I'm not sure if such a reference exists; this claim is certainly part of well known folklore, but I doubt that it is possible to "prove" this in any interesting amount of generality.

The phenomenon is commonly called the "curse of higher dimensions", which means that the error of deterministic grid methods (I leave the precise definition of "error" unspecified) is asympotically $O(N^d)$ (N = number of grind points in one coordinate, d = dimension). This is not true for "Monte-Carlo methods" that use averages of the simulation of stochastic differential equations instead. But I'm mostly sure that you'll have to specify a concrete problem in order to show that there is a break-even point in 3D, and it will also depend on your definition of error and the involved numerical methods.

It is possible to show that for example "sparse grid methods" can avoid the curse of higher dimensions, at least to some extend in theory, but also in numerical experiments, so that grid methods can outperform Monte-Carlo methods in specific situations in higher dimensions. This relies upon assumptions about the "smootheness" of the function space that is the solution space of the equations at hand.

You could try this review paper for an explanation of this kind of counterexample:

  • H.-J. Bungartz and M. Griebel: Sparse grids. Acta Numerica, 13:1-123, 2004.

and this one specifically for parabolic PDE:

I think some of the students of Professor Griebel have studied concrete problems and compared grid methods to Monte-Carlo methods with the result that grid methods sometimes outperform Monte-Carlo methods in dimensions greater than 3, but have not found a suitable reference.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .