KBD_algorithm
「KBDアルゴリズム」
KBDアルゴリズムは、2次元の完全にフラストレーションのあるイジングモデル 、またはより一般的には、市松模様に配置されたフラストレーションのあるプラケットを備えた任意の2次元スピングラス用に設計されたクラスター更新アルゴリズムです。 1990年にDanielKandel、Radel Ben-Av、およびEytan Domanyによって発見され、1994年にPDCoddingtonおよびL.Hanによって一般化されました。これは量子モンテカルロシミュレーションで使用されるクラスターアルゴリズムのインスピレーションです。
コンテンツ
1 動機
2 アルゴリズム
3 トポロジー的特徴
4 参考文献
動機
SWアルゴリズムは、強磁性スピンモデルの効率的なシミュレーション用に設計された最初の非局所アルゴリズムです。しかし、基礎となるスピンシステムに対して生成されたクラスターの相関長が長すぎるため、アルゴリズムの効率をフラストレーションのあるシステムに拡張できないことがすぐにわかります。 KBDアルゴリズムは、結合形成規則を格子のプラケットに拡張する試みであり、生成されたクラスターはフラストレーションプロファイルによって通知され、SWのものよりも小さくなります。比較してより効率的なアルゴリズム。しかし、現段階では、このアルゴリズムを任意のスピングラスモデルに一般化できるかどうかは不明です。
アルゴリズム
まず、正方形の格子を市松模様に配置されたプラケットに分解します（プラケットは頂点方向にのみ重なり、エッジ方向には重なりません）。スピンモデルは完全にフラストレーションがたまっているため、各プラケットには正確に1つまたは3つの負の相互作用が含まれている必要がプラケットに3つの負の相互作用が含まれている場合、結合は形成されません。ただし、プラケットに1つの負の相互作用が含まれている場合、2つの平行な結合が（負のエッジに垂直に）形成される可能性がp = 1 − e −
4 β { p = 1-e ^ {-4 beta}}
、 どこ β { beta}
はスピンモデルの逆温度です。
次に、結合は格子上にクラスターを形成し、その上でスピンをまとめて反転させることができます（SWルールまたはWolffルールのいずれかを使用）。更新が詳細釣り合いを満たしていることを示すことができます。つまり、アルゴリズムをシングルスピンフリップ更新などのエルゴードアルゴリズムと組み合わせて使用すると、正確性が保証されます。
トポロジー的特徴
ゼロ温度で、またはβ ∞
{ beta to infty}
制限として、すべての血小板にはちょうど1つのネガティブエッジが含まれます。この場合、各市松模様のプラケットで、KBDアルゴリズムは常に負のエッジに垂直な2つの平行な結合を開きます。つまり、結合は負のエッジとその反対側のエッジで閉じられます。二重格子の閉じた結合を追跡する場合、閉じた結合と交差するように各プラケットの内側に直線/曲がった線を引くことにより、線に続くパスがサイクルを形成する必要があることを示すことができます。
さらに、そのようなサイクルが少なくとも2つ必要であり、サイクルが交差できないことを示すことができます。最も重要なことは、各サイクルは、格子が埋め込まれている下にある表面の点に収縮できないことです。周期的な格子（またはトーラス）では、これは、閉じた結合のサイクルがトーラスの周りに巻かなければならないことを意味します。同じ方向から、ゼロ温度での最大のクラスター（これらのサイクルの間に「圧迫」されなければならない）は、熱力学的極限の格子サイズの有限部分にまたがることができないことを示すことができます。
参考文献
^ カンデル、ダニエル; Ben-Av、Radel; ドマニー、エイタン（1990-08-20）。「完全にフラストレーションのあるシステムのクラスターダイナミクス」。物理的レビューレター。65（8）：941–944。Bibcode：1990PhRvL..65..941K。土井：10.1103/PhysRevLett.65.941。PMID10043065 。_ ^ ハムゼ、フィラス; ジェイコブ、ダリルC .; オチョア、アンドリューJ .; ペレラ、ディリーナ; 王、文龍; Katzgraber、Helmut G.（2018-04-13）。「近くから永遠へ：スピングラスの植え付け、タイリングパズル、制約充足問題」。フィジカルレビューE。97（4）：043303。arXiv：1711.04083。Bibcode：2018PhRvE..97d3303H。土井：10.1103/PhysRevE.97.043303。PMID29758754。_ ^ Coddington、PD; ハン、L。（1994-08-01）。「フラストレーションのあるスピンモデルの一般化されたクラスターアルゴリズム」。フィジカルレビューB。50（5）：3058–3067。arXiv：cond-mat/9402030。Bibcode：1994PhRvB..50.3058C。土井：10.1103/PhysRevB.50.3058。PMID9976551。_ S2CID939709。_ ^ Swendsen、Robert H .; 王、Jian-Sheng（1987-01-12）。「モンテカルロシミュレーションにおける非普遍的な臨界ダイナミクス」。物理的レビューレター。58（2）：86–88。Bibcode：1987PhRvL..58…86S。土井：10.1103/PhysRevLett.58.86。PMID10034599。_ ^ Cataudella、V.（1992-05-01）。「フラストレーションのあるシステムにおけるパーコレーション遷移」。Physica A：統計力学とその応用。183（3）：249–254。Bibcode：1992PhyA..183..249C。土井：10.1016 / 0378-4371（92）90145-G。ISSN0378-4371。_ ^ カンデル、ダニエル; Ben-Av、Radel; ドマニー、エイタン（1992-03-01）。「完全に欲求不満のイジングモデルのクラスターモンテカルロダイナミクス」。フィジカルレビューB。45（9）：4700–4709。Bibcode：1992PhRvB..45.4700K。土井：10.1103/PhysRevB.45.4700。PMID10002105。_ “