Списки ячеек

Списки ячеек (также иногда называемые списками ячеек ) — это структуры данных в молекулярно-динамическом моделировании, предназначенные для поиска всех пар атомов в пределах заданного предельного расстояния друг от друга. Эти пары необходимы для расчета короткодействующих несвязанных взаимодействий в системе, таких как силы Ван-дер-Ваальса или ближнедействующей части электростатического взаимодействия при использовании суммирования Эвальда .

Алгоритм

Парные взаимодействия для одной частицы можно вычислить, а) вычислив взаимодействие со всеми другими частицами или б) разделив область на ячейки с длиной ребра, по крайней мере, радиусом отсечки потенциала взаимодействия и вычислив взаимодействие между частица и все частицы в той же (красной) и соседних (зеленых) ячейках.

Списки ячеек подразделяют область моделирования на ячейки с длиной ребра, большей или равной радиусу отсечки вычисляемого взаимодействия. Частицы сортируются по этим ячейкам, и взаимодействия вычисляются между частицами в одной и той же или соседних ячейках.

В своей самой базовой форме несвязанные взаимодействия на предельном расстоянии $r_{c}$ рассчитываются следующим образом:

для всех соседних пар ячеек $(C_{\alpha },C_{\beta })$ делать

для всех $p_{\alpha }\in C_{\alpha }$ делать

для всех $p_{\beta }\in C_{\beta }$ делать

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

если $r^{2}\leq r_{c}^{2}$ затем

Вычислить взаимодействие между $p_{\alpha }$ и $p_{\beta }$.

конец, если

конец для

конец для

конец для

Поскольку длина ячейки не менее $r_{c}$ во всех измерениях, внутри нет частиц $r_{c}$ друг друга можно пропустить.

Учитывая симуляцию с $N$ частицы с однородной плотностью частиц, числом ячеек $m$ пропорционально $N$ и обратно пропорциональна радиусу среза (т.е. если $N$ увеличивается, увеличивается и количество клеток). Среднее количество частиц на ячейку ${\overline {c}}=N/m$ поэтому не зависит от общего числа частиц. Стоимость взаимодействия двух ячеек находится в ${\mathcal {O}}({\overline {c}}^{2})$. Количество пар ячеек пропорционально количеству ячеек, которое снова пропорционально количеству частиц. $N$. Общая стоимость поиска всех парных расстояний в пределах заданного отсечения равна ${\mathcal {O}}(Nc)\in {\mathcal {O}}(N)$, что значительно лучше, чем вычисление ${\mathcal {O}}(N^{2})$ попарно расстояния наивно.

Периодические граничные условия

В большинстве симуляций периодические граничные условия используются, чтобы избежать наложения искусственных граничных условий. Используя списки ячеек, эти границы можно реализовать двумя способами.

Клетки-призраки

Периодические граничные условия можно смоделировать, обернув блок моделирования дополнительным слоем ячеек (закрашен оранжевым), содержащим периодические копии граничных ячеек (синие частицы).

В подходе с призрачными ячейками блок моделирования оборачивается дополнительным слоем ячеек. Эти ячейки содержат периодически упакованные копии соответствующих ячеек моделирования внутри домена.

Хотя данные (а также, как правило, вычислительные затраты) удваиваются для взаимодействий через периодическую границу, этот подход имеет то преимущество, что его легко реализовать и очень легко распараллелить, поскольку ячейки будут взаимодействовать только со своими географическими соседями.

Периодическая упаковка

Вместо создания призрачных ячеек пары ячеек, которые взаимодействуют через периодическую границу, также могут использовать вектор периодической коррекции. $\mathbf {q} _{\alpha \beta }$. Этот вектор, который можно сохранить или вычислить для каждой пары ячеек. $(C_{\alpha },C_{\beta })$, содержит поправку, которую необходимо применить, чтобы «обернуть» одну ячейку вокруг домена так, чтобы она соседствовала с другой. Попарное расстояние между двумя частицами $p_{\alpha }\in C_{\alpha }$ и $p_{\beta }\in C_{\beta }$ затем вычисляется как

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

Этот подход, хотя и более эффективен, чем использование ячеек-фантомов, менее прост в реализации (пары ячеек необходимо идентифицировать по периодическим границам, а вектор $\mathbf {q} _{\alpha \beta }$ необходимо вычислить/сохранить).

Улучшения

Несмотря на сокращение вычислительных затрат на поиск всех пар в пределах заданного расстояния от ${\mathcal {O}}(N^{2})$ к ${\mathcal {O}}(N)$, алгоритм списка ячеек, указанный выше, все еще имеет некоторую неэффективность.

Рассмотрим расчетную ячейку в трех измерениях с длиной ребра, равной радиусу среза. $r_{c}$. Вычисляется попарное расстояние между всеми частицами в ячейке и в одной из соседних ячеек. У ячейки 26 соседей: 6 имеют общую грань, 12 имеют общий край и 8 имеют общий угол. Из всех вычисленных парных расстояний только около 16% на самом деле будут меньше или равны $r_{c}$. Другими словами, 84% всех вычислений парных расстояний являются ложными.

Один из способов преодоления этой неэффективности — разбить область на ячейки с длиной ребра меньше $r_{c}$. Тогда парные взаимодействия вычисляются не только между соседними ячейками, но и между всеми ячейками внутри. $r_{c}$ друг друга (впервые предложено в и реализованы и проанализированы в и ). Этот подход может быть доведен до предела, когда каждая ячейка содержит не более одной частицы, что снижает количество ложных оценок парных расстояний до нуля. Однако этот выигрыш в эффективности быстро компенсируется количеством ячеек. $C_{\beta }$ которые необходимо проверять при каждом взаимодействии с клеткой $C_{\alpha }$, который, например, в трех измерениях, растет кубически пропорционально длине ребра ячейки. Установка длины края $r_{c}/2$, однако уже снижает количество ложных оценок расстояния до 63%.

Другой подход изложен и протестирован в Гонне, при котором частицы сначала сортируются вдоль оси, соединяющей центры ячеек. Этот подход генерирует только около 40% ложных вычислений парных расстояний, но требует дополнительных затрат из-за сортировки частиц.

См. также

• Список Верле