Listy komórek

Listy komórek (czasami określane również jako listy połączone z komórkami ) to struktura danych w symulacjach dynamiki molekularnej służąca do znajdowania wszystkich par atomów w określonej odległości od siebie. Pary te są potrzebne do obliczenia oddziaływań niezwiązanych krótkiego zasięgu w systemie, takich jak siły Van der Waalsa lub część oddziaływania elektrostatycznego krótkiego zasięgu przy użyciu sumowania Ewalda .

Algorytm

Oddziaływania parami dla pojedynczej cząstki można obliczyć, a) obliczając oddziaływanie ze wszystkimi innymi cząstkami lub b) dzieląc domenę na komórki o długości krawędzi co najmniej promienia odcięcia potencjału interakcji i obliczając oddziaływanie między cząsteczkę i wszystkie cząstki w tej samej (czerwonej) i sąsiedniej (zielonej) komórce.

Listy komórek działają poprzez podział domeny symulacji na komórki o długości krawędzi większej lub równej promieniowi odcięcia interakcji, która ma zostać obliczona. Cząstki są sortowane do tych komórek, a interakcje są obliczane między cząstkami w tej samej lub sąsiednich komórkach.

W swojej najbardziej podstawowej formie niezwiązane interakcje dla odległości odcięcia $do {\ displaystyle r_ {c}}$ obliczane w następujący sposób:

dla wszystkich sąsiednich par komórek ${\ Displaystyle (C _ {\ alfa}, C_ {\ beta})}$ zrobić

dla wszystkich ${\ Displaystyle p_ {\ alfa} \ w C_ {\ alfa }}$ zrobić

dla wszystkich ${\ Displaystyle p _ {\ beta} \ w C _ {\ beta}}$ zrobić

${\ Displaystyle r ^{2}=\|\mathbf {x} [p_{\alpha }]-\mathbf {x} [p_{\beta }]\|_{2}^{2}}$

jeśli ${\ Displaystyle r ^ {2} \ leq r_ {c} ^ {2}}$ następnie

Oblicz interakcję między ${\ displaystyle p_ {\ alfa}}$ i ${\ displaystyle p_ {\ beta}}$ .

koniec, jeśli

koniec za

koniec za

koniec za

$we$ długość komórki wynosi co najmniej $odległości$ , nie można pominąć żadnych cząstek w od siebie

$pod$$displaystyle N$ symulację z cząstkami o jednorodnej gęstości cząstek, liczba komórek $N$ proporcjonalna do i odwrotnie proporcjonalna do promienia odcięcia (tj. jeśli $\displaystyle N}$$}$ wzrasta, podobnie jak liczba komórek). $liczby$ średnia liczba cząstek na komórkę całkowitej Koszt interakcji dwóch komórek wynosi ${\ Displaystyle {\ mathcal {O}} ({\ overline {c}} ^ {2})}$ . Liczba par komórek $,$ która jest ponownie proporcjonalna do liczby cząstek . Całkowity koszt znalezienia wszystkich odległości parami w danej granicy wynosi ${\ Displaystyle {\ mathcal {O}} (Nc) \ in {\ mathcal {O}} (N )} , co$$odległości$ znacznie lepsze parami

Okresowe warunki brzegowe

W większości symulacji stosuje się okresowe warunki brzegowe , aby uniknąć narzucania sztucznych warunków brzegowych. Korzystając z list komórek, granice te można zaimplementować na dwa sposoby.

Komórki duchów

Okresowe warunki brzegowe można symulować, zawijając pudełko symulacji w dodatkową warstwę komórek (zacieniowane na pomarańczowo) zawierającą okresowe kopie komórek brzegowych (niebieskie cząstki).

W podejściu z komórkami widmowymi pudełko symulacji jest opakowane w dodatkową warstwę komórek. Komórki te zawierają okresowo zawijane kopie odpowiednich komórek symulacji wewnątrz domeny.

Chociaż dane — a zwykle także koszt obliczeniowy — są podwojone w przypadku interakcji przekraczających granicę okresową, to podejście ma tę zaletę, że jest proste do wdrożenia i bardzo łatwe do zrównoleglenia, ponieważ komórki będą wchodzić w interakcje tylko ze swoimi sąsiadami geograficznymi.

Okresowe owijanie

Zamiast tworzyć komórki duchy, pary komórek, które oddziałują na okresową granicę, mogą również używać okresowego wektora korekcyjnego ${\ displaystyle \ mathbf {q} _ {\ alfa \ beta}$ } Ten wektor $zawiera$ można zapisać lub obliczyć dla każdej pary komórek należy zastosować do „zawijania jedną komórkę wokół domeny, aby sąsiadowała z drugą. ${\ Displaystyle p _ {\ alfa} \ w C_ {\ alfa}}$ ∈ i ${\ Displaystyle p_ {\ beta} \ w C_ {\ beta$ } następnie obliczone jako

${\ Displaystyle r ^ {2} = \|\ mathbf {x} [p_ {\ alfa}] - \ mathbf {x } [p_{\beta}]-\mathbf {q} _{\alpha \beta}\|_{2}^{2}}$ .

To podejście, chociaż bardziej wydajne niż użycie komórek duchów, jest mniej proste do wdrożenia (pary komórek należy zidentyfikować na granicach okresowych, a wektor ${\ Displaystyle \ mathbf {q} _ {\ alfa \ beta}}$ musi być obliczona/przechowana).

Ulepszenia

Pomimo zmniejszenia kosztu obliczeniowego znalezienia wszystkich par w danej odległości odcięcia od ${\ Displaystyle {\ mathcal {O}} (N ^ {2})}$ do ${\ Displaystyle {\ mathcal {O}}(N)}$ , algorytm listy komórek wymieniony powyżej nadal ma pewne nieefektywności.

$do {\ displaystyle r_ {c}}$ w trzech wymiarach z długością krawędzi równą promieniowi odcięcia . Obliczana jest parami odległość między wszystkimi cząstkami w komórce iw jednej z sąsiednich komórek. Cela ma 26 sąsiadów: 6 ma wspólną twarz, 12 ma wspólną krawędź i 8 ma wspólny kąt. Ze wszystkich obliczonych odległości parami tylko około 16% będzie w rzeczywistości mniejszych lub równych r do $displaystyle r_ {c}}$ . Innymi słowy, 84% wszystkich obliczeń odległości parami jest fałszywych.

$mniejszej$ sposobów przezwyciężenia tej nieefektywności jest podzielenie domeny na komórki o długości krawędzi . Interakcje parami są wtedy obliczane nie tylko między $nawzajem$ komórkami, ale między wszystkimi komórkami w obrębie siebie (po raz pierwszy zasugerowane i zaimplementowane oraz przeanalizowane w i ) To podejście można doprowadzić do granicy, w której każda komórka zawiera co najwyżej jedną pojedynczą cząstkę, zmniejszając w ten sposób liczbę fałszywych ocen odległości parami do zera. Ten wzrost wydajności jest jednak szybko równoważony przez liczbę komórek, które należy sprawdzić pod kątem każdej interakcji z komórką, $}}$ do $β$ , na przykład w trzech wymiarach, rośnie sześciennie z odwrotnością długości krawędzi komórki. $Jednak$ ustawienie długości krawędzi na liczbę fałszywych ocen odległości do 63

Inne podejście zostało opisane i przetestowane w Gonnet, w którym cząstki są najpierw sortowane wzdłuż osi łączącej centra komórek. Takie podejście generuje tylko około 40% fałszywych obliczeń odległości parami, ale wiąże się z dodatkowymi kosztami wynikającymi z sortowania cząstek.

Zobacz też

• Lista Verletów