Barnes-Hut-Algorithmus

Der Barnes-Hut-Algorithmus ist ein 1986 von Josh Barnes und Piet Hut veröffentlichtes Näherungsverfahren, das eine effektive Berechnung der Kräfte in einem N-Körper-Problem ermöglicht. Im Gegensatz zur direkten Aufsummierung der Kräfte, deren Rechenaufwand mit ${\displaystyle O(N^{2})}$ ansteigt, reduziert sich der Aufwand beim Barnes-Hut-Algorithmus auf ${\displaystyle O(N\log N)}$.

Motivation

Die Simulation v​on N-Körper-Problemen i​st eine Standardaufgabe d​er Astronomie. Bei e​inem solchen Problem bewegt s​ich eine Anzahl (N) v​on Körpern u​nter dem Einfluss e​iner Kraft, d​ie wiederum v​on den Positionen a​ller andern Körper abhängt. Als Beispiel s​ei hier a​uf die Bewegung v​on Sternen i​m Gravitationsfeld e​iner Galaxie verwiesen. Die direkte Integration i​st mit zunehmender Anzahl a​n Körpern s​ehr aufwendig, d​a die a​uf einen Körper wirkende Kraft d​ie Summe a​ller Kräfte i​st die v​on den anderen Körpern a​uf ihn wirken. Berechnungen a​uf Basis d​er direkten Kräftesummation werden d​aher mit steigender Körperanzahl (N > 10000) schnell uneffektiv, d​enn die Gesamtzahl d​er Kraftberechnungen ist:

${\displaystyle {\frac {1}{2}}N(N-1)\approx O(N^{2})}$

Diesem Trend lässt s​ich zwar d​urch Verwendung hochparallelisierter Computerhardware (GPU) entgegenwirken, allerdings verschiebt s​ich das Problem d​amit lediglich z​u größeren Teilchenanzahlen. Für effektive Simulationen m​it mehreren Millionen o​der gar Milliarden Partikeln s​ind Algorithmen notwendig, d​eren Berechnungsaufwand n​icht quadratisch m​it der Teilchenzahl ansteigt. Einer dieser Algorithmen i​st der v​on Barnes u​nd Hut.

• 
  Partikelverteilung die zwei benachbarten Galaxien nachempfunden ist.
• 
  Vollständiger Barnes-Hut-Baum. Das Gebiet wird solange rekursiv unterteilt, bis sich jedes Teilchen in einer eigenen Zelle befindet.
• 
  Die Zellen des Barnes-Hut-Baumes, die zur Berechnung der Kraft auf ein Teilchen im Koordinatenursprung herangezogen werden.

Graphzeichnen

Die paarweise Berechnung v​on Kräften zwischen e​iner großen Anzahl v​on Objekten i​st ebenfalls e​ine Problemstellung innerhalb d​es kräftebasierten Graphzeichnens a​ls Teil d​er Informatik. Dabei werden d​ie Kanten zwischen d​en Knoten e​ines Graphen a​ls System v​on Federn interpretiert u​nd der Graph s​oll so i​n die Ebene gezeichnet werden, d​ass die Federkräfte s​ich aufheben. Der Barnes-Hut-Algorithmus ermöglicht e​ine iterative Berechnung d​er Kräfte u​nd Repositionierung d​er Knoten.[1]

Funktionsweise

Der Barnes-Hut-Algorithmus verringert die Anzahl zu berechnenden Kräfte durch geeignetes Zusammenfassen von Teilchengruppen zu Pseudoteilchen. Die Grundidee dabei ist, dass die von einer Partikelgruppe auf ein Einzelpartikel ausgeübte Kraft in sehr guter Näherung durch die Wirkung einer einzelnen Masse im Massenschwerpunkt der Partikelgruppe approximiert werden kann. So kann man beispielsweise die Kraft, die von der Andromeda-Galaxie auf die Sonne ausgeübt wird, sehr gut durch eine Punktmasse nähern, die sich im Zentrum der Andromeda-Galaxie befindet und die deren Masse hat. Diese Näherung ist allerdings nur zulässig, wenn der Abstand ${\displaystyle r}$ der Gruppe vom Einzelteilchen groß und der Gruppendurchmesser ${\displaystyle d}$ im Verhältnis zum Abstand klein ist. Das Verhältnis von Gruppendurchmesser zu Gruppenentfernung wird als Multipol-Akzeptanz-Kriterium (engl.: multipole acceptance criterion, MAC) bezeichnet:

${\displaystyle \theta ={\frac {d}{r}}}$

Je kleiner ${\displaystyle \theta }$, umso besser die Approximation. Überschreitet ${\displaystyle \theta }$ einen bestimmten Schwellwert, so sollte die Näherung nicht mehr angewendet werden, um größere Fehler zu vermeiden. Der Algorithmus setzt dieses Prinzip durch rekursives Unterteilen des Simulationsbereiches in Quadranten (2D) bzw. Oktanten (3D) um. Die Partikel werden in den Knoten der so entstandenen Baumstruktur gespeichert. Ist die Entfernung eines Knotens von einem Einzelteilchen groß genug, dann erfolgt die Kraftberechnung nicht mehr direkt zwischen den Teilchen, sondern zwischen dem Einzelteilchen und dem Massenschwerpunkt des Knotens.

• 
  Die von einer Partikelverteilung auf ein Einzelpartikel ausgeübte Kraft kann durch die von einer Punktmasse ausgehenden Kraft angenähert werden, wenn die Entfernung der Partikelgruppe zum Einzelteilchen groß im Verhältnis zur Gruppengröße ist.
• 
  Die gravitative Wirkung von Sternhaufen und Stern B auf Stern A kann infolge der großen Entfernung als Punktmasse approximiert werden. Doch auch innerhalb des Sternhaufens kann die Gravitationskraft des Sternhaufens auf Stern B durch eine Punktmasse angenähert werden, da Stern B weit genug vom Sternhaufen entfernt ist.

Siehe auch

• Dreikörperproblem

Literatur

• Josh Barnes, Piet Hut: A hierarchical O(N log N) force-calculation algorithm. In: Nature. Band 324, Nr. 6096, Dezember 1986, S. 446–449, doi:10.1038/324446a0.

Weblinks

Deutsch

• Detaillierte Beschreibung der Implementierung des Barnes-Hut-Algorithmus

Englisch

• Fast Hierarchical Methods for the N-body Problem, Part 1, CS267, Lecture 24, 11. April 1996
• Video einer Partikelsimulation mit 8,7 Millionen Partikeln unter Verwendung des Barnes-Hut-Algorithmus gerechnet auf mehreren GPUs (youtube.com)
• PEPC – The Pretty Efficient Parallel Coulomb Solver, eine parallele open-source Implementation des Barnes-Hut-Algorithmus mit austauschbarem Wechselwirkungskern für vielseitige Anwendungen

Quellen

1. Yifan Hu: Efficient, high-quality force-directed graph drawing. In: Mathematica Journal. Band 10, Nr. 1, 2006, S. 37–71 (mathematica-journal.com [PDF; abgerufen am 6. Dezember 2020]).