セルリスト

セル リスト(セル リンク リストとも呼ばれる) は、分子動力学シミュレーションにおいて、互いに指定されたカットオフ距離内にあるすべての原子ペアを見つけるためのデータ構造です。これらのペアは、ファンデルワールス力や、エワルド和を使用する場合の静電相互作用の短距離部分など、システム内の短距離の非結合相互作用を計算するために必要です。

セル リストは、計算する相互作用のカットオフ半径以上のエッジ長を持つセルにシミュレーション領域を分割することによって機能します。粒子はこれらのセルに分類され、同じセルまたは隣接するセル内の粒子間の相互作用が計算されます。

最も基本的な形式では、カットオフ距離の非結合相互作用は次のように計算されます。 ${\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}}$

均一な粒子密度を持つ粒子のシミュレーションでは、セルの数はカットオフ半径に比例し、反比例します (つまり、 が増加すると、セルの数も増加します)。したがって、セルあたりの平均粒子数は、粒子の総数に依存しません。2 つのセルを相互作用させるコストは です。セル ペアの数はセルの数に比例し、セルの数も粒子の数に比例します。特定のカットオフ内のすべてのペアワイズ距離を見つけるための総コストは で、これはペアワイズ距離を単純に計算するよりも大幅に優れています。 ${\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})}$

ほとんどのシミュレーションでは、人工的な境界条件を課すことを避けるために周期境界条件が使用されます。セル リストを使用すると、これらの境界を 2 つの方法で実装できます。

ゴースト セル アプローチでは、シミュレーション ボックスが追加のセル レイヤーでラップされます。これらのセルには、ドメイン内の対応するシミュレーション セルの定期的にラップされたコピーが含まれます。

周期境界を越えた相互作用ではデータ (および通常は計算コスト) が 2 倍になりますが、セルは地理的に隣接するセルとのみ相互作用するため、このアプローチには実装が簡単で並列化が非常に簡単であるという利点があります。

ゴーストセルを作成する代わりに、周期境界を越えて相互作用するセルペアは、周期補正ベクトルを使用することもできます。このベクトルは、すべてのセルペアに対して保存または計算することができ、1つのセルをドメインの周囲に「ラップ」して他のセルに隣接させるために必要な補正を含みます。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)}$

辺の長さがカットオフ半径 に等しい 3 次元の計算セルを考えてみましょう。セル内のすべての粒子と隣接するセルの 1 つにある粒子間のペ​​アワイズ距離が計算されます。セルには 26 個の隣接粒子があり、そのうち 6 個は共通の面を共有し、12 個は共通の辺を共有し、8 個は共通の角を共有しています。計算されたすべてのペアワイズ距離のうち、実際に 未満か に​​等しいのは約 16% だけです。言い換えると、すべてのペアワイズ距離計算の 84% は誤ったものです。 ${\displaystyle r_{c}}$${\displaystyle r_{c}}$

この非効率性を克服する 1 つの方法は、領域を より小さい辺の長さのセルに分割することです。これにより、ペアワイズ相互作用は、隣接するセル間だけでなく、 内のすべてのセル間で計算されます (最初に^{[1]で提案され、 [2] [3]}および^[4]で実装および分析されました)。このアプローチは、各セルが最大で 1 つの粒子しか保持しないという極限まで適用できるため、誤ったペアワイズ距離評価の回数がゼロになります。ただし、この効率性の向上は、セル との相互作用ごとに検査する必要があるセルの数によってすぐに相殺されます。このセルの数は、たとえば 3 次元では、セルの辺の長さの逆数で 3 乗に増加します。ただし、辺の長さを に設定すると、誤った距離評価の回数が 63% に減少します。 ${\displaystyle r_{c}}$${\displaystyle r_{c}}$${\displaystyle C_{\beta }}$${\displaystyle C_{\alpha }}$${\displaystyle r_{c}/2}$

^{Gonnet [5]}では別のアプローチが概説され、テストされています。このアプローチでは、まず粒子がセルの中心を結ぶ軸に沿ってソートされます。このアプローチでは、約 40% の誤ったペアワイズ距離計算しか生成されませんが、粒子をソートするため追加のコストがかかります。

• ヴェルレリスト