8
$\begingroup$

I asked a similar question on physics.stackexchange, being ignorant about this website.

I am basically looking for an efficient way to implement gravitational fields.

I have a huge 2D space, with thousands of objects in it. I then need to simulate how these objects are effected by each other's gravity.

I thought it'd be possible to sort the objects into collections, and check every object outside that collection against that collection, and not every individual object inside of it. I soon came to the realization that this simply wasn't possible. The gravitational field of multiple objects cannot represented as one uniform field, calculated with only one mass and distance.

Every object inside the simulation can be considered a sphere. I am fine with approximations, as long as it looks reasonably realistic.

| cite | improve this question | | | | |
$\endgroup$
5
$\begingroup$

You could try using a library that implements the Fast Multipole Method (FMM), which should drastically reduce the amount of memory you need and will decrease the complexity of matrix-vector products from $\mathcal{O}(N^{2})$ to $\mathcal{O}(N)$. It is difficult to implement, but there should be some libraries out there.

Another algorithm for N-body simulation is Barnes-Hut, which is easier to implement, and probably also has library implementations available. It is considered less efficient (in the asymptotic sense) than FMM.

If your domain is periodic, maybe you could do something like particle mesh Ewald summation? (I know less about this approach.)

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ I've done some reading about it already, and it appears to group elements. As all my elements will be fairly close to each other, and the masses being dealt with are rather small, will this still be accurate? $\endgroup$ – Jeroen Mar 24 '14 at 18:56
  • 1
    $\begingroup$ I don't have any experience using it; I've only attended a few lectures on the method. FMM is supposed to be robust, and the general idea is that the order of the summation is truncated once it has attained sufficient accuracy (error bounds can be derived for the summation, so these are used for the accuracy test). Also, the accuracy is not supposed to be source-distribution-dependent. FMM is supposed to be more efficient than particle mesh Ewald when sources are close together. $\endgroup$ – Geoff Oxberry Mar 24 '14 at 19:04
  • 4
    $\begingroup$ While every individual mass has a monopole field associated with it, a sum of masses does not have a pure monopole field. The point of FMM is that this sum of fields can be efficiently represented by a (relatively low order) multipole field since the higher modes of the field decay quickly with distance. $\endgroup$ – Wolfgang Bangerth Mar 24 '14 at 19:37
  • $\begingroup$ If I were to only use the field for the purpose of calculating acceleration, would such a limitation open up a new scope of possible ways to do it? $\endgroup$ – Jeroen Mar 24 '14 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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