Una lista Verlet (dal nome di Loup Verlet) è una struttura dati nelle simulazioni di dinamica molecolare per mantenere in modo efficiente una lista di tutte le particelle entro una data distanza di cut-off l’una dall’altra.
Questo metodo può essere facilmente applicato alle simulazioni Monte Carlo. Per le interazioni a corto raggio, viene in genere utilizzato un raggio di cut-off, oltre il quale le interazioni di particelle sono considerate “abbastanza vicine” a zero da essere ignorate in modo sicuro. Per ogni particella, viene costruita una lista di Verlet che elenca tutte le altre particelle all’interno della potenziale distanza di cut-off, più qualche distanza in più in modo che la lista possa essere utilizzata per diversi “sweep” Monte Carlo consecutivi (set di passi o mosse Monte Carlo) prima di essere aggiornata. Se si desidera utilizzare lo stesso Verlet elenco n {\displaystyle n} volte prima di aggiornare, quindi il cut-off a distanza per l’inclusione nella Verlet elenco deve essere R c + 2 n d {\displaystyle R{c}+2}
, dove R c {\displaystyle R{c}}
è il cut-off a distanza del potenziale, e d {\displaystyle d}
è il massimo Monte Carlo passaggio (spostare) di una singola particella. E così abbiamo pensato di spendere di ordine N 2 {\displaystyle N^{2}}
tempo, per calcolare la Verlet liste ( N {\displaystyle N}
è il numero totale di particelle), ma sono ricompensati con n {\displaystyle n}
Monte Carlo “spazza” di ordine N n 2 {\displaystyle Nn^{2}}
invece che N N {\displaystyle NN}
. Ottimizzando la nostra scelta di n {\displaystyle n}
può essere dimostrato che Verlet elenchi consentono di convertire i file O ( N 2 ) {\displaystyle O(N^{2})}
problema di Monte Carlo, che spazia da un O ( N 5 / 3 ) {\displaystyle O(N^{5/3})}
problema.
L’utilizzo di elenchi di celle per identificare i vicini più vicini in O ( N ) {\displaystyle O(N)} riduce ulteriormente il costo computazionale.