The Ising partition function: zeros and deterministic approximation
From MaRDI portal
Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40) Hypergraphs (05C65) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Phase transitions (general) in equilibrium statistical mechanics (82B26) Statistical mechanics of magnetic materials (82D40)
Abstract: 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 (the interaction) and (the external field), except for the case (the "zero-field" case). A randomized algorithm (FPRAS) for all graphs, and all , 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.
Recommendations
- More on zeros and approximation of the Ising partition function
- Fisher zeros and correlation decay in the Ising model
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- Location of zeros for the partition function of the Ising model on bounded degree graphs
- Publication:4038711
Cites work
- scientific article; zbMATH DE number 1268810 (Why is no real title available?)
- scientific article; zbMATH DE number 1305538 (Why is no real title available?)
- scientific article; zbMATH DE number 1559584 (Why is no real title available?)
- A Complexity Dichotomy for Partition Functions with Mixed Signs
- A generalization of permanent inequalities and applications in counting and optimization
- A power law of order 1/4 for critical mean field Swendsen-Wang dynamics
- Approach to equilibrium of Glauber dynamics in the one phase region. I: The attractive case
- Approach to equilibrium of Glauber dynamics in the one phase region. II: The general case
- Approximating partition functions of the two-state spin system
- Approximating the Permanent
- Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
- Beitrag zur Theorie des Ferromagnetismus
- Benjamini-Schramm continuity of root moments of graph polynomials
- Characterization of Lee-Yang polynomials
- Combinatorics and complexity of partition functions
- Computing the partition function for cliques in a graph
- Computing the partition function for graph homomorphisms
- Computing the partition function for graph homomorphisms with multiplicities
- Computing the permanent of (some) complex matrices
- Convergence of MCMC and loopy BP in the tree uniqueness region for the hard-core model
- Correlation decay up to uniqueness in spin systems
- Counting hypergraph matchings up to uniqueness threshold
- Counting in two-spin models on \(d\)-regular graphs
- Counting independent sets up to the tree threshold
- Critical Ising on the square lattice mixes in polynomial time
- Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
- Exact thresholds for Ising-Gibbs samplers on general graphs
- FPTAS for hardcore and Ising models on hypergraphs
- Glauber dynamics on trees and hyperbolic graphs
- Glauber dynamics on trees: Boundary conditions and mixing time
- Graph homomorphisms with complex values: a dichotomy theorem (extended abstract)
- Griffiths' singularities in diluted Ising models on the Cayley tree
- Inapproximability of the Tutte polynomial
- Interlacing families. I: Bipartite Ramanujan graphs of all degrees
- Interlacing families. II: Mixed characteristic polynomials and the Kadison-Singer problem
- Lee-Yang theorems and the complexity of computing averages
- Left and right convergence of graphs with bounded degree
- Negative dependence and the geometry of polynomials
- On a problem of Spencer
- On the distribution and gap structure of Lee-Yang zeros for the Ising model: Periodic and aperiodic couplings
- Polynomial-Time Approximation Algorithms for the Ising Model
- Random cluster dynamics for the Ising model is rapidly mixing
- Random generation of combinatorial structures from a uniform distribution
- Real stable polynomials and matroids: optimization and counting
- Spatial mixing and the connective constant: optimal bounds
- Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
- Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
- The Lee--Yang and Pólya--Schur programs. I: Linear operators preserving stability
- The Lee‐Yang and Pólya‐Schur programs. II. Theory of stable polynomials and applications
- The complexity of approximately counting in 2-spin systems on \(k\)-uniform bounded-degree hypergraphs
- The computational complexity of two‐state spin systems
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- Uniqueness, Spatial Mixing, and Approximation for Ferromagnetic 2-Spin Systems
Cited in
(27)- Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
- Some applications of Wagner's weighted subgraph counting polynomial
- The complexity of approximating the complex-valued Potts model
- Efficient algorithms for approximating quantum partition functions
- Fisher zeros and correlation decay in the Ising model
- Weighted counting of solutions to sparse systems of equations
- Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
- scientific article; zbMATH DE number 7561741 (Why is no real title available?)
- The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs
- Lee-Yang theorems and the complexity of computing averages
- Cycle basis Markov chains for the Ising model
- The complexity of approximating the complex-valued Potts model
- A binomial approximation method for the Ising model
- Deterministic equivalent for the Allen-Cahn energy of a scaling law in the Ising model
- A near-optimal zero-free disk for the Ising model
- Approximating pairwise correlations in the Ising model
- Algorithmic Pirogov-Sinai theory
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- On the zeroes of hypergraph independence polynomials
- More on zeros and approximation of the Ising partition function
- Lee-Yang theorems and the complexity of computing averages
- Polynomial-Time Approximation Algorithms for the Ising Model
- scientific article; zbMATH DE number 177833 (Why is no real title available?)
- Location of zeros for the partition function of the Ising model on bounded degree graphs
- Zeros and approximations of holant polynomials on the complex plane
- Spectral independence via stability and applications to Holant-type problems
- Lee-Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
This page was built for publication: The Ising partition function: zeros and deterministic approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1730971)
