Das Mehrkörperproblem in der Astronomie/ Hierarchische Algorithmen/ Problematik des Rechenaufwands

Das entscheidende Maß für die Effizienz der Simulation eines Mehrkörperensembles ist die Anzahl der Rechenschritte, die in Abhängigkeit von der Anzahl $N$ dessen Mitglieder erforderlich sind. In dieser Hinsicht schneiden die bisher erarbeiteten Methoden leider unzureichend ab. Bei Verwendung individueller Zeitschritte müssen, um nur einen einzigen Massenpunkt zu bewegen, die Positionen (und je nach Verfahren auch die Geschwindigkeiten) aller Körper extrapoliert werden. Der Rechenaufwand für einen solchen Vorgang wächst linear mit $N$. Um die Beschleunigung (und gegebenenfalls auch den Ruck) des gerade betrachteten Objekts an dessen extrapolierter Position zu berechnen, ist die Kenntnis der Abstände (und eventuell auch der Geschwindigkeitsdifferenzen) zu allen anderen Massenpunkten erforderlich. Erneut ist der Aufwand direkt proportional zu $N$. Da alle $N$ Mitglieder gleichermaßen von diesen Zusammenhängen betroffen sind, gilt insgesamt eine Proportionalität zu $N^{2}$, um die Simulation effektiv um einen Schritt weiter voranzubringen.

Das Ziel der nun vorgestellten Algorithmen besteht darin, stattdessen eine Abhängigkeit der Größenordnung $N\log(N)$ zu erreichen, was durch eine hierarchische Organisation der Zeitschritte und der räumlichen Verteilung der Körper erreicht werden kann. Je mehr Mitglieder ein System enthält, umso dramatischer fällt der Unterschied zwischen einem Verfahren ohne und mit hierarchischer Struktur aus.

Abhängigkeit des Rechenaufwands pro Zeitschritt von der Anzahl N der Mitglieder einer Mehrkörpersimulation für einen Algorithmus ohne und mit hierarchischer Organisation. Bei einfachen Verfahren ist der Aufwand proportional zu $N^{2}$, bei hierarchischen Methoden hingegen nur zu $N\log(N)$

Für die Plejaden (2100 Sterne) liegt der Aufwand $N^{2}$ mit einem Standardalgorithmus bei 4410000, mit einem hierarchischen Verfahren dagegen bei $N\log(N)=6977$, was einer Verbesserung um einen Faktor 632 entspricht. 47 Tucanae (1 Million Sterne) weist mit einem einfachen Verfahren einen Aufwand von 1 Billion, mit einem hierarchischen Algorithmus dagegen von 6000000 auf - eine Steigerung um etwa den Faktor 167000. Von den Plejaden hin zu 47 Tucanae wächst mit den bisherigen Methoden der Aufwand um einen Faktor 227000, mit einem hierarchischen Algorithmus dagegen nur um einen Faktor 860.

Die Frage der Rechenarbeit ist auch deshalb so drängend, weil nicht nur der Aufwand pro Zeitschritt mit $N$ wächst, sondern auch die für eine Simulation notwendige Anzahl $S$ an Schritten selbst. Wie bereits dargelegt, müssen mit zunehmendem $N$ bei festgehaltener Größe des Ensembles die Plummerradien und damit die minimalen dynamischen Zeiten immer kleiner gehalten werden. Für den Fall, dass auch lokale Besonderheiten berücksichtigt werden sollen, wurde eine Abhängigkeit der Form $S\sim N^{3/2}$ abgeleitet. Ohne eine Verbesserung der Effizienz würde der Aufwand für eine Simulation proportional zu $N^{2}N^{3/2}=N^{7/2}$ ansteigen. Selbst mit einem hierarchischen Algorithmus liegt mit einem Aufwand proportional zu $N\log(N)N^{3/2}=N^{5/2}\log(N)$ noch ein enormer Anstieg mit zunehmender Anzahl von Masssenpunkten vor.