Dynamic connectivity algorithms for Monte Carlo simulations of the random-cluster model

25th IUPAP Conference on Computational Physics

物理学;计算机科学

Elçi, Eren Metin^1,2 ; Weigel, Martin^1,2

Appl. Math. Res. Ctr., Coventry Univ., Coventry, CV1 5FB, United Kingdom^1

Inst. F. Physik, Johannes Gutenberg-Univ. Mainz, Staudinger Weg 7, D-55099 Mainz, Germany^2

关键词: Computational effort;    Connectivity algorithms;    Connectivity information;    Critical slowing down;    Droplet shape;    Edge operation;    Random-cluster model;    System size;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/510/1/012013/pdf
DOI  :  10.1088/1742-6596/510/1/012013

学科分类：计算机科学（综合）

来源: IOP

【 摘 要 】

We review Sweeny's algorithm for Monte Carlo simulations of the random cluster model. Straightforward implementations suffer from the problem of computational critical slowing down, where the computational effort per edge operation scales with a power of the system size. By using a tailored dynamic connectivity algorithm we are able to perform all operations with a poly-logarithmic computational effort. This approach is shown to be efficient in keeping online connectivity information and is of use for a number of applications also beyond cluster-update simulations, for instance in monitoring droplet shape transitions. As the handling of the relevant data structures is non-trivial, we provide a Python module with a full implementation for future reference.