WikiDer > Списки ячеек

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

Алгоритм

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

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

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

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

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

для всех ${displaystyle p_ {eta} на C_ {eta}}$ делать

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

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

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

конец, если

конец для

конец для

конец для

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

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

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

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

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

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

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

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

Периодическое обертывание

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

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

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

Улучшения

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

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

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

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

Смотрите также

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

Рекомендации