Cavity method
Encyclopedia
The Cavity method is a mathematical method due to M. Mezard, Giorgio Parisi
and Miguel Angel Virasoro
in 1985 to solve some mean field type of models in statistical physics
, specially adapted to disordered systems. It has been used to compute properties of ground state
s in many condensed matter
and optimization problem
s. Initially invented to deal with the Sherrington Kirkpatrick model of spin glasses, it has shown wide applicability. It can be regarded as a generalization of the Bethe Peierls iterative method in tree-like graphs to the case of graph with loops that are not too short. The different approximations that can be done with the cavity method are usually named after their equivalent with the different steps of the replica method
which is mathematically more subtle and less intuitive than the cavity approach.
The cavity method has played and is playing a major role in the solution of optimization problem
s like the K-satisfiability
and the graph coloring
in present days. It has yielded not only ground states energy predictions in the average case, but also has inspired algorithmic methods for solving particular instances of an optimization problem
.
and is closely related to other methods and algorithms in different fields of mathematics such as belief propagation
. It has been created initially in the context of spin glasses as an alternative of the replica trick
.
Giorgio Parisi
Giorgio Parisi is an Italian theoretical physicist. He is best known for his works concerning statistical mechanics, quantum field theory and various aspects of physics, mathematics and science in general....
and Miguel Angel Virasoro
Miguel Angel Virasoro
Miguel Angel Virasoro is an Argentine physicist who did most of his work in Italy. The Virasoro algebra is named after him. Together with Giorgio Parisi and Marc Mezard he discovered the...
in 1985 to solve some mean field type of models in statistical physics
Statistical physics
Statistical physics is the branch of physics that uses methods of probability theory and statistics, and particularly the mathematical tools for dealing with large populations and approximations, in solving physical problems. It can describe a wide variety of fields with an inherently stochastic...
, specially adapted to disordered systems. It has been used to compute properties of ground state
Ground state
The ground state of a quantum mechanical system is its lowest-energy state; the energy of the ground state is known as the zero-point energy of the system. An excited state is any state with energy greater than the ground state...
s in many condensed matter
Condensed Matter
Condensed matter may refer to several things*Condensed matter physics, the study of the physical properties of condensed phases of matter*European Physical Journal B: Condensed Matter and Complex Systems, a scientific journal published by EDP sciences...
and optimization problem
Optimization problem
In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...
s. Initially invented to deal with the Sherrington Kirkpatrick model of spin glasses, it has shown wide applicability. It can be regarded as a generalization of the Bethe Peierls iterative method in tree-like graphs to the case of graph with loops that are not too short. The different approximations that can be done with the cavity method are usually named after their equivalent with the different steps of the replica method
Replica trick
In statistical physics of spin glasses and other systems with quenched disorder, the replica trick is a mathematical technique based on the application of the formula- Mathematical Trick :...
which is mathematically more subtle and less intuitive than the cavity approach.
The cavity method has played and is playing a major role in the solution of optimization problem
Optimization problem
In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...
s like the K-satisfiability
Boolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
and the graph coloring
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
in present days. It has yielded not only ground states energy predictions in the average case, but also has inspired algorithmic methods for solving particular instances of an optimization problem
Optimization problem
In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...
.
See also
The cavity method has been created in the context of statistical physicsStatistical physics
Statistical physics is the branch of physics that uses methods of probability theory and statistics, and particularly the mathematical tools for dealing with large populations and approximations, in solving physical problems. It can describe a wide variety of fields with an inherently stochastic...
and is closely related to other methods and algorithms in different fields of mathematics such as belief propagation
Belief propagation
Belief propagation is a message passing algorithm for performing inference on graphical models, such as Bayesian networks and Markov random fields. It calculates the marginal distribution for each unobserved node, conditional on any observed nodes...
. It has been created initially in the context of spin glasses as an alternative of the replica trick
Replica trick
In statistical physics of spin glasses and other systems with quenched disorder, the replica trick is a mathematical technique based on the application of the formula- Mathematical Trick :...
.