N-Körper- und Partikel-Mesh-Methoden

Die Berechnung der gegenseitigen Gravitations- oder elektrostatischen Kräfte zwischen vielen Partikeln kostet naiv das Quadrat ihrer Anzahl. Schnelle N-Körper- und Partikel-Mesh-Methoden reduzieren dies auf nahezu lineare Kosten, was Simulationen von Galaxien und Plasmen mit Millionen von Partikeln ermöglicht.

Definition

N-Körper- und Partikel-Mesh-Methoden sind Algorithmen, die die weitreichenden Kräfte zwischen vielen wechselwirkenden Partikeln in weniger als quadratischer Zeit annähern, indem sie entfernte Partikel gruppieren oder das Feld auf einem Gitter lösen.

Scope

Dieses Thema behandelt skalierbare Algorithmen für weitreichende Partikelwechselwirkungen: hierarchische Baumcodes wie Barnes-Hut, die schnelle Multipolmethode und gitterbasierte Partikel-Mesh- sowie Partikel-Partikel-Partikel-Mesh-Verfahren. Es befasst sich mit den Kompromissen zwischen Genauigkeit und Kosten und der Rolle dieser Methoden in großen Gravitations- und elektrostatischen Simulationen.

Core questions

• Warum ist die direkte Summierung paarweiser weitreichender Kräfte prohibitiv teuer?
• Wie gruppieren Baumcodes entfernte Partikel, um die Kosten der Kraftberechnung zu reduzieren?
• Wie erreicht die schnelle Multipolmethode eine nahezu lineare Skalierung mit kontrolliertem Fehler?
• Wie lösen Partikel-Mesh-Methoden das Feld auf einem Gitter, um weitreichende Kräfte zu behandeln?

Key theories

Hierarchische Baumcodes

Der Barnes-Hut-Algorithmus gruppiert entfernte Partikel in Zellen, deren kollektive Kraft durch ihren Massenmittelpunkt angenähert wird, wodurch die Kosten der Kraftauswertung von quadratisch auf die Größenordnung N log N reduziert werden.

Schnelle Multipolmethode

Die schnelle Multipolmethode stellt Partikelgruppen durch abgeschnittene Multipolexpansionen dar und übersetzt diese hierarchisch, wodurch eine nahezu lineare Skalierung mit einer streng kontrollierbaren Genauigkeit erreicht wird.

Partikel-Mesh-Methoden

Partikel-Mesh- und Partikel-Partikel-Partikel-Mesh-Verfahren interpolieren Ladungen oder Massen auf ein Gitter, lösen das Feld mit schnellen Fourier-Transformationen und fügen kurzreichweitige Korrekturen hinzu, wodurch weitreichende Wechselwirkungen effizient behandelt werden.

Clinical relevance

Diese Methoden treiben kosmologische und galaktische N-Körper-Simulationen der Strukturbildung, Plasmasimulationen und die weitreichende Elektrostatik großer molekularer Systeme voran. Die schnelle Multipolmethode gilt als einer der wichtigsten Algorithmen des zwanzigsten Jahrhunderts.

History

Partikel-Mesh-Methoden wurden in den 1980er Jahren von Hockney und Eastwood systematisiert; der Barnes-Hut-Baumcode von 1986 und die schnelle Multipolmethode von Greengard und Rokhlin von 1987 revolutionierten die N-Körper-Simulation und ermöglichten die darauf folgenden großen kosmologischen und molekularen Simulationen.

Key figures

• Josh Barnes
• Piet Hut
• Leslie Greengard
• Vladimir Rokhlin

Seminal works

• barneshut1986
• greengard1987

Frequently asked questions

Warum nicht einfach jede paarweise Kraft direkt berechnen?

Die Kosten der direkten Summierung wachsen quadratisch mit der Partikelanzahl, sodass eine Verdopplung der Partikel die Arbeitslast vervierfacht. Dies wird für die Millionen oder Milliarden von Partikeln in kosmologischen und großen molekularen Simulationen unmöglich. Schnelle Methoden reduzieren dies auf nahezu lineare Kosten.

Wie kontrollieren Baum- und Multipolmethoden ihren Fehler?

Sie approximieren den Einfluss entfernter Partikelgruppen, und die Approximation wird durch die Einbeziehung weiterer Multipolterme oder die Verwendung eines strengeren Öffnungskriteriums verfeinert, sodass Genauigkeit und Geschwindigkeit kontrolliert gegeneinander abgewogen werden können.