スヴェンセン・ワンのアルゴリズム

スヴェンセン・ワンのアルゴリズム (Swendsen–Wang algorithm) は、イジング模型のモンテカルロシミュレーション用のアルゴリズムの一つで、サイト全体を同一スピンのクラスターに分割し、クラスターそれぞれに新たなスピンを割り当てるアルゴリズムである。ウォルフのアルゴリズムも参照。

このアルゴリズムは、一回の状態変化において広域にわたる変化を実行するアルゴリズムとしては初期の物である。もともとのアルゴリズムはイジング模型とポッツ模型用であったが、後に一般化され、ウォルフのアルゴリズムによるXY模型や流体粒子など、他の系にも用いられるようになった。この手法のカギは、Fortuin^{[訳語疑問点]}と Kasteleyn^{[訳語疑問点]} に帰せられるイジング模型やポッツ模型を結合のパーコレーションでモデル化する方法である。結合されたサイトはクラスターを形成する。等しいスピンを持つサイト同士は次に示す確率で結合される。

$P = 1 - exp(-2 J /(k B T))$

ここで、 $J$ は強磁性イジング模型におけるカップリング定数、 $T$ は温度、 $k B$ はボルツマン定数である。クラスターは同じ確率で「反転」される。この手法は二次相転移点付近において臨界減速を克服でき、最も効率がよい手法である。

Barbu & Zhu 2005で一般化がなされ、任意のサンプリング確率分布の場合にも提案されたモンテカルロ遷移の採択確率を計算することができるようになり、メトロポリス・ヘイスティングス法を実行できるようになった。

出典

Swendsen, Robert H.; Wang, Jian-Sheng (1987年1月). “Nonuniversal critical dynamics in Monte Carlo simulations”. Phys. Rev. Lett. 58 (2): 86–88. doi:10.1103/PhysRevLett.58.86.
Kasteleyn, P. W.; Fortuin (1969). J. Phys. Soc. Jpn. Suppl. 26: 11.
- Fortuin, C.M.; Kasteleyn, P.W. (1972). “On the random-cluster model: I. Introduction and relation to other models”. Physica 57 (4): 536–564. doi:10.1016/0031-8914(72)90045-6. ISSN 0031-8914.
Wang, Jian-Sheng; Swendsen, Robert H. (1990). “Cluster Monte Carlo algorithms”. Physica A: Statistical Mechanics and its Applications 167 (3): 565–579. doi:10.1016/0378-4371(90)90275-W. ISSN 0378-4371.
Barbu, Adrian; Zhu, Song-Chun (2005). “Generalizing Swendsen-Wang to Sampling Arbitrary Posterior Probabilities”. IEEE Transactions on Pattern Analysis and Machine Intelligence 27 (8): 1239–1253. doi:10.1109/TPAMI.2005.161. ISSN 0162-8828.

外部リンク