DL1

Directed Loop I

写在前面：本文是我最近想要写XXZ+hz+hx Model的思考，顺带着复习、回顾DL. 大量参考了Syljuåsen, O. F. 关于DL的两篇文章，即2003年的The Directed‐Loop Algorithm和2003年的Directed loop updates for quantum lattice models. 其中第一篇可以看作是他和Sandvik合作的DL原文献的简略版.

Intro

这里简单概述一下DL从何而来，以及为什么需要用到DL.

环算法(Loop algorithms)在世界线(world-line)量子蒙特卡罗计算中的应用及其在解决特定问题上的局限性。首先，环算法显著提高了世界线量子蒙特卡罗计算的性能，可以将自相关时间减少几个数量级，但传统环更新(conventional loop updates)受限于特定模型和参数空间. 特别是，在构建环的时候无法考虑外部场，并且环的翻转取决于Metropolis接受/拒绝步骤。在高场下，大环的接受概率很小，因此此方法仅在高温或非常弱的场下可行。[^ 1]

• Loop algorithm目前有许多限制，依赖于具体的模型和模型的参数，在低温或者强场的情况下发挥不好.

最近的蠕虫算法(worm algorithm)和SSE算符-环算法(operator-loop algorithm for stochastic series expansion (SSE))的泛化克服了这个问题，允许环自相交(selfintersect)(我也不太知道这个翻译准不准)和回溯(backtrack)，从而考虑了复杂的相互作用和外部场。

SSE的早期应用中，local off-diagonal updates涉及同时将两个算符进行替换, 即$[1,b(p)][1,b(p’)] \longleftrightarrow [2,b(p)][2,b(p’)]$. 现在有DL，通过局域细致平衡条件，导致了始终接受的封闭loop的有效配置. [^ 2]

有向环(DL)可以看作是由 vertex类型+DL方程+loop构建方式 组成.

在有向环(DL)方案中，细致平衡条件导致了一组耦合的方程，用于描述各种构建loop（或蠕虫）步骤的概率。这些有向环方程通常有无穷多解，因此需要进行优化。有向循环算法最初是为SSE（Stochastic Series Expansion）开发的，但在同一篇文章中也介绍了对离散和连续虚时间中的世界线的适应性。

• 对于给定的$S=1/2$海森堡模型的SSE算法. 选择合适的参数使得对角算符只作用于自旋相反的算符，令另外两种vertex权重为零. loop路过两次的算符将保持不变。由于所有bond算符的非零矩阵元都等于1/2，新配置的权重与旧配置完全相同，因此loop flip总是可以接受的。这种类型的环是通过构建而避免自交(self-avoiding)的（环不能有相交）。因此，配置也可以被分解为它的所有环（每个自旋属于恰好一个环），它们以1/2的概率独立于彼此翻转，就像经典的Swendsen-Wang算法. 但这种确定的loop明显依赖于$\Delta = 1,h=0$. 证明DL其实是比SSE更普适的算法

• 想象DL loop的构建可以想象这些vertex通过vertexlist连接，因为虚时间上自旋的“线”的信息是冗余的

• 这个不连续性不是在于起点翻不翻的vertex类型允许不允许，而是在于（起点和终点）这些腿现在将链接到具有不同自旋的腿。[^ 3] 换句话说，就是一个配置，如果某个格点在虚时间上的自旋不满足周期性边界条件，这样的配置是不被允许，不对配分函数产生贡献的

DL方程构建方式如下：首先，为通过vertex的所有可能路径分配未知权重$a$。所有这些路径权重在所有出口上（同一个入口）的总和必须等于裸vertex权重.[^ 4] 关键点还在于，**局部细致平衡(local detailed balance)**，要求构成彼此相反的vertex路径的权重必须相等，即，如果通过vertex k的路径i → e在翻转入口和出口自旋后导致vertex k’，那么通过k’的反向路径e → i会产生vertex k且路径权重相等[^ 5]

目前没有找到寻找最优解的严格方法，但已提出一些启发式的论点：合理的假设是，反弹过程的概率应该最小化，因为它们不完成任何vertex变化，并导致环构建过程回溯一步（有时在环构建过程中方向相反时回溯一步以上）。

然而，DL的方程组实际上是给提供了追求无反弹（或者最优解）的数学框架，追求无反弹或者反弹很少的解，在于追求算法的自关联时间更少. 对于某些模型，最小化反弹的解反而可能不是最优策略.[^ 6] 因此，vertex和各路径权重拿到手之后，首要做的事也许不是思考怎么列方程，而是如何设计算符、如何构造一个loop，How to start? How to end?.

---

Loop 的构建过程

link-discontinuities 链接不连续性

改变入口腿或退出腿的状态，或者同时改变两者，将导致一个或两个“链接不连续性”，即属于同一链接的不同腿上的状态不同。具有链接不连续性的配置不会对分区函数产生贡献，因此必须重复该过程，直到配置不再存在链接不连续性。

为了不引入更多的链接不连续性，下一个vertex入口腿的自旋状态受限于与之前退出腿的自旋状态相同，因此，前一个退出腿和当前入口腿之间的链接不连续性得以消除，然而，新退出腿的状态更改将引入新的链接不连续性，因此链接不连续性相当于是在路径前移动。

• 出口腿自旋状态与下一个vertex的入口腿状态相同，且出口腿自旋翻转时，下一个vertex的入口腿自旋必须翻转
• 不连续性不能产生于路径中间，路径中途没有不连续性

因此，在 Syljuåsen, O. F. (2003) 这篇文章中提到，若是出口腿没有翻转，那么下一个vertex入口腿也就不用翻转[^ 7]

当没有这样的守恒定律[^ 7]时，只因为尽管入口腿状态已经改变，退出腿状态没有改变时，一个链接不连续性可以消失，然后，如果在此步骤之前只有一个链接不连续性存在，可以终止该路径。这可以通过要求初始入口腿上没有链接不连续性来实现[^ 8][^ 9].

由于文献中提了一嘴“要求入口腿没有链接不连续性”，我们这里就顺便讲一下Henelius, P. 2002这篇文章

横场导致的非守恒定律. ——以 Henelius, P. 2002 这篇文章为例

现在可以有只翻转一个自旋的更新方式，要么是出口腿要么是入口腿. 注意到在上段中提到了“终止”的说法，显然这并不是单格点算符的特权.

单个翻转顶点的引入或去除会改变链接不连续性的数量，如果选择以与无横场的方式相同的方式启动和结束循环，则循环可以在未纠正初始不连续性的情况下关闭（若终止腿无不连续性则闭合后无法和初始的不连续性湮灭，独留一个初始的不连续性）. 因此，Henelius, P. 继续设定，起点是不翻转的，这样开始一个loop。

其后果就是，若起点是以不翻转开始的，那么出口在翻或不翻的选择下，选到翻，这个不连续性经由下一个vertex的入口处必须翻转，这样的话该不连续性湮灭，取决于下一个vertex的出口到底翻不翻，翻则不连续性传播；不翻则无不连续性，loop可以在终止了. 当遇到终点是翻转自旋回到原点的时候，意识到初始的vertex是还是单自旋翻转的vertex，此时我们决定跟随终点翻转传播不连续性至起点，将原来不翻转的起点给翻了，这样新出来一个不连续性和终点的不连续性互相湮灭. 这样的话，闭合的loop实际上和之前起点翻、终点翻的loop是没有区别的，总的来说因为人为假设起点不翻，只是多了一种在中途停止的可能性”string”.

---

代码实现的部分讲解

Technical details 技术细节

局部更新之对角更新

(和YZ聊了一下这么做应该是没问题的，之后再写进去)

Loop更新

从随机选一个腿开始

do !select random vertex's leg
   v0=int(ran()*(mm))*4+int(4.0*ran())
   if(vertexlist(v0)>=0) exit
enddo !end select

判断起点vertex是site vertex还是bond vertex，是后者的话当一端遇到site end时需要另起.

我们将引入一个判断，如果是site start，记为-2，如果是bond start，记为-1.

v3=-2
   if(mod(opstring(v0/4),4)==1 .or. mod(opstring(v0/4),4)==2) v3=-1

XXZ中的退出方式无非是两种

以短箭头为出发点，(a)是通过v1=vertexlist(v2)纵向连接，并发现v1=v0来退出

if((v1==v0).and.(n/=1)) then

(b)是通过v1连到了起点bond vertex之后，又一次执行了路径判断，发现v2 = ir(ieor(v1,1)) == v0来退出.

if (v2==v0) exit

这在构建过程中已经实现.

我们分别考察两种闭合方式中的自旋翻转和算符类型更改。



在程序中我们是通过v2, v1=vertexlist(v2)绕过边界来实现连接的“这一段”之间的自旋翻转的，因此，起点出发作为起点本身的自旋是没有翻转的，对于(a)相当于是最后一段的自旋翻转“推”到了起点，引起了起点的自旋翻转；对于(b)起点本来也没有翻转，

程序主体:

do ...!for MCStep
! 怎样算一个MC步由自己定义，目前来讲是通过fixed Loop number来退出:
l = l+1 ! 完成的loop计数

select a random vertex's leg v0

   v1=v0

do !for makeloop of v0
 !now we deal with v1
   i=v1/4 !add
   op=opstring(i)
   b=op/4 !this cant distinct the bond or site
   
   
   !(a)种退出的情况: 一定在已经翻转v2,v1=vertexlist(v2)路段之后
   if((v1==v0).and.(n/=1)) exit
  	
   
   if(    ) then !进行v1所在vertex类型的判断
   		!根据入口、概率决定去向
   		v2 = ..
   		v1 = vertexlist(v2)
   		n = n+1
   		
   		!(b)种退出的情况
   		if (v2==v0) exit
   
   ...
   
   
   endif
   
   
   
   !翻转自旋
   !在这里仅翻转对周期性边界上自旋会产生影响的路段
   
	  b=opstring(v2/4)/4 !这里假设b = op/4
      
      if (mod(v2,4)>1) then !*判断v2在上面两条腿
         if (v2>v1) then
            s1=bsites(mod(v2,4)-1,b) !* bsites(1,b) or bsites(2,b)
            spin(s1)=-spin(s1) 
         endif
      
      else !*或者v2是下面两条腿
         if (v2<v1) then !*且v2在作为纵向跳转的v1的下面
            s1=bsites(mod(v2,4)+1,b) !* 也就是 i or j
            spin(s1)=-spin(s1) 
         endif
      endif
 enddo
 
 if(l>=20) exit !用来退出loop构造
 
 enddo !for end MCStep
   

现在我们知道程序中实际上未对v0所在的腿进行翻转的处理. 但依然在两种闭合方式下符合.

仿照这样的处理方式，我们引入site算符，并且使用热浴解出的概率.

[^ 1]: In particular, external fields cannot be taken into account when constructing a loop, and the loop-flip is then conditional upon a subsequent Metropolis accept/reject step. The acceptance probability for large loops in a high field is small, and this approach is therefore feasible only at high temperatures or very weak fields.
[^ 2]: In the worm and SSE operator-loop algorithms, detailed balance is ensured by local probabilistic rules, and the resulting closed-loop configurations are always accepted.
[^ 3]: Two link-discontinuities (which are analogous to the source operators in the worm algorithm) are then created when the first entrance and exit spins are flipped, i.e., these legs will now be linked to legs with different spins . Configurations contributing to Z only contain links between same-spin legs. When the loop closes, the two discontinuities annihilate each other, and a new contributing configuration has then been generated.
[^ 4]: The probabilities for the different exit legs (e = 1,…4), given the type of the vertex (k = 1,…6) and an entrance leg (i = 1,…4), are chosen such that detailed balance is satisfied. The sum of all these path weights over all exits e must equal the bare vertex weight. And the actual normalized exit probability is the path weight divided by the bare vertex weight.
[^ 5]: local detailed balance. The key observation leading to the directed-loop equations is that the weights for vertex-paths i → e that constitute each other’s reverses have to be equal: If the path i → e through vertex k leads to the vertex k′ when the entrance and exit spins have been flipped, then the reverse path e → i through k′ yields vertex k

[^ 6]: 一般来说，对于S > 1/2和软核玻色子，最小化反弹概率不会导致有向环方程的唯一解，因此还必须施加一些其他约束。还指出，最小化反弹并不一定是最佳策略[31]（从一开始就预料到这不一定是绝对正确的）。此外，对于S > 1的海森堡模型，为了完全消除反弹，必须为在构建环时存在的不连续性（源）分配不等于1的乘法权重。
[^ 7]: 更详细的说，原文讨论的是守恒定律是vertex上下两条腿自旋之和必须相等，这是哈密顿量与$S^z$对易造成的. 既如此，一个vertex入口腿出口腿必须都翻转，形成一个“双自旋翻转”的vertex，不难立马想到，这样的更新方式会在起点产生一个链接不连续性，因此，这里的守恒定律说的是，由守恒定律导致入口腿出口腿都要改变状态时，只有loop闭合才可以消除不连续. When there is a conservation law such that the state change at the exit leg is determined by the state change at the entrance leg the link discontinuities will only vanish when the path closes forming a loop…. In contrast, when there is no such conservation law a link discontinuity can vanish just because an exit state is not changed, although the entrance state was changed.
[^ 8]: 当存在守恒定律时，这种起始条件是不可能的，因为不会产生新的配置，但在没有守恒定律的情况下，即使入口腿上没有状态改变，退出腿上的状态改变仍然可能发生. 以bond的角度视横场算符，The transverse field introduces vertices where the sum of the spins on the lower two legs is not equal to the sum on the upper two legs.（出现三上一下或三下一上，导致不对称）Thus the conservation law utilized in Sec. IV cannot be used and we must include the possibilities of a state change on just one leg, the entrance or the exit leg, keeping the state on the other legs unchanged.
[^ 9]: Henelius, P. 2002 这篇文章就做了 “起点自旋不翻转” 这样的修正. 初始入口腿上没有链接不连续性