Optimization and exact sampling algorithms for simulations of glassy materials

Date of Award


Degree Type


Degree Name

Doctor of Philosophy (PhD)




A. Alan Middleton

Second Advisor

A. Alan Middleton


Spin glass, Planar lattice, Dimer, Ferromagnets

Subject Categories

Condensed Matter Physics | Physical Sciences and Mathematics | Physics


Slow dynamics in disordered materials prohibits the direct simulation of their rich behavior. Clever algorithms are therefore needed to study low temperature states. This thesis presents three efficient algorithms for the numerical simulation of the Edwards Anderson model with Ising spins.

In two dimensions, the spin glass model is exactly mapped to a disordered dimer covering model. An efficient algorithm for finding minimum-weight perfect matchings is applied to rapidly compute the ground states of both models. Extended ground states in Ising spin glasses on a torus, which are optimized over all boundary conditions, are used to compute precise values for ground state energy densities.

Also, an exact sampling algorithm is presented that generates configurations of the two dimensional Ising spin glass at finite temperature, with probabilities proportional to their Boltzmann weights. The algorithm uses the above mapping, and adapts Wilson's algorithm for sampling dimer coverings on a planar lattice. This algorithm is recursive: it computes probabilities for spins along a "separator" that divides the sample in half. Given the spins on the separator, sample configurations for the two separated halves are generated by further division and assignment. For n spins and given floating point precision, the algorithm has an asymptotic run-time of O ( n 3/2 ).

Finally, a technique is presented for simulating the nonequilibrium behavior of spin glasses. "Patchwork dynamics" mimics the relaxation of a spin glass over a broad range of time scales by equilibrating or optimizing directly on successive length scales. This dynamics is used to study coarsening and to replicate memory effects for spin glasses and random ferromagnets. It is also used to find, with high confidence, exact ground states in large or toroidal samples.


Surface provides description only. Full text is available to ProQuest subscribers. Ask your Librarian for assistance.