We study the problem of approximating the partition function of the ferromagnetic Ising model in graphs and hypergraphs. Our first result is a deterministic approximation scheme (an FPTAS) for the partition function in bounded degree graphs that is valid over the entire range of parameters &#x03B2; (the interaction) and &#x03BB; (the external field), except for the case |&#x03BB;|=1 (the zero-field case). A randomized algorithm (FPRAS) for all graphs, and all &#x03B2;,&#x03BB; has long been known. Unlike most other deterministic approximation algorithms for problems in statistical physics and counting, our algorithm does not rely on the decay of correlations property. Rather, we exploit and extend machinery developed recently by Barvinok, and Patel and Regts, based on the location of the complex zeros of the partition function, which can be seen as an algorithmic realization of the classical Lee-Yang approach to phase transitions. Our approach extends to the more general setting of the Ising model on hypergraphs of bounded degree and edge size, where no previous algorithms (even randomized) were known for a wide range of parameters. In order to achieve this extension, we establish a tight version of the Lee-Yang theorem for the Ising model on hypergraphs, improving a classical result of Suzuki and Fisher.
Since the problems are in fact #P-hard in most cases, algorithmic interest has focused largely on approximation , motivated also by the general observation that approximating the partition function is polynomial time equivalent to sampling (approximately) from the underlying Gibbs distribution @cite_49 . In fact, most early approximation algorithms exploited this connection, and gave fully-polynomial randomized approximation schemes (FPRAS) for the partition function using Markov chain Monte Carlo (MCMC) samplers for the Gibbs distribution. In particular, for the ferromagnetic Ising model, the MCMC-based algorithm of Jerrum and Sinclair @cite_47 is valid for all positive real values of @math and for all graphs, irrespective of their vertex degrees. (For the connection with random sampling in this case, see @cite_9 .) This was later extended to ferromagnetic two-spin systems by Goldberg, Jerrum and Paterson @cite_33 . Similar techniques have been applied recently to the related random-cluster model by Guo and Jerrum @cite_20 .
@cite_33 @cite_9 @cite_49 @cite_47 @cite_20
2122772637 2038383704 2051283034 2024710200 2963060913
The subject of this article is spin-systems as studied in statistical physics. We focus on the case of two spins. This case encompasses models of physical interest, such as the classical Ising model (ferromagnetic or antiferromagnetic, with or without an applied magnetic field) and the hard-core gas model. There are three degrees of freedom, corresponding to our parameters beta, gamma and mu. We wish to study the complexity of (approximately) computing the partition function in terms of these parameters. We pay special attention to the symmetric case mu=1 for which our results are depicted in Figure 1. Exact computation of the partition function Z is NP-hard except in the trivial case beta gamma=1, so we concentrate on the issue of whether Z can be computed within small relative error in polynomial time. We show that there is a fully polynomial randomised approximation scheme (FPRAS) for the partition function in the "ferromagnetic" region beta gamma >= 1, but (unless RP=NP) there is no FPRAS in the "antiferromagnetic" region corresponding to the square defined by 0<beta<1 and 0<gamma<1. Neither of these "natural" regions --- neither the hyperbola nor the square --- marks the boundary between tractable and intractable. In one direction, we provide an FPRAS for the partition function within a region which extends well away from the hyperbola. In the other direction, we exhibit two tiny, symmetric, intractable regions extending beyond the antiferromagnetic region. We also extend our results to the asymmetric case mu not equal to 1. Abstract The class of problems involving the random generation of combinatorial structures from a uniform distribution is considered. Uniform generation problems are, in computational difficulty, intermediate between classical existence and counting problems. It is shown that exactly uniform generation of ‘efficiently verifiable’ combinatorial structures is reducible to approximate counting (and hence, is within the third level of the polynomial hierarchy). Natural combinatorial problems are presented which exhibit complexity gaps between their existence and generation, and between their generation and counting versions. It is further shown that for self-reducible problems, almost uniform generation and randomized approximate counting are inter-reducible, and hence, of similar complexity. The paper presents a randomised algorithm which evaluates the partition function of an arbitrary ferromagnetic Ising system to any specified degree of accuracy. The running time of the algorithm in... We show for the first time that the mixing time of Glauber (single edge update) dynamics for the random cluster model at q = 2 is bounded by a polynomial in the size of the underlying graph. As a consequence, the Swendsen-Wang algorithm for the ferromagnetic Ising model at any temperature has the same polynomial mixing time bound.