# Solving Poisson equation while suffering from the curse of dimensionality

I have a heat transfer equation in a cube in $R^{100}$: $[0,1]\times[0,1]\times[0,1]\dots$: $$\nabla^2 \varphi = f,$$ with boundary conditions set in a form that in the number of points $p_i$, temperature field should least deviate from observed values $o_i$, or in other words that solution of heat equation should minimise: $$\sum_{k=0}^{m}|\varphi(p_i) - o_i|^2.$$

This would be pretty straightforward problem in 2-3 dimensional case (assuming problem is well-posed), I've solved it with FEM successfully, but for high dimensional case I cannot even build the grid, let alone do any calculations. (I don't store $f$, I can easily calculate it in any point).

It seems, I need to employ some grid-less method. I've skimmed google briefly and found two possible venues: to use radial basis functions or use particle methods. Are they applicable in my case? Do my problem feasible at all?

I've never worked with high dimensional problems before, so I would like to hear all suggestions and references to the relevant and possibly relevant literature.

• Can you explain the background of this problem, maybe give some references? Are you looking at a stationary or time dependent problem? – Bananach Dec 7 '16 at 14:04
• I am not as pessimistic as Wolfgang. You may use sparse grids with one degree of freedom at the coarsest level to avoid 2^100. Or you may use stochastic representations of the PDE, whose cost is dimension independent – Bananach Dec 7 '16 at 14:16
• @Bananach I have system depending on many parameters. Each simulation of given system with different parameters gives me point in this $R^{100}$ space. The simulations are expensive and I have a key observation that space of possible solutions should itself be a solution of something like Poisson equation. So, I figured instead of running many simulations of my system I will do just a few and solve Poisson equation. The distribution itself is of no interest for me, but only moments: the mean value, variance, may be higher order moments. – Moonwalker Dec 8 '16 at 10:24
• I don't think this will be worth the effort. If you can compute point values of $\phi$, then I guess you should just apply Monte Carlo, especially since you are only interested in moments. If your point evaluations are expensive, it sounds like you should look into Multilevel Monte Carlo: Here, you use a lot of inexpensive and less accuracte evaluations of $\phi$, and only a few expensive ones, yet you get the same error estimates as if you used only expensive ones – Bananach Dec 8 '16 at 11:21
• Well, if you use Monte Carlo integration to compute your mean (and other moments), then you choose the evaluation locations at random according to the measure with respect to which you want to compute the mean – Bananach Dec 8 '16 at 12:10

The short answer is that you can't do this -- it's outside our computational power today. To explain why, think of just building the box itself, where you have one degree of freedom on each vertex. In 100 dimensions, there are $2^{100}\approx 10^{10}$ vertices. That's not far from the size of the biggest finite element computations, and you'll need on the order of $10^5-10^6$ processors to do that. At the same time, all you could do on this one cube is represent the solution as some kind of linear function in each direction -- that's not going to tell you anything about what is really going on; in fact, all it really does is interpolate the boundary values.
• This analysis is based on the assumption that realistically possible states of the boundary can obtain any combination of values on the vertices. However, the whole point of sparse grids is that in many high-dimensional applications, the dimensions are relatively independent. For example, if one assumes that the underlying function is linear, then only 100 degrees of freedom are required. If one assumes that there are additional quadratic interactions ($x_1^2,x_1x_2, \dots, x_{12}x_{15},\dots$), then only 100+100+100*99/2 degrees of freedom are required. – Bananach Dec 8 '16 at 11:11
• In short, your statement "all you could do on this one cube is represent the solution as some kind of linear function in each direction" is misleading. If you actually used $2^100$ dof for the boundary, then you could represent functions where each variable acts differently in interaction with any other variable. In practice, a lot of variables have globally monotonous effects. (E.g. when the function is linear, only 100dof are needed since the effect of each variable $x_i$ is independent from the others). – Bananach Dec 8 '16 at 11:15