Loop algorithm

Massie, 1986] Massie, D. (1986). A survey of looping algorithms for sampled data musical instruments. In Proc. IEEE Workshop Appl. of Signal Processing to Audio and Acoustics, Mohonk Mountain House, New Paltz, NY. 

For a discussion and an example on how to program an arbitrary number of nested loops using a single loop algorithm, allowing to realize an arbitrary number of nested sums, see references [45b,c]. 

Windemuth and Schulten described a further variant of the systolic loop algorithm, the replicated systolic loop for the efficient calculation of macromolecular force fields on the Connection Machine (e.g., CM-1, CM-2, CM-5). The full force field was separated into bond interactions and nonbonding interactions only the latter were implemented on the Connection Machine, and parallelized by the replicated systolic loop algorithm. The former, less computationally intensive tasks were performed by an existing, conventional MD code on the front end. 

Which one of these variations one should use is mostly a question of the balance between communication and calculation of the parallel computer being used. In any case as the systems grow larger the RD method will be limited by the all-to-all global communication steps. However, there is an improvement of the RD method which avoids global all-to-all communication [102]. Also it is possible to combine the ideas of RD with systolic loop algorithms. The main reason to do this would be to decrease the need for node memory and it also opens up the possibility for overlapping communication and calculation [46,103-105]. 

While the loop algorithm was originally developed only for spin-1/2 models it has been generalized to higher spin models [56-59] and anisotropic spin... 

Worm and Directed Loop Updates The Loop Algorithm in a Magnetic Field... 

As successful as the loop algorithm is, it is restricted - as most classical cluster algorithms - to models with spin inversion symmetry. Terms in the Hamiltonian which break this spin-inversion symmetry, such as a magnetic field, are not taken into account during loop construction. Instead they enter through the acceptance rate of the loop flip, which can be exponentially small at low temperatures. 

The loop, worm and directed loop algorithms can be used for the simulation of a wide class of quantum magnets. They are of interest not only to theoretical physicists, but also to experimentalists who want to fit experimental measurements to theoretical models. The wide applicability of these methods has led to the publication of open-source versions of these algorithms as part of the ALPS project (Algorithms and Libraries for Physics Simulations) [10] on the web page http //alps.comp-phys.org/. 

The loop algorithm has been applied to a wide range of problems, ranging from purely theoretical questions to experimental data fitting. Below we list a... 

The worm and directed loop algorithms are applied when magnetic fields are present. Typical examples include the calculation of magnetization curves of quantum magnets [74], the determination of the first order nature of the spin flop transition in two dimensions [75] and the calculation of phase diagrams of dimerized quantum magnets in a magnetic field [76]. 

N. Kawashima and J. Gubernatis (1994) Loop algorithms for Monte Carlo simulations of quantum spin systems. Phys. Rev. Lett. 73, p. 1295... 

Data movement in systolic loop algorithm for aU-to-aU broadcast involving four processes, P0-P3. Using p processes, the algorithm requires p - 1 steps. Initially, process Pi owns data Di, and upon completion, the full data set Do, Di, D2, D3 has been copied to every process. 

Results for ratios of delays indicate that proportional loss differentiation (i.e., schedule cancellation) is achieved when the outbound route is overloaded and traffic is dropped. However, it is not met in any of the algorithms when the queue falls to 0. This implies that the algorithms basically manipulate the queue of the flow members and scheduling of the members to meet the relative delay and loss guarantees. With this the REP feedback loops used in the closed-loop algorithm appear to be robust to variations in the offered load, and the results of the REP closed-loop algorithm are found to be better than the one without any shift. 

FIGURE 10.1 Double-loop algorithm employed in ADFT/cDFT calculations for the optimization of MO coefficients and cDFT Lagrange multipliers. 

Interestingly, the effort invested in developing vectorizable algorithms pays off on scalar architectures as well. The CPU ratio between the nested-loop algorithm and the algorithm just presented is slightly more favorable for the latter on vector machines since the nested DO loop constructs of Section III.D contain comparatively more or deeper IP s and low-count do s that must be unrolled. 

Inserting complete sets of basis states between the different Hi factors then leads to a similar representation of the partition function and a similar world-line picture as in the world-line Monte Carlo method. Because there is no Trotter decomposition involved, the method is free of time discretization errors from the outset. Early applications of the SSE method employed local updates, but more efficient cluster-type updates have been developed more recently to overcome the critical slowing down. They include the operator-loop update and the previously mentioned directed-loop algorithm. ... 

Remember, as long as the real robot s sensors and motors respond similarly to the simulator, then closed-loop algorithms developed for the simulator generally work with the real robot with minimal, if any, modification. Even if there are significant differences between the simulation and the real robot, an algorithm developed on the simulation is far easier to fine-tune with the real robot than developing the entire algorithm fi om scratch. 

---