Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  Willie Wong Jul 5 '11 at 18:48
add comment

1 Answer 1

up vote 9 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.