Списки ячеек

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

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

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

для всех соседних пар клеток делают${\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 }]\|_{2}^{2}}$

если тогда${\displaystyle r^{2}\leq r_{c}^{2}}$

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

конец, если

конец для

конец для

конец для

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

При моделировании с частицами с однородной плотностью частиц количество ячеек пропорционально и обратно пропорционально радиусу отсечения (т. е. если увеличивается, то увеличивается и количество ячеек). Следовательно, среднее количество частиц на ячейку не зависит от общего количества частиц. Стоимость взаимодействия двух ячеек составляет . Количество пар ячеек пропорционально количеству ячеек, которое, в свою очередь, пропорционально количеству частиц . Общая стоимость нахождения всех попарных расстояний в пределах заданного отсечения составляет , что значительно лучше, чем наивное вычисление попарных расстояний.${\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})}$

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

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

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

Вместо создания фантомных ячеек, пары ячеек, которые взаимодействуют через периодическую границу, могут также использовать периодический вектор коррекции . Этот вектор, который может быть сохранен или вычислен для каждой пары ячеек , содержит коррекцию, которую необходимо применить для «обертывания» одной ячейки вокруг домена, чтобы она соседствовала с другой. Попарное расстояние между двумя частицами и затем вычисляется как${\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}}$.

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

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

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

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

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

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