Effiziente Implementierung von Gravitationsfeldern

8

Ich habe eine ähnliche Frage zu physics.stackexchange gestellt , da ich diese Website nicht kenne.

Ich suche grundsätzlich nach einem effizienten Weg, um Gravitationsfelder zu implementieren.

Ich habe einen riesigen 2D-Raum mit Tausenden von Objekten. Ich muss dann simulieren, wie diese Objekte durch die Schwerkraft des anderen beeinflusst werden.

Ich dachte, es wäre möglich, die Objekte in Sammlungen zu sortieren und jedes Objekt außerhalb dieser Sammlung mit dieser Sammlung zu vergleichen, und nicht jedes einzelne Objekt innerhalb dieser Sammlung. Ich stellte bald fest, dass dies einfach nicht möglich war. Das Gravitationsfeld mehrerer Objekte kann nicht als ein einheitliches Feld dargestellt werden, das mit nur einer Masse und Entfernung berechnet wird.

Jedes Objekt innerhalb der Simulation kann als Kugel betrachtet werden. Ich kann mit Annäherungen gut umgehen, solange es einigermaßen realistisch aussieht.

Jeroen
quelle

Antworten:

5

O(N2)O(N)

Ein weiterer Algorithmus für die N-Körpersimulation ist Barnes-Hut, der einfacher zu implementieren ist und wahrscheinlich auch Bibliotheksimplementierungen zur Verfügung hat. Es wird als weniger effizient (im asymptotischen Sinne) als FMM angesehen.

Wenn Ihre Domain periodisch ist, könnten Sie vielleicht so etwas wie eine Partikelwald-Ewald-Summierung durchführen? (Ich weiß weniger über diesen Ansatz.)

Geoff Oxberry
quelle
Ich habe bereits etwas darüber gelesen und es scheint Elemente zu gruppieren. Da alle meine Elemente ziemlich nahe beieinander liegen und die behandelten Massen eher klein sind, wird dies immer noch zutreffend sein?
Jeroen
1
Ich habe keine Erfahrung damit; Ich habe nur einige Vorträge über die Methode besucht. FMM soll robust sein, und die allgemeine Idee ist, dass die Reihenfolge der Summierung abgeschnitten wird, sobald sie eine ausreichende Genauigkeit erreicht hat (Fehlergrenzen können für die Summierung abgeleitet werden, daher werden diese für den Genauigkeitstest verwendet). Außerdem soll die Genauigkeit nicht von der Quellenverteilung abhängig sein. FMM soll effizienter sein als Partikelnetz Ewald, wenn die Quellen nahe beieinander liegen.
Geoff Oxberry
4
Während jeder einzelnen Masse ein Monopolfeld zugeordnet ist, hat eine Massensumme kein reines Monopolfeld. Der Punkt von FMM ist, dass diese Summe von Feldern effizient durch ein Multipolfeld (relativ niedriger Ordnung) dargestellt werden kann, da die höheren Moden des Feldes mit der Entfernung schnell abfallen.
Wolfgang Bangerth
Wenn ich das Feld nur zum Berechnen der Beschleunigung verwenden würde, würde eine solche Einschränkung neue Möglichkeiten eröffnen?
Jeroen