Elenchi di celle - Cell lists

Le liste di celle (a volte chiamate anche liste collegate di celle ) sono una struttura di dati nelle simulazioni di dinamica molecolare per trovare tutte le coppie di atomi entro una determinata distanza di taglio l'una dall'altra. Queste coppie sono necessarie per calcolare le interazioni non legate a corto raggio in un sistema, come le forze di Van der Waals o la parte a corto raggio dell'interazione elettrostatica quando si utilizza la sommatoria di Ewald .

Algoritmo

Le interazioni a coppie per una singola particella possono essere calcolate a) calcolando l'interazione con tutte le altre particelle o b) dividendo il dominio in celle con una lunghezza del bordo almeno pari al raggio di taglio del potenziale di interazione e calcolando l'interazione tra la particella e tutte le particelle nelle stesse (rosse) e nelle adiacenti (verdi) celle.

Gli elenchi di celle funzionano suddividendo il dominio di simulazione in celle con una lunghezza del bordo maggiore o uguale al raggio di taglio dell'interazione da calcolare. Le particelle vengono ordinate in queste celle e le interazioni vengono calcolate tra le particelle nelle stesse celle o nelle celle vicine.

Nella sua forma più elementare, le interazioni non legate per una distanza di taglio sono calcolate come segue: ${\displaystyle r_{c}}$

per tutte le coppie di cellule vicine do${\displaystyle (C_{\alpha },C_{\beta })}$

per tutto fare${\displaystyle p_{\alpha }\in C_{\alpha }}$

per tutto fare${\displaystyle p_{\beta }\in C_{\beta }}$

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

se poi${\displaystyle r^{2}\leq r_{c}^{2}}$

Calcola l'interazione tra e .${\displaystyle p_{\alpha }}$${\displaystyle p_{\beta }}$

finisci se

fine per

fine per

fine per

Poiché la lunghezza della cella è almeno in tutte le dimensioni, nessuna particella l'una dentro l'altra può essere persa. ${\displaystyle r_{c}}$${\displaystyle r_{c}}$

Data una simulazione con particelle con una densità di particelle omogenea, il numero di celle è proporzionale e inversamente proporzionale al raggio di taglio (cioè se aumenta, aumenta anche il numero di celle). Il numero medio di particelle per cellula quindi non dipende dal numero totale di particelle. Il costo dell'interazione di due celle è di . Il numero di coppie di cellule è proporzionale al numero di cellule che è ancora proporzionale al numero di particelle . Il costo totale per trovare tutte le distanze a coppie all'interno di un dato cut-off è in , che è significativamente migliore rispetto al calcolo ingenuo delle distanze a coppie. ${\displaystyle N}$${\displaystyle m}$${\displaystyle N}$${\displaystyle N}$${\displaystyle {\overline {c}}=N/m}$${\displaystyle {\mathcal {O}}({\overline {c}}^{2})}$${\displaystyle N}$${\displaystyle {\mathcal {O}}(Nc)\in {\mathcal {O}}(N)}$${\displaystyle {\mathcal {O}}(N^{2})}$

Condizioni al contorno periodiche

Nella maggior parte delle simulazioni, vengono utilizzate condizioni al contorno periodiche per evitare di imporre condizioni al contorno artificiali. Utilizzando gli elenchi di celle, questi limiti possono essere implementati in due modi.

Cellule fantasma

Le condizioni al contorno periodiche possono essere simulate avvolgendo il riquadro di simulazione in uno strato aggiuntivo di celle (ombreggiato in arancione) contenente copie periodiche delle celle al contorno (particelle blu).

Nell'approccio delle celle fantasma, la scatola di simulazione è avvolta in un ulteriore strato di celle. Queste celle contengono copie avvolte periodicamente delle celle di simulazione corrispondenti all'interno del dominio.

Sebbene i dati, e di solito anche il costo computazionale, siano raddoppiati per le interazioni oltre il confine periodico, questo approccio ha il vantaggio di essere semplice da implementare e molto facile da parallelizzare, poiché le celle interagiranno solo con i loro vicini geografici.

Incarto periodico

Invece di creare celle fantasma, le coppie di celle che interagiscono su un confine periodico possono anche utilizzare un vettore di correzione periodica . Questo vettore, che può essere memorizzato o calcolato per ogni coppia di celle , contiene la correzione che deve essere applicata per "avvolgere" una cella attorno al dominio per avvicinarla all'altra. La distanza a coppie tra due particelle e viene quindi calcolata come ${\displaystyle \mathbf {q} _{\alpha \beta }}$${\displaystyle (C_{\alpha },C_{\beta })}$${\displaystyle p_{\alpha }\in C_{\alpha }}$${\displaystyle p_{\beta }\in C_{\beta }}$

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

Questo approccio, sebbene più efficiente rispetto all'utilizzo di celle fantasma, è meno semplice da implementare (le coppie di celle devono essere identificate sui confini periodici e il vettore deve essere calcolato/memorizzato). ${\displaystyle \mathbf {q} _{\alpha \beta }}$

Miglioramenti

Nonostante la riduzione del costo computazionale per trovare tutte le coppie entro una determinata distanza di taglio da a , l'algoritmo dell'elenco di celle sopra elencato presenta ancora alcune inefficienze. ${\displaystyle {\mathcal {O}}(N^{2})}$${\displaystyle {\mathcal {O}}(N)}$

Considera una cella di calcolo in tre dimensioni con lunghezza del bordo uguale al raggio di taglio . Viene calcolata la distanza a coppie tra tutte le particelle nella cella e in una delle celle vicine. La cella ha 26 vicini: 6 che condividono una faccia comune, 12 che condividono un bordo comune e 8 che condividono un angolo comune. Di tutte le distanze a coppie calcolate, solo il 16% circa sarà effettivamente inferiore o uguale a . In altre parole, l'84% di tutti i calcoli della distanza a coppie è falso. ${\displaystyle r_{c}}$${\displaystyle r_{c}}$

Un modo per superare questa inefficienza consiste nel partizionare il dominio in celle di lunghezza del bordo inferiore a . Le interazioni a coppie non vengono quindi calcolate solo tra celle vicine, ma tra tutte le celle all'interno l' una dell'altra (prima suggerite e implementate e analizzate in e ). Questo approccio può essere portato al limite in cui ogni cella contiene al massimo una singola particella, riducendo quindi a zero il numero di valutazioni spurie della distanza a coppie. Questo guadagno di efficienza è però rapidamente compensato dal numero di celle che devono essere ispezionate per ogni interazione con una cella che, ad esempio in tre dimensioni, cresce cubicamente con l'inverso della lunghezza del bordo della cella. L'impostazione della lunghezza del bordo su , tuttavia, riduce già il numero di valutazioni false della distanza al 63%. ${\displaystyle r_{c}}$${\displaystyle r_{c}}$${\displaystyle C_{\beta }}$${\displaystyle C_{\alpha }}$${\displaystyle r_{c}/2}$

Un altro approccio è delineato e testato in Gonnet, in cui le particelle vengono prima ordinate lungo l'asse che collega i centri cellulari. Questo approccio genera solo circa il 40% di calcoli spuri della distanza a coppie, ma comporta un costo aggiuntivo dovuto all'ordinamento delle particelle.

Guarda anche

• Lista Verlet

Riferimenti