Numerical sign problem

From Wikipedia, the free encyclopedia

 The introduction to this article provides insufficient context for those unfamiliar with the subject.
Please help improve the article with a good introductory style.

In physics, the numerical sign problem refers to the slow statistical convergence of a numerical integration procedure like the Metropolis Monte Carlo algorithm, when applied to compute a many-particle theory characterized by a complex or non-positive semidefinite weight function. Such weight functions typically occur in field theories of classical and quantum many-particle systems, obtained via the Hubbard-Stratonovich transformation (Baeurle 2002, Baeurle 2007, Schmid 1998, Baer 1998), as well as in real-time Feynman path integral quantum dynamics (Makri 1987, Miller 2005). In case of field theories the difficulty relates to the oscillatory nature of the weight function in specific parameter ranges, resulting from strong repulsive forces between the particles (Baeurle 2004).

Contents

[edit] Sign problem of statistical field theories

[edit] Sampling with non-positive semidefinite weight functions

To explain the numerical sign problem, let us in the following consider a statistical field theory of interacting particles, whose statistics is described by the non-positive semidefinite weight function \rho \left[ \; \sigma \; \right] (Baeurle 2002a). For such a system, the thermodynamic average of a physical property A can be expressed in the general form (Baeurle 2003)

\langle A \rangle = \frac{\int D \sigma \; A \left[ \; \sigma \; \right] \; \rho \left[ \; \sigma \; \right]}{\int D \sigma \; \rho \left[ \; \sigma \; \right]},

where Dσ represents the field integration measure and A \left[ \; \sigma \; \right] the estimator belonging to the real and non-positive semidefinite distribution \rho \left[ \; \sigma \; \right]. It is well-established that an average in the presence of such a distribution cannot be evaluated with standard numerical integration techniques like the Metropolis Monte Carlo algorithm, since they are only valid for real and positive probability distributions (Salcedo 1997).

[edit] Reweighting procedure

The common approach in such cases is to employ a reweighting procedure, which consists in factorizing the original distribution into a real and positive definite part, called the reference distribution, and a remainder, which is included in the estimator. The ensemble average of the property A can then be calculated with a standard simulation approach, like Metropolis Monte Carlo, by evaluating the following expression

\langle A \rangle = \frac{ \int D \sigma \; A \left[ \; \sigma \; \right] \; \frac{\rho \left[ \; \sigma \; \right]}{\rho^\text{ref} \left[ \; \sigma \; \right]} \; \rho^\text{ref} \left[ \; \sigma \; \right]}{ \int D \sigma \; \frac{\rho \left[ \; \sigma \; \right]}{\rho^\text{ref} \left[ \; \sigma \; \right]} \; \rho^\text{ref} \left[ \; \sigma \; \right]} = \frac{\left\langle A \left[ \; \sigma \; \right] \; \frac{\rho \left[ \; \sigma \; \right]}{\rho^\text{ref} \left[ \; \sigma \; \right]} \right\rangle^\text{ref}}{ \left\langle \frac{\rho \left[ \; \sigma \; \right]}{\rho^\text{ref} \left[ \; \sigma \; \right]} \right\rangle^\text{ref}},

where the brackets \langle \cdots \rangle^\text{ref} denote averaging with respect to the real and positive definite reference distribution \rho^\text{ref} \left[ \; \sigma \; \right]. In practice, the averages in the numerator and denominator are approximated by their respective discrete sum (Baeurle 2003)

\langle A \rangle \approx \lim_{\tau_\text{run} \longrightarrow \infty} \frac{\sum\limits_{i=1}^{\tau_\text{run}} \; A \left[ \; \sigma_i \; \right] \; \frac{\rho \left[ \; \sigma_i \; \right]}{\rho^\text{ref} \left[ \; \sigma_i \; \right]}}{ \sum\limits_{i=1}^{\tau_\text{run}} \; \frac{\rho \left[ \; \sigma_i \; \right]}{\rho^\text{ref} \left[ \; \sigma_i \; \right]}},

where τrun defines the total number of simulation steps.

[edit] Choice of reference system and sign problem

A crucial issue for the effective evaluation of the ensemble average \langle A \rangle is to choose a reference distribution, which minimizes the standard deviations of the averages of the numerator and denominator, as well as is independent of the estimator A \left[ \; \sigma \; \right]. The best possible reference distribution is obtained through the application of the variational method (Kieu 1994), which provides

\rho^\text{ref} \left[ \; \sigma \; \right] = \frac{\left| \; \rho \left[ \; \sigma \; \right] \; \right|}{\int D \sigma \left| \; \rho \left[ \; \sigma \; \right] \; \right|},

with the optimal standard deviation for the denominator average

\sigma \left( \langle {\rm sign} \left[ \; \sigma \; \right] \rangle^\text{ref} \right) = \sqrt{1 - \langle {\rm sign} \left[ \; \sigma \; \right] \rangle^{\text{ref} \; ^2}},

where

\langle {\rm sign} \left[ \; \sigma \; \right] \rangle^\text{ref} = \frac{\int D \sigma \; \rho \left[ \; \sigma \; \right]}{\int D \sigma \; \left| \; \rho \left[ \; \sigma \; \right] \; \right|}

is the average of the sign function. The sign problem now occurs when the average of the sign

\langle {\rm sign} \left[ \; \sigma \; \right] \rangle^\text{ref} \longrightarrow 0,

which causes that, unless a huge number of configurations are sampled, the large statistical fluctuations of the quantity render the calculation meaningless.

[edit] Methods for reducing the sign problem

[edit] Analytical techniques

Several analytical and numerical techniques have been developed to alleviate the numerical sign problem effectively. The analytical techniques essentially base on the contour-shifting procedure, which makes use of the Cauchy’s integral theorem to shift the integration contour of the functional integral into the complex plane in such way that it crosses as many critical points as possible. Critical points in a mathematical sense (Baeurle 2003a) define configurations, which provide the main contributions to the integral, like e.g. the mean field solution. Contour-shifts through the mean field solution of functional integrals have successfully been employed in field-theoretic electronic structure calculations (Baer 1998) and in statistical simulations of classical many-particle systems (Baeurle 2002, Baeurle 2002a). In a very recent work it has been demonstrated that better contour shifts with regard to statistical convergence can be obtained by employing tadpole renormalization techniques (Baeurle 2002).

[edit] Numerical techniques

Numerical techniques essentially rely on the stationary phase Monte Carlo technique (Doll 1988), which is a numerical strategy for importance sampling around the stationary phase points of the functional integral. Such techniques have sucessfully been used for sampling Feynman-path integrals in real-time quantum dynamics, as well as statistical field theories of classical many particle systems (Baeurle 2003a).

[edit] References

[edit] See also

[edit] External links