4
$\begingroup$

I am looking for stochastic methods for solving a very high-dimensional PDE (with one time dimension and very large number of spatial dimensions), which would reduce it to a lower-dimensional problem, probably at the cost of carrying out a Monte Carlo simulation. Any pointers?

$\endgroup$

2 Answers 2

5
+50
$\begingroup$

It seems to me this question "has not received enough attention" because of the conflation of two issues: dimensional reduction of a high-dimensional PDE and stochastic (Monte Carlo) integration of the PDE.

The socalled "curse of dimensionality" refers to the fact that the computational time required for a non-stochastic solution of a PDE grows exponentially with the number of dimensions (each dimension needs to be discretized, say with $N$ points, so the total number of points in $d$ dimensions is $N^d$). Dimensional reduction is then imperative, and one method to achieve that is principal component analysis.

The computational time for a solution of a PDE by Monte Carlo integration grows only linearly with dimension, so dimensional reduction is not needed. The accuracy of this approach is low, and this is why one tries to avoid resorting to a Monte Carlo method.

The two approaches to the solution of a high-dimensional PDE, dimensional reduction by principal component analysis and Monte Carlo integration, are compared in these lecture notes.


Upon some more search, I found one dimensional-reduction scheme with a stochastic component. It goes by the acronym RS-HDMR = Random-Sampling-High-Dimensional-Modeling-Representation and is described here. (The HDMR Wikipedia page could use some expansion...)

$\endgroup$
2
  • 1
    $\begingroup$ I am aware of the link between Monte Carlo and PDEs in the Black-Scholes theory. I was looking for general stochastic, dimensionality-reducing approaches one could apply to an arbitrary linear PDE. $\endgroup$
    – Katastrofa
    Nov 17, 2014 at 12:09
  • 2
    $\begingroup$ I added one such approach, RS-HDMR, that seems to have the generality you are looking for. $\endgroup$ Nov 17, 2014 at 12:22
2
$\begingroup$

It seems that you are interested in a "tractability problem", that is, a problem which asks whether the solution of a very high-dimensional problem can be efficiently approximated. As far as I know some research has been done in this direction, but much more for numerical integration than for PDEs. It may make sense to look for QMC methods (Quasi-Monte Carlo methods) for solving such problems (that means, using cleverly chosen deterministic points instead of random points). Look for example at the following: https://math.unibas.ch/uploads/x4epublication/53518/Preprint_1328.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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