Optimization of the Algorithm

Under some common circumstances it is possible to optimize the extended Wolff algorithms by technical means. This will depend fundamentally on the characteristics of the external source or of the boundary conditions which are present. Specially in the case of external sources, the main cause of performance degradation is the high cluster rejection rate associated to large values of the sources. Let us recall that, after the cluster is built, one has to calculate the variation $\Delta S_{\eta}$ of the external-source term of the action and then accept the cluster with the probability $\exp(-\Delta S_{\eta})$ . In order to do this, one extracts a random number $r\in[0,1)$ and only accepts the cluster if

$\begin{displaymath} r\leq\exp(-\Delta S_{\eta}), \end{displaymath}$

or, equivalently, if

$\begin{displaymath} \Delta S_{\eta}\leq-\ln(r), \end{displaymath}$

where one should note that $-\ln(r)$ is always a positive number. The best way to calculate $\Delta S_{\eta}$ is to do so along the construction of the cluster, incrementing $\Delta S_{\eta}$ as the sites are added to it. The optimizations we are talking about here are usually the following two things: if the variation of the action $S_{\eta}$ is guaranteed to be negative, then the cluster is sure to be accepted and it is not necessary to calculate $\Delta S_{\eta}$ or to perform the final Metropolis test, which saves some computational effort; if the variation of the action is known to always increase as sites are added to the cluster, then at some point one may know that the cluster will be rejected even before completing it, and then one may drop the cluster, thus saving the significant computer effort required to finish building it.

The main idea behind this is that, so long as the random number used for the final Metropolis test has a flat distribution of probabilities in , it does not matter whether it is extracted from the generator after the cluster is built or before one starts to build it. Therefore one may extract it beforehand and keep the value $-\ln(r)$ in storage for tests to be performed along the building of the cluster. In order to better exemplify the idea, let us consider a specific case. Let us consider the case in which the external source has a constant and non-vanishing value $\eta$ over the whole lattice. As we saw in the discussion of the building algorithm for the clusters, it is always true that all the sites of a cluster have the field oriented in the same direction. Therefore, if $\eta$ is a constant, all the variations of the action $S_{\eta}$ associated to the flipping of the field at each site of the cluster will have the same sign. Therefore, given $\eta$ and the initial site $\psi_{i}$ of the cluster, the following statements are true:

If $\eta\psi_{i}<0$ then all the variations of $S_{\eta}$ due to the inclusion of sites in the cluster will be negative, and hence the cluster is sure to be accepted. In fact, $\Delta S_{\eta}$ will decrease monotonically from zero as the cluster is built.
If $\eta\psi_{i}>0$ then all the variations of $S_{\eta}$ due to the inclusion of sites in the cluster will be positive, and hence the cluster may be rejected. In this case, $\Delta S_{\eta}$ will increase monotonically from zero as the cluster is built.

Note that, so long as the external source $\eta$ is not zero, it never happens that $\eta\psi_{i}=0$ . Note also that, if the random number extracted beforehand happens to be , then one cannot calculate and store $-\ln(r)$ , but in this case this is also not necessary, because the condition

$\begin{displaymath} r=0\leq\exp(-\Delta S_{\eta}) \end{displaymath}$

will be satisfied regardless of the value of $\Delta S_{\eta}$ , and hence the cluster is sure to be accepted. A simple and well-structured way to implement these ideas is to imagine that the code for building the cluster can run in one of two modes: a ``check'' mode, in which $\Delta S_{\eta}$ is calculated along the building of the cluster, and a ``no-check'' mode, in which the variations of $S_{\eta}$ are simply ignored and the cluster is built and flipped just as would happen in the absence of any external sources. Here is the algorithm for the optimized code in this case:

Choose the first site randomly, starting in check mode.
If $\eta\psi_{i}<0$ then go to no-check mode, build and flip the cluster, and loop back to step , in order to build and possibly flip a new cluster.
If $\eta\psi_{i}>0$ then extract a random number for the Metropolis test.
If then go to no-check mode, build and flip the cluster, and loop back to step , in order to build and possibly flip a new cluster.
Calculate and store $-\ln(r)$ , and stay in check mode, building the cluster and calculating $\Delta S_{\eta}$ along the construction.
As each site is added to the cluster, check the relation between the value of $\Delta S_{\eta}$ and $-\ln(r)$ : if the monotonically increasing $\Delta S_{\eta}$ surpasses $-\ln(r)$ , then reject the cluster, which means that you quit building it, repeat the current configuration in the stochastic sequence, and loop back to step , in order to build and possibly flip a new cluster.
If you get to the end of the construction of the cluster without a rejection, then flip it with probability equal to and loop back to step , in order to build and possibly flip a new cluster.

In this way one makes as much economy as possible of computer effort. The idea can be used in essentially the same way for other forms of constant external sources such as, for example, one existing only over the world line of a particle, which is a one-dimensional line of sites within the -dimensional lattice. Also, it can easily be adapted to fixed boundary conditions with a constant value of the field at the external boundary. In fact, the external source or the value at the boundary do not really have to be constant, so long as they do not change sign, for this idea to work as explained above. In these other cases additional indexing structures may be necessary, in order to single out the sites where the external source exists, or the interior sites which are next to the external boundary, connected to it by the boundary links.

It is much more difficult to optimize the case of a general external source or set of boundary conditions, which can change sign freely. One can use ideas which are similar to the ones described above, but it is much more difficult to obtain a significant amount of optimization. The basic idea goes something like what follows. Let us consider a typical intermediate situation during the construction of the cluster. Assume that one keeps updated along the construction two positive variables, $\Delta S_{\eta,{\rm min}}$ and $\Delta S_{\eta,{\rm max}}$ , which hold the maximum value that can be subtracted from the current value of $\Delta S_{\eta}$ and the maximum value that can be added to the current value of $\Delta S_{\eta}$ , respectively, during the rest of the construction of the cluster.

Under these conditions, after the inclusion of a certain site in the cluster, if one verifies that $\Delta S_{\eta}+\Delta S_{\eta,{\rm max}}$ is less than or equal to $-\ln(r)$ , then there is no chance that the action will ever increase enough to cause a rejection, and therefore one can go to no-check mode in order to build the rest of the cluster and flip it. This is so because the sum above is larger than or equal to the maximum possible value that $\Delta S_{\eta}$ can assume from this point on. Similarly, if one verifies that $\Delta S_{\eta}-\Delta S_{\eta,{\rm min}}$ is greater than $-\ln(r)$ , then there is no chance that the action will ever decrease enough to avoid a rejection, and therefore one can quit the current cluster before actually completing its construction. In this case, the difference above is smaller than the minimum possible value that $\Delta S_{\eta}$ can assume from this point on.

The initial values of the variables $\Delta S_{\eta,{\rm min}}$ and $\Delta S_{\eta,{\rm max}}$ can be obtained, respectively, as the sum of all negative single-site variations and the sum of all positive single-site variations of the action $S_{\eta}$ . Given the orientation of a certain cluster, these sums can be limited to the sites of the lattice where the field has that orientation, or even only to the sites that can actually participate of that particular cluster, because they are connected to the initial site by strings of $\ell_{+}$ links. Along the construction the values of $\Delta S_{\eta,{\rm min}}$ and $\Delta S_{\eta,{\rm max}}$ have to be modified by the addition or subtraction of the variation of $S_{\eta}$ at each site which is added to the cluster, in order to keep the variables up to date. There is, of course, an additional overhead of computer effort, needed in order to initialize and update these variables. Due to this and to the added complexity of the resulting code, sometimes it may not be worth while to implement this kind of optimization.