Ich möchte zwei Algorithmen vorstellen, die für die schnelle Kollisionserkennung in Simulationen mit granularen Medien nützlich sind. Wir alle wissen, dass der zeitaufwändigste Teil bei Molekulardynamik-Simulationen die Kollisionserkennung ist. Normalerweise kann dieses Problem gelöst werden, indem man die Form der Partikel auf Kugeln beschränkt. Aber wenn man beliebige konvexe Polygone verwenden will, braucht man schnellere Algorithmen.
Zunächst einmal ein wenig Philosophie: Im Allgemeinen wollen wir in der Computerphysik Informationen, und die muss man mit Rechenzeit bezahlen. Wenn also Information teuer ist, sollte man sie recyceln!
Im Ernst, wenn wir eine Molekulardynamik-Simulation von körnigen Materialien haben, ändert sich der Zustand des Systems sehr langsam. Die Information, die wir im letzten Zeitschritt gewonnen haben, ist also nahezu korrekt. Wir sollten versuchen, diese Informationen wiederzuverwenden. Entweder indem wir sie als Startbedingungen verwenden oder indem wir nur die Änderungen zwischen den Zeitschritten berechnen, so dass wir die alten Informationen korrigieren können. Wenn wir einen guten Algorithmus wählen, der diese Arbeit erledigt, können wir eine Menge Zeit sparen.