Sampling algorithms

standardMC(X::AbstractGraph, β::Real, iters::Integer; keywords...)

Runs iters iterations of a standard Metropolis Monte Carlo algorithm on the given Ising spin model X, at inverse temperature β. Each spin flip attempt counts as an iteration.

Returns two objects: a vector of energies and the last configuration (see Config).

Possible keyord arguments are:

• step: the interval of iterations with which to collect energies (for the returned result) and to call the hook function (see below). The default is 1, which is good for debugging but otherwise generally a bad idea.
• seed: the random seed. The default is some arbitrary number.
• C0: the initial configuration. The default is nothing, in which case it is initialized at random. Otherwise it can be a Config object. Passing the result of a previous run can be useful e.g. when implementing a simulated annealing protocol, or if the system has not equilibrated yet.
• hook: a function to be executed after every step number of iterations (see above). It must take five arguments: the current iteration, the graph X, the current configuration, the number of accepted moves so far, and the current energy. Useful to collect data other than the energy, write to files ecc; you'd probably want to use a closure, see the example below. The return value must be a Bool: return false to interrupt the simulation, true otherwise. The default does nothing and just returns true.

Basic example:

julia> Random.seed!(76543); X = RRRMC.GraphPSpin3(3999, 5); β = 1.0;
julia> Es, C = standardMC(X, β, 100_000, step = 1_000);

Example of using the hook for collecting samples as the columns of a BitMatrix:

julia> iters = 100_000; step = 1_000; l = iters ÷ step; N = RRRMC.getN(X);
julia> Cs = BitArray(undef, N, l); hook = (it, X, C, acc, E) -> (Cs[:,it÷step]=C.s; true);
julia> Es, C = standardMC(X, β, iters, step = step, hook = hook);

rrrMC(X::AbstractGraph, β::Real, iters::Integer; keywords...)

Same as standardMC, but uses the reduced-rejection-rate method. Each iteration takes more time, but has a higher chance of being accepted, so fewer iterations overall should be needed normally. Whether this trade-off is convenient depends on the parameters and the details of the model. This function has specialized versions for DiscrGraph and DoubleGraph models.

The return values and the keyword arguments are the same as standardMC, see the usage examples for that function.

bklMC(X::AbstractGraph, β::Real, iters::Integer; keywords...)

Same as standardMC, but uses the rejection-free method by Bortz, Kalos and Lebowitz. Each step takes more time, but rejected moves are almost free, since they are skipped entirely. This function has a specialized version for DiscrGraph models.

The return values and the keyword arguments are the same as standardMC, see the usage examples for that function.

Note that the number of iterations includes the rejected moves. This makes the results directly comparable with those of standardMC. It also means that increasing β at fixed iters will result in fewer steps being actually computed.

wtmMC(X::AbstractGraph, β::Real, samples::Integer; keywords...)

Same as standardMC, but uses the rejection-free waiting-time method by Dall and Sibani. It is similar to bklMC.

The return values and the keyword arguments are almost the same as standardMC, see the usage examples for that function. However, the waiting time method uses an internal "global time" variable, which takes the place of the "iterations" counter of standardMC and of bklMC. Thus, this function has two differences with respect to the other samplers in the module:

• the function takes a samples integer argument, with the maximum number of samples which will be collected.
• the step keyword argument is of type Float64 instead of integer (default value = 1.0; you'll probably want to change this). The step is measured in terms of the global time variable and is scaled with the size of the problem N.

The total number of samples actually collected can still be less than samples if the hook function from the keyword arguments returns false earlier.

extremal_opt(X::AbstractGraph, τ::Real, iters::Integer; keywords...)

Extremal optimization algorithm: it seeks the lowest energy state of a given Ising spin model X by performing a random walk biased towards low-energy states, but with a heavy tail which allows it to avoid getting trapped.

The interface is very similar to that of standardMC and the other RRRMC Monte Carlo functions, but it takes a parameter τ instead of β, the return values are different, and the hook keyword argument has a different signature, see below.

The parameter τ controls the shape of the tail and should be larger than 1 (a reasonable value could be 1.3); iters is the total number of spin flips performed.

This function has a specialized version for DiscrGraph models; otherwise, it works but it is not implemented very efficiently at the moment (each spin flip takes O(N) time even on diluted graphs).

Returns 4 objects: the final configuration, the minimum energy found, the configuration of minimum energy, and the iteration at which such configuration was found (see Config).

Possible keyord arguments are:

• step: the interval of iterations with which to call the hook function (see below). The default is 1, which is good for debugging but otherwise generally a bad idea, probably.
• seed: the random seed. The default is some arbitrary number.
• C0: the initial configuration. The default is nothing, in which case it is initialized at random. Otherwise it can be a Config object.
• hook: a function to be executed after every step number of iterations (see above). It must take five arguments: the current iteration, the graph X, the current configuration, the current energy, and the minimum energy found so far. Useful to collect data other than the energy, write to files ecc; you'd probably want to use a closure, see the example below. The return value must be a Bool: return false to interrupt the simulation, true otherwise. The default does nothing and just returns true. Note that the signature is similar to that of the corresponding hook argument in standardMC, but different.

Basic example:

julia> Random.seed!(76543); X = RRRMC.GraphPSpin3(3999, 5); τ = 1.3;
julia> C, Emin, Cmin, itmin = extremal_opt(X, τ, 100_000, step = 1_000);

Example of using the hook for collecting samples as the columns of a BitMatrix:

julia> iters = 100_000; step = 1_000; l = iters ÷ step; N = RRRMC.getN(X);
julia> Cs = BitArray(undef, N, l); hook = (it, X, C, E, Emin) -> (Cs[:,it÷step]=C.s; true);
julia> C, Emin, Cmin, itmin = extremal_opt(X, τ, iters, step = step, hook = hook);

Config(N::Integer)

The object storing the configuration for an Ising model. Although the spin values are $σ_i ∈ {-1,1}$, internally they are stored in a BitArray, in the type field s, so that to obtain the real value one needs to perform the transformation $σ_i = 2s_i - 1$.