The Ising partition function: zeros and deterministic approximation
From MaRDI portal
Hypergraphs (05C65) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40) 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
- scientific article; zbMATH DE number 177833
Cites work
- 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
- 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?)
- 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 complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs
- The computational complexity of two‐state spin systems
- 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 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
(31)- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- The complexity of approximating the complex-valued Potts model
- Zeros and approximations of holant polynomials on the complex plane
- Algorithmic Pirogov-Sinai theory
- Some applications of Wagner's weighted subgraph counting polynomial
- Lee-Yang theorems and the complexity of computing averages
- Deterministic equivalent for the Allen-Cahn energy of a scaling law in the Ising model
- Polynomial-Time Approximation Algorithms for the Ising Model
- Location of zeros for the partition function of the Ising model on bounded degree graphs
- scientific article; zbMATH DE number 177833 (Why is no real title available?)
- More on zeros and approximation of the Ising partition function
- Lee–Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
- The complexity of approximating the complex-valued Potts model
- Fisher Zeros and Correlation Decay in the Ising Model
- scientific article; zbMATH DE number 7561741 (Why is no real title available?)
- Cycle basis Markov chains for the Ising model
- Fisher zeros and correlation decay in the Ising model
- Approximating pairwise correlations in the Ising model
- Mean-field approximation, convex hierarchies, and the optimality of correlation rounding: a unified perspective
- Weighted counting of solutions to sparse systems of equations
- Lee-Yang theorems and the complexity of computing averages
- Efficient algorithms for approximating quantum partition functions
- The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs
- Lee-Yang zeros and the complexity of the ferromagnetic Ising model on bounded-degree graphs
- Spectral independence via stability and applications to Holant-type problems
- A near-optimal zero-free disk for the Ising model
- On the zeroes of hypergraph independence polynomials
- Contraction: a unified perspective of correlation decay and zero-freeness of 2-spin systems
- Correlation decay and partition function zeros: algorithms and phase transitions
- LDP for inhomogeneous U-statistics
- A binomial approximation method for the Ising model
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)
