Optimierung

Durch die gegenseitige Wechselwirkung ist der Aufwand bei $N$ Teilchen $O(N^2)$, da der Einfluß von allen Teilchen auf jedes Teilchen berücksichtigt wird. Nun ist es aber so, daß die Stärke der Kraft von der Entfernung der Teilchen abhängt. Nur die Teilchen in näherer Umgebung haben einen wirklichen Einfluß auf die Bewegung. Um das auszunutzen gibt es verschiedene Ansätze:

1. Nachbarschaftstafeln
   Für jedes Teilchen $i$ gibt es eine Liste von Teilchen die sich innerhalb einer Kugel (oder eines Kreises) mit dem Radius $R$ um Teilchen $i$ befinden. $R$ muß dabei größer als die Reichweite der Kräfte sein. Für das Teilchen $i$ werden nur die Kräfte aus den in der Liste stehenden Teilchen berechnet und die Liste wird regelmäßig erneuert. Der Erneuerungsprozeß kann zwar $O(N^2)$ sein, aber der Aufwand muß nur nach vielen Zeitschritten betrieben werden.

2. linked-cell (verbundene Zellen)
   Der Raum (die Ebene) wird in einzelne Zellen unterteilt. Jede Zelle besitzt eine Liste der Teilchen in ihr und jedes Teilchen in einer Zelle wechselwirkt nur mit Teilchen in umgebenden Zellen. Für die Berechnung werden nur die Teilchen aus der eigenen und den benachbarten Zellen herangezogen.

Abbildung: Verlet-Nachbarschaftstafeln (oben) und linked-cell (unten)

Durch Kombination dieser beiden Methoden kann man einen Aufwand von $O(N)$ erreichen. Außerdem lassen sich die Methoden sehr einfach parallelisieren und so auch auf Systemen mit mehreren Recheneinheiten effektiv realisieren.