  Ising and Potts models are an important class of discrete probability
distributions which originated from Statistical Physics and since then have
found applications in several disciplines. Simulation from these models is a
well known challenging problem. In this paper, we propose a class of MCMC
algorithms to simulate from both Ising and Potts models, by using auxiliary
Gaussian random variables. Our algorithms apply to coupling matrices with both
positive and negative entries, thus including Spin Glass models such as the SK
and Hopfield model. In contrast to existing methods of a similar flavor, our
algorithm can take advantage of the low-rank structure of the coupling matrix,
and scales linearly with the number of states in a Potts model. We compare our
proposed algorithm to existing state of the art algorithms, such as the
Swendsen-Wang and Wolff algorithms for Ising and Potts models on graphs, and
the Heat Bath for Spin Glass models. Our comparison takes into account a wide
range of coupling matrices and temperature regimes, focusing in particular on
behavior at or below the critical temperature. For cold systems, augmenting our
algorithm with a tempering scheme yields significant improvements.
