15

I know that most methods of finding approximate solutions to PDEs scale poorly with the number of dimensions, and that Monte Carlo is used for situations that call for ~100 dimensions.

What are good methods for efficiently numerically solving PDEs in ~4-10 dimensions? 10-100?

Are there any methods besides Monte Carlo that scale well with the number of dimensions?

Dan
  • 3,355
  • 3
  • 21
  • 47
  • 1
    It might help to provide a bit more information about the kind of problem you're solving. Most PDE's handled in computational science tend to be at most four-dimensional (time plus three spatial dimensions). Are the variables spatial or time variables, or are there other dependencies you're including? – aeismail Dec 16 '11 at 20:27
  • 1
    Spatial variables. In quantum mechanics if you don't want to make the approximations that you use in density functional theory or Hartree-Fock, the wavefunction is $3n$ dimensional, where $n$ is the number of electrons. So even small atoms and molecules require a large number of dimensions to handle correctly. – Dan Dec 16 '11 at 20:32
  • 1
    It depends a lot on what information you want to knowabout the solution. One hardly wants to know every detail about an $n$-electron wave function. So one has to taylor the computational technique to the informastion actually desired. – Arnold Neumaier Apr 16 '12 at 16:55
  • 1
    Please cite a reference for the Monte Carlo solution of an electronic Schroedinger equation in 100 dimensions. – Arnold Neumaier Apr 16 '12 at 17:00
  • I don't have a reference. I've only heard of simulations in that many dimensions being used for QCD. I'm only looking to do Schroedinger simulation in 4-5 dimensions, but I was wondering if anything besides monte carlo scaled well with the number of dimensions, and 100 seemed like a nice, large round number to get the asymptotic scaling. – Dan Apr 16 '12 at 17:10

3 Answers3

14

A more structured way of providing a basis or quadrature (which may replace MC in many cases) in multiple dimensions is that of sparse grids, which combines some family of one dimensional rules of varying order in such a way as to have merely exponential growth in dimension, $2^d$, rather than having it be that dimension is an exponent of the resolution $N^d$.

This is done through what is known as a Smolyak quadrature, which combines a series of one-dimensional rules $Q^1_l$ as

$ Q^d_n = \displaystyle\sum^{n}_{l}(Q^{1}_i - Q^{1}_{i-1})\otimes Q^{d-1}_{m-i+1} $

This is equivalent to the tensor product quadrature space with the high mixed orders removed from the space. If this is done in a severe enough fashion, the complexity may be improved greatly. However, for one to be able to do this and maintain good approximation, the regularity of the solution has to have sufficiently vanishing mixed derivatives.

Sparse grids have been beaten to death by the Griebel group for things like the Schrödinger equation in configuration space and other high dimensional things with pretty good results. In application, the basis functions used may be pretty general, as long as you can nest them. For instance, plane-waves or hierarchical bases are common.

It's also pretty simple to code up yourself. From my experience, actually getting it to work for these problems, however, is very hard. A good tutorial exists.

For problems whose solutions live in specialized Sobolev spaces featuring derivatives that rapidly die, the sparse grid approach may potentially yield even greater results.

See also the Acta Numerica review paper, Sparse tensor discretizations of high-dimensional parametric and stochastic PDEs.

Peter Brune
  • 1,675
  • 12
  • 20
  • Are there well known examples where sparse grids aren't applicable? – MRocklin Dec 20 '11 at 16:40
  • 1
    You really need the regularity to hold. Also, if you have nasty high-dimensional cusps (like in QM), you have to be careful. I heard some stories about the Sparse Grid clique starting to concede (with proofs even) that it isn't that much better than Monte-Carlo, but can't find a good reference. – Peter Brune Dec 23 '11 at 05:01
  • Well, The paper on sparse grid for schroedinger you referred to only treats 2 electrons. How many electrons are actually tractable by the method? – Arnold Neumaier Apr 16 '12 at 16:57
6

As a general rule, it's easy to understand why regular grids can't go much beyond 3 or 4-dimensional problems: in d dimensions, if you want to have a minimum of N points per coordinate direction, you'll get N^d points overall. Even for relatively nice functions in 1d, you need at least N=10 grid points to resolve them at all, so the overall number of points will be 10^d -- i.e. even on the biggest computers you're unlikely to go beyond d=9, and will probably not go much beyond ever. Sparse grids can help in some circumstances if the solution function has certain properties, but in general, you'll have to live with the consequences of the curse of dimensionality and go with MCMC methods.

Wolfgang Bangerth
  • 55,373
  • 59
  • 119
2

Monte Carlo has a very attractive property: it has the same convergence rate independent of the dimension of the problem. So, even for problems of dimension $d=4,...,100$, they will converge at the same rate as problems with dimension $d=100,101,...\infty$. So, even as your dimension increases from 4 to 100, monte carlo will probably be faster anyways.

Paul
  • 12,045
  • 7
  • 56
  • 129
  • 2
    That's not a very useful statement, though. Of course, the convergence rate is $O(\sqrt{N})$ independent of the dimension. But the constantin front of it depends on the dimension, and in very unpleasant ways. You can easily approximate an integral in 3d using 100 sample points for a reasonably smooth functions. You can't do the same with $10^7$ points if you are in 100 dimensions! – Wolfgang Bangerth Apr 17 '12 at 13:09
  • Well, this depends on the smoothness. If all you have is some finite Hölder bound $C^{k,\alpha}$, then functions with rich mixed derivatives are allowed and there is no overcoming the curse of dimensionality. We can only do better if mixed derivatives decay sufficiently rapidly, or if there is some other exploitable regularity. – Jed Brown Apr 20 '12 at 15:50