Seznamy buněk - Cell lists

Seznamy buněk (někdy také označované jako seznamy propojených buněk) je datová struktura v molekulární dynamika simulace k vyhledání všech atomových párů v dané mezní vzdálenosti. Tyto páry jsou potřebné k výpočtu vazebných interakcí krátkého dosahu v systému, jako je například Van der Waalsovy síly nebo část krátkého dosahu elektrostatické interakce při použití Ewaldův součet.

Algoritmus

Párové interakce pro jednu částici lze vypočítat a) výpočtem interakce se všemi ostatními částicemi nebo b) rozdělením domény na buňky s délkou hrany minimálně poloměrem meze interakčního potenciálu a výpočtem interakce mezi částicemi a všemi částicemi ve stejných (červených) a v sousedních (zelených) buňkách.

Seznamy buněk fungují tak, že se simulační doména rozdělí na buňky s délkou hrany větší nebo rovnou meznímu poloměru vypočítané interakce. Částice jsou tříděny do těchto buněk a jsou počítány interakce mezi částicemi ve stejných nebo sousedních buňkách.

Ve své nejzákladnější formě jsou nevázané interakce na mezní vzdálenost ${displaystyle r_ {c}}$ se počítají takto:

pro všechny sousední buněčné páry ${displaystyle (C_ {alpha}, C_ {eta})}$ dělat

pro všechny ${displaystyle p_ {alpha} v C_ {alpha}}$ dělat

pro všechny ${displaystyle p_ {eta} v C_ {eta}}$ dělat

${displaystyle r ^ {2} = | mathbf {x} [p_ {alpha}] - mathbf {x} [p_ {eta}] | _ {2} ^ {2}}$

-li ${displaystyle r ^ {2} leq r_ {c} ^ {2}}$ pak

Vypočítejte interakci mezi ${displaystyle p_ {alpha}}$ a ${displaystyle p_ {eta}}$.

skončit, pokud

konec pro

konec pro

konec pro

Protože délka buňky je alespoň ${displaystyle r_ {c}}$ ve všech dimenzích, žádné částice uvnitř ${displaystyle r_ {c}}$ navzájem mohou chybět.

Vzhledem k simulaci s ${displaystyle N}$ částice s homogenní hustotou částic, počet buněk ${displaystyle m}$ je úměrný ${displaystyle N}$ a nepřímo úměrné poloměru cut-off (tj. pokud ${displaystyle N}$ se zvyšuje, tak se zvyšuje i počet buněk). Průměrný počet částic na buňku ${displaystyle {overline {c}} = N / m}$ proto nezávisí na celkovém počtu částic. Náklady na interakci dvou buněk jsou v ${displaystyle {mathcal {O}} ({overline {c}} ^ {2})}$. Počet párů buněk je úměrný počtu buněk, který je opět úměrný počtu částic ${displaystyle N}$. Celkové náklady na nalezení všech párových vzdáleností v rámci dané mezní hodnoty jsou v ${displaystyle {mathcal {O}} (Nc) v {mathcal {O}} (N)}$, což je výrazně lepší než výpočet ${displaystyle {mathcal {O}} (N ^ {2})}$ párové vzdálenosti naivně.

Periodické okrajové podmínky

Ve většině simulací periodické okrajové podmínky se používají, aby se zabránilo zavedení umělých okrajových podmínek. Pomocí seznamů buněk lze tyto hranice implementovat dvěma způsoby.

Buňky duchů

Periodické okrajové podmínky lze simulovat tak, že se simulační rámeček zabalí do další vrstvy buněk (stínovaná oranžová) obsahující periodické kopie hraničních buněk (modré částice).

V přístupu buněk duchů je pole simulace zabaleno do další vrstvy buněk. Tyto buňky obsahují pravidelně zabalené kopie odpovídajících simulačních buněk uvnitř domény.

Přestože jsou data - a obvykle také výpočetní náklady - pro interakce přes periodické hranice zdvojnásobena, má tento přístup tu výhodu, že je přímý na implementaci a je velmi snadné jej paralelizovat, protože buňky budou interagovat pouze se svými geografickými sousedy.

Periodické balení

Místo vytváření buněk duchů mohou páry buněk, které interagují přes periodickou hranici, také použít vektor periodické korekce ${displaystyle mathbf {q} _ {alpha eta}}$. Tento vektor, který lze uložit nebo vypočítat pro každý pár buněk ${displaystyle (C_ {alpha}, C_ {eta})}$, obsahuje opravu, kterou je třeba použít k "zabalení" jedné buňky kolem domény tak, aby sousedila s druhou. Párová vzdálenost mezi dvěma částicemi ${displaystyle p_ {alpha} v C_ {alpha}}$ a ${displaystyle p_ {eta} v C_ {eta}}$ se pak počítá jako

${displaystyle r ^ {2} = | mathbf {x} [p_ {alpha}] - mathbf {x} [p_ {eta}] - mathbf {q} _ {alpha eta} | _ {2} ^ {2}}$.

Tento přístup, i když je účinnější než použití buněk duchů, je implementován méně přímočaře (páry buněk je třeba identifikovat přes periodické hranice a vektor ${displaystyle mathbf {q} _ {alpha eta}}$ je třeba vypočítat / uložit).

Vylepšení

I přes snížení výpočetních nákladů na nalezení všech párů v dané mezní vzdálenosti od ${displaystyle {mathcal {O}} (N ^ {2})}$ na ${displaystyle {mathcal {O}} (N)}$výše uvedený algoritmus seznamu buněk má stále některé neúčinnosti.

Vezměme si výpočetní buňku ve třech rozměrech s délkou hrany rovnou poloměru ořezu ${displaystyle r_ {c}}$. Je vypočítána párová vzdálenost mezi všemi částicemi v buňce a v jedné ze sousedních buněk. Buňka má 26 sousedů: 6 sdílí společnou tvář, 12 sdílí společnou hranu a 8 sdílí společný roh. Ze všech vypočítaných párových vzdáleností bude pouze asi 16% ve skutečnosti menší nebo rovno ${displaystyle r_ {c}}$. Jinými slovy, 84% všech párových výpočtů vzdálenosti je falešných.

Jedním ze způsobů, jak překonat tuto neúčinnost, je rozdělit doménu na buňky s délkou hrany menší než ${displaystyle r_ {c}}$. Párové interakce se pak nepočítají jen mezi sousedními buňkami, ale také mezi všemi buňkami uvnitř ${displaystyle r_ {c}}$ navzájem (nejprve navrženo v ^[1] a implementováno a analyzováno v ^[2][3] a ^[4]). Tento přístup lze vzít na hranici, kde každá buňka obsahuje nanejvýš jednu jedinou částici, čímž se sníží počet rušivých vyhodnocení párových vzdáleností na nulu. Tento nárůst efektivity je však rychle kompenzován počtem buněk ${displaystyle C_ {eta}}$ které je třeba kontrolovat při každé interakci s buňkou ${displaystyle C_ {alpha}}$, který například ve třech rozměrech roste kubicky s inverzí délky hrany buňky. Nastavení délky hrany na ${displaystyle r_ {c} / 2}$však již snižuje počet falešných hodnocení vzdálenosti na 63%.

Další přístup je uveden a testován v Gonnetu,^[5] ve kterém jsou částice nejprve tříděny podél osy spojující buněčná centra. Tento přístup generuje pouze asi 40% rušivých párových výpočtů vzdálenosti, přesto přináší další náklady v důsledku třídění částic.

Viz také

• Seznam verletů

Reference