ベルレ・リスト(英: Verlet list)は、任意のカットオフ(打ち切り)相互距離内の全ての粒子のリストを効率的に維持するための分子動力学シミュレーションにおけるデータ構造である[1]。名称はルー・ベルレ(英語版)に因む。
この方法はモンテカルロシミュレーションに容易に応用できる。短距離相互作用については、カットオフ半径が大抵使われる。カットオフ半径を超えると粒子の相互作用はゼロに「十分近い」と見なされ安全に無視される。個々の粒子について、ベルレ・リストが構築される。これにはポテンシャルカットオフ距離内のその他の全ての粒子が記載され、さらに更新される前に複数の連続したモンテカルロ「スイープ」に使用できるようにいくらか余分な距離を含む。更新の前に同じベルレ・リストをn回使用したい場合は、ベルレ・リストに含めるカットオフ距離は R c + 2 n d {\displaystyle R_{c}+2nd} ( R c {\displaystyle R_{c}} はポテンシャルのカットオフ距離、 d {\displaystyle d} は単一粒子の最大モンテカルロステップ)でなければならない。ゆえに、ベルレ・リストを計算するためには N 2 {\displaystyle N^{2}} オーダーの時間を費すが( N {\displaystyle N} は粒子の総数)、( N N {\displaystyle NN} ではなく) N n 2 {\displaystyle Nn^{2}} オーダーの n {\displaystyle n} モンテカルロ「スイープ」という見返りが得られる。 n {\displaystyle n} の選択を最適化することで、ベルレ・リストを用いることによってモンテカルロスイープの O ( N 2 ) {\displaystyle O(N^{2})} 問題を O ( N 5 / 3 ) {\displaystyle O(N^{5/3})} へ変換できることが示されている。
O ( N ) {\displaystyle O(N)} における最近傍を同定するためにセル・リスト(英語版)用いると、さらに計算コストを削減できる。