スウェンセン・ワングアルゴリズム

スウェンセン・ワングアルゴリズムは、臨界点に近い大規模システムのモンテカルロシミュレーションのための最初の非局所的またはクラスターアルゴリズムです。1987年にカーネギーメロン大学のロバート・スウェンセンとジャンシェン・ワンによって導入されました。

元のアルゴリズムはイジングモデルとポッツモデル用に設計され、後にウルフアルゴリズムによるXYモデルや流体粒子など他のシステムにも一般化されました。重要な要素はランダムクラスターモデルで、フォーチュインとカステリンによる、接続結合の浸透モデルによるイジングモデルまたはポッツモデルの表現です。これは、BarbuとZhu ^{[1]によって、}メトロポリス-ヘイスティングスアルゴリズムとして捉え、提案されたモンテカルロ法の受理確率を計算することで、任意のサンプリング確率に一般化されました。

局所的過程に影響を及ぼす臨界減速の問題は、2 次相転移（イジング模型における強磁性転移など）の研究において根本的に重要です。これは、有限サイズ効果を低減するためにシステムのサイズを大きくすると、熱平衡に達するまでに非常に多くの移動が必要になるという欠点があるためです。実際、相関時間は通常、またはそれ以上に増加します。正確には、シミュレーション時間は でなければならないため、これは局所的アルゴリズムで研究できるシステムのサイズに関する大きな制限となります。SW アルゴリズムは、動的臨界指数に異常に小さな値を生成した最初のアルゴリズムです。2Dイジング模型では（標準シミュレーションの場合）、3D イジング模型では、標準シミュレーションの場合とは対照的に、非常に小さな値を生成しました。 ${\displaystyle \tau}$${\displaystyle L^{z}}$${\displaystyle z\simeq 2}$${\displaystyle t\gg \tau}$${\displaystyle z=0.35}$${\displaystyle z=2.125}$${\displaystyle z=0.75}$${\displaystyle z=2.0}$

このアルゴリズムは、単一のスイープでFortuin–Kasteleyn 表現に基づいてスピン変数のコレクションを更新するという意味で非局所的です。更新は、スピンの相互作用状態に基づいて、 パーコレーションプロセスを通じて生成されるオープン結合変数によって接続されたスピン変数の「クラスター」に対して行われます。

最近接相互作用のみを持つ典型的な強磁性イジングモデルを考えてみましょう。

• 与えられたスピン構成から始めて、サイト上の最も近い隣接スピンの各ペアに、次のように解釈されるランダム変数を関連付けます。の場合、サイトとスピンの間にリンクはありません(結合は閉じています )。 の場合、スピンを接続するリンクがあります(結合は開いています)。 これらの値は、次の (条件付き) 確率分布に従って割り当てられます。${\displaystyle n,m}$${\displaystyle b_{n,m}\in \lbrace 0,1\rbrace }$${\displaystyle b_{n,m}=0}$${\displaystyle n}$${\displaystyle m}$${\displaystyle b_{n,m}=1}$${\displaystyle \sigma _{n}{\text{ と }}\sigma _{m}}$

 ${\displaystyle P\left[b_{n,m}=0|\sigma _{n}\neq \sigma _{m}\right]=1}$;
  ;
  ;
  ;
${\displaystyle P\left[b_{n,m}=1|\sigma _{n}\neq \sigma _{m}\right]=0}$${\displaystyle P\left[b_{n,m}=0|\sigma _{n}=\sigma _{m}\right]=e^{-2\beta J_{nm}}}$${\displaystyle P\left[b_{n,m}=1|\sigma _{n}=\sigma _{m}\right]=1-e^{-2\beta J_{nm}}}$

ここで、強磁性結合の強度です。 ${\displaystyle J_{nm}>0}$

この確率分布は次のように導出された。イジングモデルのハミルトニアンは

${\displaystyle H[\sigma ]=\sum \limits _{<i,j>}-J_{i,j}\sigma _{i}\sigma _{j}}$、

そして、分配関数は

${\displaystyle Z=\sum \limits _{\lbrace \sigma \rbrace }e^{-\beta H[\sigma ]}}$。

選択されたサイトと間の相互作用を考えて、それを全ハミルトニアンから除去し、定義する。 ${\displaystyle n}$${\displaystyle m}$${\displaystyle H_{nm}[\sigma ]=\sum \limits _{<i,j>\neq <n,m>}-J_{i,j}\sigma _{i}\sigma _{j}.}$

制限された合計も定義します。

${\displaystyle Z_{n,m}^{same}=\sum \limits _{\lbrace \sigma \rbrace }e^{-\beta H_{nm}[\sigma ]}\delta _{\sigma _{n},\sigma _{m}}}$;

${\displaystyle Z_{n,m}^{diff}=\sum \limits _{\lbrace \sigma \rbrace }e^{-\beta H_{nm}[\sigma ]}\left(1-\delta _{\sigma _{n},\sigma _{m}}\right).}$

${\displaystyle Z=e^{\beta J_{nm}}Z_{n,m}^{same}+e^{-\beta J_{nm}}Z_{n,m}^{diff}.}$

数量を紹介する

${\displaystyle Z_{nm}^{ind}=Z_{n,m}^{same}+Z_{n,m}^{diff}}$;

分割関数は次のように書き直すことができる。

${\displaystyle Z=\left(e^{\beta J_{nm}}-e^{-\beta J_{nm}}\right)Z_{n,m}^{same}+e^{-\beta J_{nm}}Z_{n,m}^{ind}.}$

最初の項にはスピン値に対する制限が含まれていますが、2 番目の項には制限がないため、重み付け係数 (適切に正規化) は、サイト間のリンクが形成される/形成されない確率として解釈できます。このプロセスは、反強磁性スピン システムに簡単に適応できます。これは、(相互作用定数の符号の変化によって示唆されるように)を優先して を除去するだけで十分であるためです。 ${\displaystyle P_{<n,m>\;link}=1-e^{-2\beta J_{nm}}.}$${\displaystyle Z_{n,m}^{same}}$${\displaystyle Z_{n,m}^{diff}}$

• 結合変数を割り当てた後、接続されたサイトによって形成された同じスピンのクラスターを識別し、クラスター内のすべての変数を確率 1/2 で反転します。次のタイム ステップでは、新しい開始イジング構成が得られ、新しいクラスタリングと新しい集合スピン反転が生成されます。

このアルゴリズムは平衡構成につながることが示せます。これを示すために、アルゴリズムをマルコフ連鎖として解釈し、連鎖がエルゴード的であり（他のアルゴリズムと一緒に使用した場合）、詳細なバランスを満たし、平衡ボルツマン分布が連鎖の 定常分布に等しいことを示します。

エルゴード性とは、有限回数の更新で任意の初期状態から任意の最終状態に遷移できることを意味します。SWアルゴリズムは一般にエルゴードではないことが示されています（熱力学的限界において）。^[2]そのため、実際には、SWアルゴリズムは通常、メトロポリス-ヘイスティングスアルゴリズムなどの単一のスピンフリップアルゴリズムと組み合わせて使用​​され、エルゴード性を実現します。

しかし、SWアルゴリズムは詳細バランスを満たしています。これを示すために、2つのイジングスピン状態間のすべての遷移は、パーコレーション表現の何らかの結合構成を通過する必要があることに注意します。特定の結合構成を固定しましょう。それに関連する確率を比較する際に重要なのは、同じ値を持つ隣接するスピン間の失われた結合の因子の数です。特定の結合構成と互換性のある特定のイジング構成に移行する確率は均一です（とします）。したがって、ある状態から別の状態に移行する遷移確率の比は ${\displaystyle q=e^{-2\beta J}}$${\displaystyle p}$

${\displaystyle {\frac {P_{\lbrace \sigma \rbrace \rightarrow \lbrace \sigma '\rbrace }}{P_{\lbrace \sigma '\rbrace \rightarrow \lbrace \sigma \rbrace }}}={\frac {Pr\left(\lbrace \sigma '\rbrace |B.C.\right)Pr\left(B.C.|\lbrace \sigma \rbrace \right)}{Pr\left(\lbrace \sigma \rbrace |B.C.\right)Pr\left(B.C.|\lbrace \sigma '\rbrace \right)}}={\frac {p\cdot \exp \left[-2\beta \sum \limits _{<l,m>}\delta _{\sigma _{l},\sigma _{m}}J_{lm}\right]}{p\cdot \exp \left[-2\beta \sum \limits _{<l,m>}\delta _{\sigma '_{l},\sigma '_{m}}J_{lm}\right]}}=e^{-\beta \Delta E}}$

以来。 ${\displaystyle \Delta E=-\sum \limits _{<l,m>}J_{lm}\left(\sigma '_{l}\sigma '_{m}-\sigma _{l}\sigma _{m}\right)=-\sum \limits _{<l,m>}J_{lm}\left[\delta _{\sigma '_{l},\sigma '_{m}}-\left(1-\delta _{\sigma '_{l},\sigma '_{m}}\right)-\delta _{\sigma _{l},\sigma _{m}}+\left(1-\delta _{\sigma _{l},\sigma _{m}}\right)\right]=-2\sum \limits _{<l,m>}J_{lm}\left(\delta _{\sigma '_{l},\sigma '_{m}}-\delta _{\sigma _{l},\sigma _{m}}\right)}$

これは、システムが進化の過程で通過する可能性のあるすべての結合構成に有効であるため、全体の遷移確率について詳細なバランスが満たされます。これにより、アルゴリズムが正しいことが証明されます。

原著論文からは解析的に明らかではないが、SWアルゴリズムで得られたzの値がすべて、シングルスピンフリップアルゴリズムの正確な下限値（）よりもはるかに低い理由は、相関長の発散が、一緒に反転するパーコレーションクラスターの形成に厳密に関連しているためである。このようにして、緩和時間が大幅に短縮されます。これを別の方法で見るには、エドワーズ-ソーカル表現におけるスピン統計とクラスター統計間の対応を通して見る。^[3]このプロセスの混合時間に関するいくつかの数学的に厳密な結果は、GuoとJerrumによって得られている[1]。 ${\displaystyle z\geq \gamma /\nu }$

このアルゴリズムは、フラストレーションのあるシステムをシミュレートするのに効率的ではありません。なぜなら、フラストレーションのある相互作用がある場合、クラスターの相関長はスピンモデルの相関長よりも大きいからです。 ^[4]現在、この問題に対処するための2つの主なアプローチがあり、クラスターアルゴリズムの効率がフラストレーションのあるシステムに拡張されています。

最初のアプローチは、結合形成ルールをより多くの非局所的なセルに拡張することであり、2番目のアプローチは、より関連性の高い秩序パラメータに基づいてクラスターを生成することです。最初のケースでは、完全にフラストレートしたイジングモデルのKBDアルゴリズムがあり、結合を開く決定は、正方格子上にチェッカーボードパターンで配置された各プラケットで行われます。^[5] 2番目のケースでは、低次元スピングラスのレプリカクラスター移動があり、クラスターは、関連する秩序パラメータであると考えられているスピンオーバーラップに基づいて生成されます。

• ランダムクラスターモデル
• モンテカルロ法
• ウォルフアルゴリズム
• http://www.hpjava.org/theses/shko/thesis_paper/node69.html
• http://www-fcs.acs.i.kyoto-u.ac.jp/~harada/monte-ja.html

• Swendsen, Robert H.; Wang, Jian-Sheng (1987-01-12). 「モンテカルロシミュレーションにおける非普遍的臨界ダイナミクス」. Physical Review Letters . 58 (2). American Physical Society (APS): 86–88. Bibcode :1987PhRvL..58...86S. doi :10.1103/physrevlett.58.86. ISSN  0031-9007. PMID  10034599.
• Kasteleyn PW と Fortuin (1969) J. Phys. Soc. Jpn. Suppl. 26s:11
• Fortuin, CM; Kasteleyn, PW (1972). 「ランダムクラスターモデルについて」. Physica . 57 (4). Elsevier BV: 536–564. Bibcode :1972Phy....57..536F. doi :10.1016/0031-8914(72)90045-6. ISSN  0031-8914.
• Wang, Jian-Sheng; Swendsen, Robert H. (1990). 「クラスターモンテカルロアルゴリズム」. Physica A: 統計力学とその応用. 167 (3). Elsevier BV: 565–579. Bibcode :1990PhyA..167..565W. doi :10.1016/0378-4371(90)90275-w. ISSN  0378-4371.
• Barbu, A. (2005). 「Swendsen-Wang 法の一般化による任意の事後確率のサンプリング」. IEEE Transactions on Pattern Analysis and Machine Intelligence . 27 (8). Institute of Electrical and Electronics Engineers (IEEE): 1239–1253. doi :10.1109/tpami.2005.161. ISSN  0162-8828. PMID  16119263. S2CID  410716.