High dimensional integration by Metropolis¶
The classical method for high-dimensional integration is the Vegas algorithm, discussed before. However, Vegas cannot resolve poles, that are not aligned with a coordinate axis.
Problems in physics very commonly require integrals over space of many coordinates, and might have the form: \begin{eqnarray} I(\vec{r}_0) = \int f(\vec{r}_0,\vec{r}_1,\vec{r}_2,\cdots,\vec{r}_N) d^3\vec{r}_1 d^3\vec{r}_2\cdots d^3\vec{r}_N \end{eqnarray} Here $f$ might have poles for many combinations of $\vec{r}_i-\vec{r}_j$ or $\vec{r}_i-\vec{r}_j-\vec{r}_k$, etc.
For a concrete example, we will think of the following convolutions \begin{eqnarray} I(\vec{r}_0) = {\cal N} \int e^{-\frac{(\vec{r}_1-\vec{r}_0)^2}{w^2}} e^{-\frac{(\vec{r}_2-\vec{r}_1)^2}{w^2}} \cdots e^{-\frac{(\vec{r}_{N-1}-\vec{r}_{N})^2}{w^2}} e^{-\frac{{\vec{r}_N}^2}{w^2}} d^3\vec{r}_1 d^3\vec{r}_2\cdots d^3\vec{r}_N \end{eqnarray} with normalization ${\cal N}= \frac{(N+1)^{3/2}}{(w \sqrt{\pi})^{3 N}},$ the value of the integral is $I(\vec{r}_0)=e^{-\frac{\vec{r}_0^2}{(N+1) w^2}}$
If width $w$ is small, this is very difficult problem for MC, even for moderate values of $N$.
We could create a Markov chain and take as the probability for a step proportionally to $|f(x)|$, i.e, the transition probability $T(X\rightarrow X') = min(|f(X')|/|f(X)|,1)$. Here $X$ stands for configuration $(\vec{r}_0,\vec{r}_1,\cdots,\vec{r}_N)$.
We would measure $f(X)/|f(X)|=\textrm{sign}(f(X))$. As a result we would get correct shape of the function $I(\vec{r}_0)$, however, the integral itself would be unknown.
More precisely, if we take the transition probability $T(X\rightarrow X') = min(|f(X')|/|f(X)|,1)$, it means that probability for configuration X is $$dP(X) = C dX |f(X)|,$$ because multiplying $f(X)$ by a positive constant leaves the Metropolis acceptance ratios unchanged. Adding a constant generally changes them.
If we are sampling $O(X)=sign(f(X))$, we would obtain
$$<O> = \int dP(X) O(X) = C \int dX |f(X)| sign(f(X))= C \int dX f(X)$$
Hence we do not know the integral, because $C$ is unknown constant.
If we have a family of curves, like $g(k)=\int dX f(X,k)$ and we want to integrate over $X$ while $k$ is external parameter, we can determine the shape of the curve $\widetilde{g}(k) = C \int dX f(X,k)$, but we will not know the normalization.
To determine the normalization, we need to introduce another function or another Hilbert space, as discussed below.
Jumping between spaces¶
The most common way to determine the unknown constant is to define two spaces, the physical space and the alternative space. The function in the alternative space should be as similar as possible to the function we are integrating, but its integral must be known, and we should be allowed to jump between the two spaces. Suppose the function in the alternative space is $V_0 f_m(X)$, where $f_m(X)$ is normalized to unity ($\int f_m(X) dX=1$) and is positive, and $V_0$ is an arbitrary constant.
Probability density in the physical space $P(X)$ is then taken to be proportional to $|f(x)|$ in the physical Hilbert space, and $V_0 f_m(x)$ in the alternative space. The probability to visit a configuration $X$ in the physical and alternative space would be: \begin{eqnarray} & d P_{physical}(X) = & dX |f(X)| \; {\cal C}\\ & d P_{alternative}(X) = & dX V_0 f_m(X) \; {\cal C} \end{eqnarray}
In Metropolis we would have two types of moves:
- jump from configuration $X\rightarrow X'$
- jump between the two spaces.
The detailed balance requires $$ dP(X) T(X\rightarrow X') = dP(X') T(X'\rightarrow X)$$ Here we have a continuous space, hence we are dealing with $dP(X)$ rather than finite $P(X)$.
If we are in the physical space, we would accept the step with $T(X\rightarrow X') = min(|f(X')|/|f(X)|,1)$. If we are in alternative space, we would accept the step with $T(X\rightarrow X') = min(f_m(X')/f_m(X),1)$, and if we are jumping from the Physical to the alternative space, we would have $T(X_p\rightarrow X'_a) = min(V_0 f_m(X'_a)/|f(X)|,1)$.
More precisely, if there is non-symmetric trial step probability, the Metropolis acceptance probability would be $A(X\rightarrow X')=min\left(1,\frac{|f(X')|\omega_{X'\rightarrow X}}{|f(X)|\omega_{X\rightarrow X'}}\right)$, where $\omega_{X'\rightarrow X}$ is the trial step probability. But let's first think of steps which have symmetric trial step probability.
We would then sample the following quantities \begin{eqnarray} O_{physical}= \sum_{i=physical} \frac{f(X_i)}{|f(X_i)|} \end{eqnarray} when we are in the physical space, and when we are in alternative space we would just count steps in this space as the function $f_m$ is positive: \begin{eqnarray} O_{alternative}= \sum_{i=alternative} 1 \end{eqnarray}
These quantities will converge to the following values \begin{eqnarray} V_{physical} &=& \int dP_{physical}(X) O_{physical}(X) ={\cal C} \int dX\; |f(X)| \frac{f(X)}{|f(X)|}\\ V_{alternative} &=& \int dP_{alternative}(X) O_{alternative}(X) ={\cal C} \int dX\; V_0 |f_m(X)| 1 \end{eqnarray} where $C$ is an arbitrary number, which we do not know. This is because the probability to reach a configuration $X$ in the physical space is $\propto dX |f(X)|$ and in alternative space is $\propto dX V_0 |f_m(X)|$.
Because the function in alternative space is normalized $\int dX |f_m(x)|=1$, we conclude that \begin{eqnarray} \frac{V_{physical}}{V_{alternative}}=\frac{1}{V_0} \int dX f(X) \end{eqnarray} hence we know the integral \begin{eqnarray} \int dX f(X) = V_0 \frac{V_{physical}}{V_{alternative}}=V_0 \frac{\sum_{i\in physical} \textrm{sign}(f(X_i))}{\sum_{i\in alternative} 1} \end{eqnarray}
The art in this approach is to find a good function $f_m(X)$, which we know how to normalize, and adjust $V_0$ so that we spend a finite, but not excessive, fraction of the time in the alternative space. A good rule is 90% in physical space, and 10% in alternative space.
The best approach is to self-consistently determine both $f_m(X)$ and the constant $V_0$ during the sampling.
But before we discuss how to determine both, we outline a simpler algorithm that is often more efficient.
Evaluation of both functions on each configuration¶
Alternatively we can define the probability for visiting configuration $X$ to be \begin{eqnarray} dP \propto |f(X)|+ V_0 f_m(X) \end{eqnarray} and now we abandon the alternative space. We only have one physical space of configurations $X$, on which we would simultaneously evaluate both $f(X)$ and $f_m(X)$.
We have freedom to adjust $V_0$. The idea is to adjust $V_0$ so that on average $|f(X)|$ is around 10-times larger than $V_0 f_m(X)$. As a result we would still visit most often those configurations in which function $|f(X)|$ is large, and if $f_m(X)$ is similar to $f(X)$ we would not visit configurations where $|f(X)|$ is very small. Even if the overlap between $f(X)$ and $f_m(X)$ is small, we will still visit configurations where $f(X)$ is large more often, because we will make sure that $V_0$ is such that on average $f(X)$ contributes much more to the weight that $V_0 f_m(X)$.
The detailed balance requires $$ dP(X) T(X\rightarrow X') = dP(X') T(X'\rightarrow X)$$ hence the acceptance probability is \begin{eqnarray} T(X\rightarrow X') = min(1,\frac{|f(X')| + V_0 f_m(X')}{|f(X)| + V_0 f_m(X)}) \end{eqnarray}
We will sample two quantities \begin{eqnarray} O_{physical} = \sum_i \frac{f(X_i)}{|f(X_i)| + V_0 f_m(X_i)}\\ O_{alternative} = \sum_i \frac{V_0 f_m(X_i)}{|f(X_i)| + V_0 f_m(X_i)} \end{eqnarray}
The two quantities will converge towards \begin{eqnarray} V_{physical} &=& \int dP(X) O_{physical}(X) ={\cal C}\int dX\; (|f(X)| + V_0 f_m(X)) \frac{f(X)}{|f(X)| + V_0 f_m(X)} = {\cal C} \int dX f(X) \\ V_{alternative} &=& \int dP(X) O_{alternative}(X) ={\cal C} \int dX\; (|f(X)| + V_0 f_m(X)) \frac{V_0 f_m(X)}{|f(X)| + V_0 f_m(X)}={\cal C}\; V_0 \end{eqnarray}
The desired integral will again be \begin{eqnarray} \int dX f(X) = V_0 \frac{V_{physical}}{V_{alternative}} \end{eqnarray}
During the simulations of the Markov chain we will adjust $V_0$ so that \begin{eqnarray} \frac{\widetilde{V}_{physical}}{V_{alternative}} \approx 10, \end{eqnarray} where \begin{eqnarray} \widetilde{V}_{physical}=\sum_i \frac{|f(X_i)|}{|f(X_i)| + V_0 f_m(X_i)} \end{eqnarray} This makes sure that the contribution from the measured function $f(X)$ is much larger than from the normalized $f_m(X)$, which is used only to get correct normalization.
Suppose that during simulation we realize that currently $\frac{\widetilde{V}_{physical}}{V_{alternative}} \approx 1$. It means that $V_{alternative}$ is around 10-times too large, hence we would reduce $V_0$ for a factor (maybe 2 initially, and then recheck). We would also need to reduce with the same constant the current sum $V_{alternative}$, because it is proportional to $V_0$. We adjust $V_0$ during an initial adaptation stage until the ratio of $\frac{\widetilde{V}_{physical}}{V_{alternative}}$ is close to the desired number. We also update the auxiliary function $f_m$ during this stage. For the final integral estimate, both $V_0$ and $f_m$ are held fixed and the measurements are restarted. This separates adaptation from production sampling.
Measuring function¶
We are left to determine the optimal function $f_m(X)$, which is as similar as possible to $|f(X)|$, but subject to the additional constraint that it is normalizable, i.e., $\int dX f_m(X)=1$.
An obvious choice (think of Vegas) is a separable ansatz: \begin{eqnarray} f_m(X=(\vec{r}_1,\vec{r}_r,\cdots,\vec{r}_N))=g_1(r_1) g_2(r_2)\cdots g_N(r_N) \end{eqnarray}
To determine the projections $g_i(r_i)$, we would self-consistently project the sampled function $|f(X)|$ onto each axis, just like in Vegas algorithm: \begin{eqnarray} g_i(x)\propto \int d\vec{r_1} d\vec{r}_2 \cdots d\vec{r}_N |f(X)|\delta(r_i-x) \end{eqnarray}
The integration of separable function is simple \begin{eqnarray} \int dX f_m(X) = \prod_{i} \int d\vec{r}_i g_i(r_i) \end{eqnarray} To avoid systematic error, we will not treat $g_i(r_i)$ function as continuous function, but rather as a step-wise constant function, with the following property \begin{eqnarray} g(x) = \sum_{l=0}^{M-1} g[l]\theta(x_l<x<x_{l+1}). \end{eqnarray} Unfortunately this makes analysis tedious, and integrals a bit more involved.
Nevertheless, for a separable function, we can readily compute \begin{eqnarray} &&1D : \int d\vec{r}_i g_i(r_i)= \Delta \sum_{l=0}^{M-1} g_i[l]\\ &&3D : \int d\vec{r}_i g_i(r_i)= \frac{4\pi \Delta^3}{3} \sum_{l=0}^{M-1} ((l+1)^3-l^3)g_i[l] \end{eqnarray} Here $\Delta$ is mesh distance for equidistant mesh.
For more complicated ansatz of convolutions, the analytic formulas can still be derived, and the equations are given below.
Implementation¶
Here we will not show all details of implementing the measuring function. It is implemented in module mweight.py, which we will include here. We will rather implement Metropolis Markov chain and use three-dimensional convolutions as the measuring function.
To test the implementation, we will use Gaussian functions, with peaks along the diagonals (not along the axes). The Gaussian integrand has the form \begin{eqnarray} f(k_0,k_1,\cdots k_{N-1}) = C e^{-|k_{N-1}|^2/w^2} e^{-|k_{N-2}-k_{N-1}|^2/w^2} e^{-|k_{N-3}-k_{N-2}|^2/w^2}\cdots e^{-|k_1-k_0|^2/w^2} \end{eqnarray} where \begin{eqnarray} C = \frac{N^{3/2} }{ ( \sqrt{\pi} w )^{3(N-1)}} \end{eqnarray}
If we integrate over all $k_n$ except one, let us say $k_0$, we will get a Gaussian of width $w\sqrt{N}$ with the form $e^{-k_0^2/(w\sqrt{N})^2}$.
from numpy import array, copy, cos, exp, linspace, ones, pi, shape, sin, sqrt, zeros
from numpy import linalg, random
from mweight import meassureWeight
from numba import jit
import matplotlib.pyplot as plt
class FuncNDiag:
""" Gaussian through all diagonals k_i=k_j, i.e.:
We have the following variables : k_0, k_1, k_2, ... k_{N-1}
The function is
fPQ = exp(-|k_{N-1}|^2/width^2) * exp(-|k_{N-2}-k_{N-1}|^2/width^2) * exp(-|k_{N-3}-k_{N-2}|^2/width^2) *...* exp(-|k_1-k_0|^2/width^2) * normalization
We integrate only over k_1,k_2,...k_{N-1} and keep k_0 as external independent variable.
We want the final result to be
exp(-k_0^2/(width^2*N)) = Integrate[ fPQ d^3k_1 d^3k_2....d^3k_{N-1} ]
Hence the normalization is
normalization = N^(3/2) / ( sqrt(pi)*width )^(3(N-1))
"""
def __init__(self, width=1, Ndim=1):
self.width = width # width of gaussians
self.Ndim = Ndim
self.cnrm = ((sqrt(pi)*self.width)**3 )**(Ndim-1)/sqrt(Ndim)**3 # integral of gaussian convolution
def __call__(self, momentum):
kn = linalg.norm( momentum[-1] )
res = exp( -(kn/self.width)**2 )/self.cnrm
for i in range(len(momentum)-1):
dk = linalg.norm( momentum[i+1]-momentum[i] )
res *= exp( -(dk/self.width)**2 )
return res
We will define several parameters for MC integration
class params:
def __init__(self):
self.kF = 1. # typical momentum
self.cutoff = 3*self.kF # integration cutoff
self.dkF = 0.1*self.kF # the size of a step
#
self.Nitt = 1000000 # total number of MC steps
self.Ncout = 50000 # how often to print
self.Nwarm = 1000 # warmup steps
self.tmeassure = 10 # how often to meassure
#
self.Nbin = 129 # how many bins for saving the histogram
self.V0norm = 2e-2 # starting V0
self.dexp = 6 # parameter for fm at the first iteration, we will use
self.recomputew = 2e4/self.tmeassure # how often to check if V0 is correct
self.per_recompute = 7 # how often to recompute fm auxiliary measuring function
This is the core of the algorithm, which implements the Metropolis random walk, and measures both functions $f$ and $f_m$ on each configuration, using $|f|+V_0 f_m$ as the weight of each configuration.
At the first iteration, the weight function $f_m$ will be
$$f_m(r) \propto \theta(r<k_F) + \left(\frac{k_F}{r}\right)^{dexp} \theta(r>k_F) $$
Later it is adjusted to
\begin{eqnarray} f_m(\vec{r}_1,\vec{r}_2,\cdots,\vec{r}_n)= g_1(r_1) h_1(|\vec{r}_n-\vec{r}_1|) g_2(r_2)h_2(|\vec{r}_n-\vec{r}_2|)\cdots g_n(r_n) \end{eqnarray}
where $g_i$ and $h_i$ are determined self-consistently from the histograms.
The external variable $r_0$ will be computed on the user-defined mesh, which is named qx[i].
Since $r_0$ is only the length of the vector in 3D, we will sample (and integrate) over its angles $\theta$ and $\phi$. In other words, we will sample $I(|\vec{r}_0|)$ rather than $I(\vec{r}_0)$. Here $$\vec{r}_0=\left(qx_i \sin(\theta)\cos(\phi), qx_i \sin(\theta)\sin(\phi), qx_i \cos(\theta)\right).$$
We draw $u=\cos\theta$ uniformly from $[-1,1]$ and $\phi$ uniformly from $[0,2\pi)$. This samples solid angle $d\Omega=d\phi\,d(\cos\theta)$ uniformly, so the angular proposal has no additional Metropolis factor. The discrete mesh index for $|\vec r_0|$ is proposed uniformly as well. Because $r_0$ is an external argument rather than a radial integration variable, no $r_0^2$ Jacobian enters this proposal. Rotational symmetry would also allow us to fix $\vec r_0=(0,0,q)$ and omit angle sampling entirely.
The internal integration variables $r_1,r_2,\ldots,r_N$ (called momentum in the code) are sampled in Cartesian coordinates, so the trial proposal is symmetric. The trial step will be
$$ \vec{r}_{new} = \vec{r}_{old} + dk\;(2\xi_1-1, 2\xi_2-1, 2\xi_3-1),$$ where $dk$=p.dkF.
But this is only provided that $|r_{new}|<= \Lambda_{cutoff}$. If $|r_{new}|>\Lambda_{cutoff}$, we instantly reject the step. The sampling is thus constrained to a set of spheres, so that no sampled internal vector has a magnitude greater than the cutoff.
def IntegrateByMetropolis2(func, qx, p):
""" Integration by Metropolis:
func(momentum) -- function to integrate
qx -- mesh given by a user
p -- other parameters
Output:
Pval(qx)
"""
#random.seed(0) # make sure that we always get the same sequence of steps
Pval = zeros(len(qx)) # Final results V_physical is stored in Pval
Pnorm = 0.0 # V_alternative is stored in Pnorm
Pval_sum = 0.0 # this is widetilde{V_physical}
Pnorm_sum = 0.0 # this is widetilde{V_alternative}
V0norm = p.V0norm # this is V0
dk_hist = 1.0 # we are creating histogram by adding each configuration with weight 1.
Ndim = func.Ndim # dimensions of the problem
inc_recompute = (p.per_recompute+0.52)/p.per_recompute # How often to self-consistently recompute
# the weight functions g_i and h_{ij}.
momentum = zeros((Ndim,3)) # contains all variables (r1,r2,r3,....r_Ndim)==configuration=X
# We call them momentum here, but could be real space vectors or momentum space vectors.
iQ = int(len(qx)*random.rand()) # which bin do we currently visit for r0, iQ is current r0=qx[iQ]
momentum[1:,:] = random.random((Ndim-1,3)) * p.kF / sqrt(3.) # Initial guess for r1,r2,....r_N is random
momentum[0,:] = [0,0,qx[iQ]] # initial configuration for r_0 has to be consistent with iQ, and will be in z-direction
# This is fm function, which is defined in mweight.py module
mweight = meassureWeight(p.dexp, p.cutoff, p.kF, p.Nbin, Ndim) # measuring function fm in alternative space
# fQ on the current configuration. Has two components (f(X), V0*f_m(X))
fQ = func(momentum), V0norm * mweight( momentum ) # fQ=(f(X), V0*f_m(X))
print('starting with f=', fQ, '\nstarting momenta=', momentum)
Nmeassure = 0 # How many measurements we had?
Nall_q, Nall_k, Nacc_q, Nacc_k = 0, 0, 0, 0 # how many steps in each category
c_recompute = 0 # when to recompute the fm auxiliary function?
adaptation_end = min(p.Nitt-1, max(p.Nwarm, int(0.7*p.Nitt)))
for itt in range(p.Nitt): # adaptation followed by fixed-weight production
iloop = int( Ndim * random.rand() ) # which variable to change, iloop=0 changes external r_0
accept = False
if (iloop == 0): # changing external variable : r_0==Q
Nall_q += 1 # how many steps changing external variable
tiQ = int( random.rand()*len(qx) ) # trial iQ for qx[iQ]
Ka_new = qx[tiQ] # |r_0| length of the vector
u, phi = 2*random.rand()-1, 2*pi*random.rand() # uniform cos(theta) and azimuth
radial_xy = Ka_new * sqrt(1-u*u)
K_new = array([radial_xy*cos(phi), radial_xy*sin(phi), Ka_new*u])
trial_ratio = 1. # uniform solid-angle proposal
accept = True # trial step always succeeds
else: # changing momentum ik>0
Nall_k += 1 # how many steps of this type
dk = (2*random.rand(3)-1)*p.dkF # change of k in cartesian coordinates of size p.dkF
K_new = momentum[iloop,:] + dk # K_new = K_old + dK
Ka_new = linalg.norm(K_new) # norm of the new vector
trial_ratio = 1. # trial step probability is just unity
accept = Ka_new <= p.cutoff # we might reject the step if the point is too far from the origin
if (accept): # trial step successful. We did not yet accept, just the trial step.
tmomentum = copy(momentum)
tmomentum[iloop,:] = K_new # this is trial configuration X_{new}=momentum
fQ_new = func(tmomentum), V0norm * mweight(tmomentum) # f_new
# Notice that we take |f_new(X)+V0*fm_new(X)|/|f_old(X)+V0*fm_old(X)| * trial_ratio
ratio = (abs(fQ_new[0])+fQ_new[1])/(abs(fQ[0])+fQ[1]) * trial_ratio
accept = abs(ratio) > 1-random.rand() # Metropolis
if accept: # the step succeeded
momentum[iloop] = K_new
fQ = fQ_new
if iloop==0:
Nacc_q += 1 # how many accepted steps of this type
iQ = tiQ # the new external variable index
else:
Nacc_k += 1 # how many accepted steps of this type
if itt == adaptation_end:
# Start production with the final fixed weight and fresh estimates.
Pval[:] = 0
Pnorm = Pval_sum = Pnorm_sum = 0.0
Nmeassure = 0
if (itt >= p.Nwarm and itt % p.tmeassure==0): # below is measuring every p.tmeasure steps
Nmeassure += 1 # new measurements
W = abs(fQ[0])+fQ[1] # this is the weight we are using
f0, f1 = fQ[0]/W, fQ[1]/W # the two measuring quantities
Pval[iQ] += f0 # V_physical : integral up to a constant
Pnorm += f1 # V_alternative : the normalization for the integral
Pnorm_sum += f1 # widetilde{V}_alternative, accumulated over all steps
Wphs = abs(f0) # widetilde{V}_{physical}, accumulated over all steps
Pval_sum += Wphs
# doing histogram of the simulation in terms of V_physical only.
# While the probability for a configuration is proportional to f(X)+V0*fm(X), the histogram for
# constructing g_i and h_{ij} is obtained from f(X) only.
mweight.Add_to_K_histogram(dk_hist*Wphs, momentum, p.cutoff, p.cutoff) # saving functions g and h on a mesh up to cutoff
if itt>10000 and itt % (p.recomputew*p.tmeassure) == 0 :
# Now we want to check if we should recompute g_i and h_{ij}
# P_v_P is V_physical/V_alternative*0.1
P_v_P = Pval_sum/Pnorm_sum * 0.1
# We expect V_physical/V_alternative*0.1=P_v_P to be of the order of 1.
# We do not want to change V0 too much, only if P_V_P falls outside the
# range [0.25,4], we should correct V0.
change_V0 = 0
if P_v_P < 0.25 and itt < adaptation_end: # But P_v_P above 0.25 is fine
change_V0 = -1 # V0 should be reduced
V0norm /= 2 # V0 is reduced by factor 2
#Pnorm /= 2 # V_alternative is proportional to V0, hence needs to be reduced too.
Pnorm_sum /= 2 # widetilde{V}_alternative also needs to be reduced
if P_v_P > 4.0 and itt < adaptation_end: # and P_v_P below 4 is also fine
change_V0 = 1 # V0 should be increased
V0norm *= 2 # actually increasing V0
#Pnorm *= 2
Pnorm_sum *= 2
if change_V0: # V0 was changed. Report that.
schange = ["V0 reduced to ", "V0 increased to"]
print( ' ', itt/1e6, 'M P_v_P=', P_v_P, schange[int( (change_V0+1)/2 )], V0norm )
# Here we decided to drop all prior measurements if V0 is changed.
# We could keep them, but the convergence can be better when we drop them.
Pval = zeros(len(Pval))
Pnorm = 0
Nmeassure = 0
fQ = (fQ[0], V0norm * mweight(momentum)) # refresh current weight
# Next we should check if g_i and h_ij need to be recomputed.
# This should not be done too often, and only in the first half of the sampling.
if (c_recompute==0 and itt<adaptation_end):
# At the beginning we recompute quite often, later not so often anymore
# as the per_recompute is increasing...
p.per_recompute = int(p.per_recompute*inc_recompute+0.5)
# We normalized f_m, hence all previous accumulated values are now of the order
# of 1/norm. We also normalize the new additions to histogram with similar value,
# but 5-times larger than before.
dk_hist *= 5*mweight.Normalize_K_histogram()
if dk_hist < 1e-8: # Once dk becomes too small, just start accumulating with weight 1.
dk_hist = 1.0
mweight.Recompute()# Here we actually recompute g_i and h_{ij}.
fQ = (fQ[0], V0norm * mweight(momentum)) # And now we must recompute V0*f_m, because f_m has changed!
c_recompute += 1
if c_recompute>=p.per_recompute : c_recompute = 0 # counting when we will recompute next.
if (itt+1)% p.Ncout == 0 : # This is just printing information
P_v_P = Pval_sum/Pnorm_sum * 0.1 if Pnorm_sum else float("nan")
Qa = qx[iQ] # current r0
ka = linalg.norm(momentum[1,:]) # current r1
print( '%9.2fM Q=%5.3f k=%5.3f fQ=%8.3g,%8.3g P_v_P=%10.6f' % (itt/1e6, Qa, ka, fQ[0], fQ[1], P_v_P) )
if Pnorm <= 0:
raise RuntimeError("No production measurements of the auxiliary weight; increase p.Nitt")
Pval *= len(qx) * V0norm / Pnorm # Finally, the integral is I = V0 *V_physical/V_alternative
# This would be true if we are returning one single value. But we are sampling len(qx) values
# And we jump between qx[i] uniformly, hence each value should be normalized with len(qx).
print( 'Total acceptance rate=', (Nacc_k+Nacc_q)/(p.Nitt+0.0), 'k-acceptance=', Nacc_k/(Nall_k+0.0), 'q-acceptance=', Nacc_q/(Nall_q+0.0))
print( 'k-trials=', Nall_k/(p.Nitt+0.0), 'q-trial=', Nall_q/(p.Nitt+0.0) )
return Pval
As a test, we use six three-component vectors and Gaussians of width $1/\sqrt{6}$. The first vector is an external argument: the integral is 15-dimensional, over the other five vectors. Averaging over the first vector's two angles adds two sampled coordinates, for 17 continuous sampling coordinates in total. The result should be a Gaussian of width 1.
from numpy import random
p = params()
fnc = FuncNDiag(width=1./sqrt(6), Ndim=6)
Nq = 30
qx = linspace( 3*0.5/Nq, 3*(Nq-0.5)/Nq, Nq)
Pval = IntegrateByMetropolis2(fnc, qx, p)
starting with f= (np.float64(0.010354275862946377), 5.321406330644421e-07)
starting momenta= [[0. 0. 1.15 ]
[0.11979084 0.19696522 0.08897511]
[0.30567617 0.41760521 0.4022511 ]
[0.33309162 0.24815911 0.28731882]
[0.44586331 0.55582516 0.20182261]
[0.11086426 0.208367 0.41056654]]
0.02 M P_v_P= 166.35273161637994 V0 increased to 0.04
0.04 M P_v_P= 7.2935672622739025 V0 increased to 0.08
0.05M Q=0.150 k=0.283 fQ= 1.33, 0.0141 P_v_P= 1.228165
0.10M Q=0.850 k=0.615 fQ= 4.29, 0.0641 P_v_P= 0.580863
0.15M Q=0.450 k=0.423 fQ= 0.0371,0.000118 P_v_P= 0.598797
0.20M Q=0.550 k=0.759 fQ= 0.0482,7.77e-07 P_v_P= 0.467203
0.25M Q=0.250 k=0.503 fQ= 16.9, 0.0144 P_v_P= 0.469204
0.30M Q=0.350 k=0.467 fQ= 0.235, 0.0124 P_v_P= 0.439544
0.35M Q=0.350 k=0.282 fQ= 11.6, 0.0481 P_v_P= 0.443240
0.40M Q=0.250 k=0.144 fQ= 0.00554,4.24e-06 P_v_P= 0.436239
0.45M Q=0.150 k=0.245 fQ= 0.326, 0.0482 P_v_P= 0.452828
0.50M Q=1.650 k=1.260 fQ= 0.13,6.23e-12 P_v_P= 0.429834
0.55M Q=0.450 k=0.363 fQ= 2.79, 0.258 P_v_P= 0.422642
0.60M Q=0.650 k=0.768 fQ= 19.2,2.23e-06 P_v_P= 0.430165
0.65M Q=0.450 k=0.558 fQ= 0.171, 0.00561 P_v_P= 0.424669
0.70M Q=0.650 k=0.938 fQ= 12.9, 0.0934 P_v_P= 0.414029
0.75M Q=0.650 k=0.492 fQ= 36.6, 3.75 P_v_P= 0.375948
0.80M Q=0.450 k=0.322 fQ= 0.736, 0.26 P_v_P= 0.338953
0.85M Q=1.050 k=0.486 fQ= 4.1, 0.0266 P_v_P= 0.338196
0.90M Q=0.650 k=0.778 fQ= 4.99,0.000804 P_v_P= 0.330408
0.95M Q=0.850 k=0.892 fQ= 0.021,2.71e-08 P_v_P= 0.376330
1.00M Q=0.150 k=1.296 fQ=5.22e-12,7.25e-06 P_v_P= 0.372676
Total acceptance rate= 0.727855 k-acceptance= 0.8172284671173556 q-acceptance= 0.282227795968944
k-trials= 0.832947 q-trial= 0.167053
We expect a Gaussian with unit width:
%matplotlib inline
plt.plot(qx,Pval, 'o-')
plt.plot(qx, exp(-qx**2));
Speed up by numba¶
We will speed up simulation using numba. All parts that are called every single step are being recast into numba functions.
@jit(nopython=True)
def TrialStep0(qx, momentum):
tiQ = int( random.rand()*len(qx) ) # trial iQ for qx[iQ]
Ka_new = qx[tiQ] # |r_0| length of the vector
u, phi = 2*random.rand()-1, 2*pi*random.rand() # uniform cos(theta) and azimuth
radial_xy = Ka_new * sqrt(1-u*u)
K_new = array([radial_xy*cos(phi), radial_xy*sin(phi), Ka_new*u])
trial_ratio = 1. # uniform solid-angle proposal
accept=True
return (K_new, Ka_new, trial_ratio, accept, tiQ)
@jit(nopython=True)
def TrialStep1(iloop,momentum,dkF,cutoff):
dk = (2*random.rand(3)-1)*dkF # change of k in cartesian coordinates of size p.dkF
K_new = momentum[iloop,:] + dk # K_new = K_old + dK
Ka_new = linalg.norm(K_new) # norm of the new vector
trial_ratio = 1. # trial step probability is just unity
accept = Ka_new <= cutoff # we might reject the step if the point is too far from the origin
return (K_new, Ka_new, trial_ratio, accept)
@jit(nopython=True)
def Give_new_X(momentum, K_new, iloop):
tmomentum = copy(momentum)
tmomentum[iloop,:] = K_new # this is trial configuration X_{new}=momentum
return tmomentum
The function, which is being evaluated, will also be accelerated with Numba
@jit(nopython=True)
def cmpf(momentum, width, cnrm):
kn = linalg.norm( momentum[-1] )
res = exp( -(kn/width)**2 )/cnrm
for i in range(len(momentum)-1):
dk = linalg.norm( momentum[i+1]-momentum[i] )
res *= exp( -(dk/width)**2 )
return res
class FuncNDiag2:
""" Gaussian through all diagonals k_i=k_j, i.e.:
We have the following variables : k_0, k_1, k_2, ... k_{N-1}
The function is
fPQ = exp(-|k_{N-1}|^2/width^2) * exp(-|k_{N-2}-k_{N-1}|^2/width^2) * exp(-|k_{N-3}-k_{N-2}|^2/width^2) *...* exp(-|k_1-k_0|^2/width^2) * normalization
We integrate only over k_1,k_2,...k_{N-1} and keep k_0 as external independent variable.
We want the final result to be
exp(-k_0^2/(width^2*N)) = Integrate[ fPQ d^3k_1 d^3k_2....d^3k_{N-1} ]
Hence the normalization is
normalization = N^(3/2) / ( sqrt(pi)*width )^(3(N-1))
"""
def __init__(self, width=1, Ndim=1):
self.width = width # width of gaussians
self.Ndim = Ndim
self.cnrm = ((sqrt(pi)*self.width)**3 )**(Ndim-1)/sqrt(Ndim)**3 # integral of gaussian convolution
def __call__(self, momentum):
return cmpf(momentum, self.width, self.cnrm)
Checking that these Numba functions work.
from numpy import random
momentum = ones((4,3))
Nq = 30
qx = linspace( 3*0.5/Nq, 3*(Nq-0.5)/Nq, Nq)
TrialStep0(qx, momentum)
TrialStep1(2,momentum,0.2,10.)
print(Give_new_X(momentum, array([0.1,0.2,0.3]), 3))
print(momentum)
[[1. 1. 1. ] [1. 1. 1. ] [1. 1. 1. ] [0.1 0.2 0.3]] [[1. 1. 1.] [1. 1. 1.] [1. 1. 1.] [1. 1. 1.]]
Finally, using these Numba function in the Metropolis routine. We will also time steps, to understand if the code is optimized.
import time
def IntegrateByMetropolis3(func, qx, p):
""" Integration by Metropolis:
func(momentum) -- function to integrate
qx -- mesh given by a user
p -- other parameters
Output:
Pval(qx)
"""
tm1 = time.time()
random.seed(0) # make sure that we always get the same sequence of steps
# Next line needs CORRECTION for homework
Pval = zeros(len(qx)) # Final results V_physical is stored in Pval
Pnorm = 0.0 # V_alternative is stored in Pnorm
Pval_sum = 0.0 # this is widetilde{V_physical}
Pnorm_sum = 0.0 # this is widetilde{V_alternative}
V0norm = p.V0norm # this is V0
dk_hist = 1.0 # we are creating histogram by adding each configuration with weight 1.
Ndim = func.Ndim # dimensions of the problem
inc_recompute = (p.per_recompute+0.52)/p.per_recompute # How often to self-consistently recompute
# the weight functions g_i and h_{ij}.
momentum = zeros((Ndim,3)) # contains all variables (r1,r2,r3,....r_Ndim)
# We call them momentum here, but could be real space vectors or momentum space vectors.
iQ = int(len(qx)*random.rand()) # which bin do we currently visit for r0, iQ is current r0=qx[iQ]
momentum[1:,:] = random.random((Ndim-1,3)) * p.kF / sqrt(3.) # Initial guess for r1,r2,....r_N is random
momentum[0,:] = [0,0,qx[iQ]] # initial configuration for r_0 has to be consistent with iQ, and will be in z-direction
# This is fm function, which is defined in mweight.py module
mweight = meassureWeight(p.dexp, p.cutoff, p.kF, p.Nbin, Ndim) # measuring function fm in alternative space
# fQ on the current configuration. Has two components (f(X), V0*f_m(X))
fQ = func(momentum), V0norm * mweight( momentum ) # fQ=(f(X), V0*f_m(X))
#print('starting with f=', fQ, '\nstarting momenta=', momentum)
t_sim, t_mes, t_prn, t_rec = 0.,0.,0.,0.
Nmeassure = 0 # How many measurements we had?
Nall_q, Nall_k, Nacc_q, Nacc_k = 0, 0, 0, 0
c_recompute = 0 # when to recompute the auxiliary function?
adaptation_end = min(p.Nitt-1, max(p.Nwarm, int(0.7*p.Nitt)))
for itt in range(p.Nitt): # adaptation followed by fixed-weight production
t0 = time.time()
iloop = int( Ndim * random.rand() ) # which variable to change, iloop=0 changes external r_0
accept = False
if (iloop == 0): # changing external variable : r_0==Q
Nall_q += 1 # how many steps changing external variable
(K_new, Ka_new, trial_ratio, accept, tiQ) = TrialStep0(qx, momentum)
else: # changing momentum ik>0
Nall_k += 1 # how many steps of this type
(K_new, Ka_new, trial_ratio, accept) = TrialStep1(iloop,momentum,p.dkF,p.cutoff)
if (accept): # trial step successful. We did not yet accept, just the trial step.
#tmomentum = Give_new_X(momentum, K_new, iloop)
K_old = copy(momentum[iloop])
momentum[iloop] = K_new # this is trial configuration X_{new}=momentum
fQ_new = func(momentum), V0norm * mweight(momentum) # f_new
# Notice that we take |f_new(X)+V0*fm_new(X)|/|f_old(X)+V0*fm_old(X)| * trial_ratio
# Next line needs CORRECTION for homework
ratio = (abs(fQ_new[0])+fQ_new[1])/(abs(fQ[0])+fQ[1]) * trial_ratio
accept = abs(ratio) > 1-random.rand() # Metropolis
if accept: # the step succeeded
#momentum[iloop] = K_new
fQ = fQ_new
if iloop==0:
Nacc_q += 1 # how many accepted steps of this type
iQ = tiQ # the new external variable index
else:
Nacc_k += 1 # how many accepted steps of this type
else:
momentum[iloop] = K_old # We are backtracking
t1 = time.time()
t_sim += t1-t0
if itt == adaptation_end:
# Start production with the final fixed weight and fresh estimates.
Pval[:] = 0
Pnorm = Pval_sum = Pnorm_sum = 0.0
Nmeassure = 0
if (itt >= p.Nwarm and itt % p.tmeassure==0): # below is measuring every p.tmeasure steps
Nmeassure += 1 # new measurements
# Next line needs CORRECTION for homework
W = abs(fQ[0])+fQ[1] # this is the weight we are using
f0, f1 = fQ[0]/W, fQ[1]/W # the two measuring quantities
# Next line needs CORRECTION for homework
Pval[iQ] += f0 # V_physical : integral up to a constant
Pnorm += f1 # V_alternative : the normalization for the integral
Pnorm_sum += f1 # widetilde{V}_alternative, accumulated over all steps
# Next line needs CORRECTION for homework
Wphs = abs(f0) # widetilde{V}_{physical}, accumulated over all steps
Pval_sum += Wphs
# doing histogram of the simulation in terms of V_physical only.
# While the probability for a configuration is proportional to f(X)+V0*fm(X), the histogram for
# constructing g_i and h_{ij} is obtained from f(X) only.
mweight.Add_to_K_histogram(dk_hist*Wphs, momentum, p.cutoff, p.cutoff)
if itt>10000 and itt % (p.recomputew*p.tmeassure) == 0 :
# Now we want to check if we should recompute g_i and h_{ij}
# P_v_P is V_physical/V_alternative*0.1
P_v_P = Pval_sum/Pnorm_sum * 0.1
# We expect V_physical/V_alternative*0.1=P_v_P to be of the order of 1.
# We do not want to change V0 too much, only if P_V_P falls outside the
# range [0.25,4], we should correct V0.
change_V0 = 0
if P_v_P < 0.25 and itt < adaptation_end: # But P_v_P above 0.25 is fine
change_V0 = -1 # V0 should be reduced
V0norm /= 2 # V0 is reduced by factor 2
Pnorm /= 2 # V_alternative is proportional to V0, hence needs to be reduced too.
Pnorm_sum /= 2 # widetilde{V}_alternative also needs to be reduced
if P_v_P > 4.0 and itt < adaptation_end: # and P_v_P below 4 is also fine
change_V0 = 1 # V0 should be increased
V0norm *= 2 # actually increasing V0
Pnorm *= 2
Pnorm_sum *= 2
if change_V0: # V0 was changed. Report that.
schange = ["V0 reduced to ", "V0 increased to"]
print('%9.2fM P_v_P=%10.6f' % (itt/1e6, P_v_P), schange[int( (change_V0+1)/2 )], V0norm )
# Here we decided to drop all prior measurements if V0 is changed.
# We could keep them, but the convergence can be better when we drop them.
# Next line needs CORRECTION for homework
Pval = zeros(shape(Pval))
Pnorm = 0
Nmeassure = 0
fQ = (fQ[0], V0norm * mweight(momentum)) # refresh current weight
# Next we should check if g_i and h_ij need to be recomputed.
# This should not be done too often, and only in the first half of the sampling.
if (c_recompute==0 and itt<adaptation_end):
t5 = time.time()
# At the beginning we recompute quite often, later not so often anymore
# as the per_recompute is increasing...
p.per_recompute = int(p.per_recompute*inc_recompute+0.5)
# We normalized f_m, hence all previous accumulated values are now of the order
# of 1/norm. We also normalize the new additions to histogram with similar value,
# but 5-times larger than before.
dk_hist *= 5*mweight.Normalize_K_histogram()
if dk_hist < 1e-8: # Once dk becomes too small, just start accumulating with weight 1.
dk_hist = 1.0
mweight.Recompute()# Here we actually recompute g_i and h_{ij}.
fQ = func(momentum), V0norm * mweight( momentum ) # And now we must recompute V0*f_m, because f_m has changed!
t6 = time.time()
print('%9.2fM recomputing f_m=%10.6f' % (itt/1e6, fQ[1]))
t_rec += t6-t5
c_recompute += 1
if c_recompute>=p.per_recompute : c_recompute = 0 # counting when we will recompute next.
t2 = time.time()
t_mes += t2-t1
if (itt+1)% p.Ncout == 0 : # This is just printing information
P_v_P = Pval_sum/Pnorm_sum * 0.1 if Pnorm_sum else float("nan")
Qa = qx[iQ] # current r0
ka = linalg.norm(momentum[1,:]) # current r1
# Next line needs CORRECTION for homework
print( '%9.2fM Q=%5.3f k=%5.3f fQ=%8.3g,%8.3g P_v_P=%10.6f' % (itt/1e6, Qa, ka, fQ[0], fQ[1], P_v_P) )
t3 = time.time()
t_prn += t3-t2
if Pnorm <= 0:
raise RuntimeError("No production measurements of the auxiliary weight; increase p.Nitt")
Pval *= len(qx) * V0norm / Pnorm # Finally, the integral is I = V0 *V_physical/V_alternative
# This would be true if we are returning one single value. But we are sampling len(qx) values
# And we jump between qx[i] uniformly, hence each value should be normalized with len(qx).
tp1 = time.time()
print('Total acceptance rate=', (Nacc_k+Nacc_q)/(p.Nitt+0.0), 'k-acceptance=', Nacc_k/(Nall_k+0.0), 'q-acceptance=', Nacc_q/(Nall_q+0.0))
print('k-trials=', Nall_k/(p.Nitt+0.0), 'q-trial=', Nall_q/(p.Nitt+0.0) )
print('t_simulate=%6.2f t_meassure=%6.2f t_recompute=%6.2f t_print=%6.2f t_total=%6.2f' % (t_sim, t_mes-t_rec, t_rec, t_prn, tp1-tm1))
return (Pval,mweight)
from numpy import random
p = params()
p.Nitt = 3000000
Ndim = 6
width = 1./sqrt(Ndim)
fnc = FuncNDiag2(width, Ndim)
Nq = 30
qx = linspace( 3*0.5/Nq, 3*(Nq-0.5)/Nq, Nq)
(Pval,mweight) = IntegrateByMetropolis3(fnc, qx, p)
0.02M P_v_P= 38.077032 V0 increased to 0.04
0.02M recomputing f_m= 0.023312
0.04M P_v_P= 5.170865 V0 increased to 0.08
0.05M Q=1.050 k=1.310 fQ= 0.0058,6.22e-42 P_v_P= 1.231652
0.10M Q=0.650 k=0.956 fQ= 0.753,5.12e-08 P_v_P= 0.597675
0.15M Q=0.650 k=0.511 fQ= 0.149, 0.00178 P_v_P= 0.472796
0.18M recomputing f_m= 0.056287
0.20M Q=0.650 k=0.470 fQ= 0.97, 0.00974 P_v_P= 0.409043
0.25M Q=0.250 k=0.363 fQ= 17.5, 0.231 P_v_P= 0.427650
0.30M Q=0.750 k=0.433 fQ= 0.0791,0.000177 P_v_P= 0.438164
0.35M Q=0.750 k=0.728 fQ= 0.661,0.000248 P_v_P= 0.473321
0.36M recomputing f_m= 0.076438
0.40M Q=0.150 k=0.520 fQ= 0.864, 0.213 P_v_P= 0.466841
0.45M Q=0.750 k=0.641 fQ= 0.0113,0.000361 P_v_P= 0.467796
0.50M Q=0.150 k=0.558 fQ= 0.149,1.16e-08 P_v_P= 0.460545
0.55M Q=0.550 k=0.900 fQ= 0.761, 0.0199 P_v_P= 0.464321
0.56M recomputing f_m= 0.124415
0.60M Q=0.450 k=0.389 fQ= 0.0529,4.17e-05 P_v_P= 0.468060
0.65M Q=0.650 k=0.438 fQ= 55.3, 0.505 P_v_P= 0.442192
0.70M Q=0.250 k=0.622 fQ= 0.069, 0.0018 P_v_P= 0.425375
0.75M Q=2.750 k=0.888 fQ=4.64e-15, 0.00302 P_v_P= 0.403362
0.78M recomputing f_m= 0.001986
0.80M Q=0.350 k=0.529 fQ= 0.121,2.08e-06 P_v_P= 0.403826
0.85M Q=1.050 k=1.168 fQ= 0.226,3.92e-17 P_v_P= 0.390127
0.90M Q=0.050 k=0.203 fQ= 14.8, 0.279 P_v_P= 0.393060
0.95M Q=0.650 k=0.496 fQ= 2.19, 0.00285 P_v_P= 0.388328
1.00M Q=1.550 k=1.422 fQ= 0.0949,4.14e-11 P_v_P= 0.387085
1.02M recomputing f_m= 0.000000
1.05M Q=0.350 k=0.674 fQ= 2.23, 0.511 P_v_P= 0.384588
1.10M Q=0.250 k=0.764 fQ= 16.4, 0.00114 P_v_P= 0.380906
1.15M Q=0.550 k=0.482 fQ= 16.8,0.000524 P_v_P= 0.380055
1.20M Q=0.650 k=0.772 fQ= 1.36,8.93e-05 P_v_P= 0.381777
1.25M Q=0.250 k=0.710 fQ= 2.59, 0.00147 P_v_P= 0.378774
1.28M recomputing f_m= 0.940142
1.30M Q=0.650 k=0.345 fQ= 1.08, 1.78 P_v_P= 0.366960
1.35M Q=0.450 k=0.898 fQ= 0.0921,5.74e-08 P_v_P= 0.359753
1.40M Q=1.050 k=0.786 fQ= 0.446,5.12e-06 P_v_P= 0.363403
1.45M Q=0.950 k=0.745 fQ= 0.688,1.95e-05 P_v_P= 0.361609
1.50M Q=1.750 k=1.236 fQ= 0.148, 7.3e-08 P_v_P= 0.369402
1.55M Q=1.350 k=0.938 fQ= 0.0638, 3.3e-07 P_v_P= 0.367101
1.56M recomputing f_m= 0.002710
1.60M Q=0.050 k=0.121 fQ= 0.91,0.000627 P_v_P= 0.369435
1.65M Q=0.850 k=1.163 fQ= 0.00649,8.77e-12 P_v_P= 0.369192
1.70M Q=2.550 k=0.476 fQ=2.54e-13, 0.0813 P_v_P= 0.367812
1.75M Q=0.450 k=0.630 fQ= 24.4, 0.00607 P_v_P= 0.368895
1.80M Q=0.750 k=0.502 fQ= 0.0108,9.17e-07 P_v_P= 0.367946
1.85M Q=1.450 k=1.392 fQ= 0.441,1.29e-07 P_v_P= 0.369967
1.86M recomputing f_m= 0.329367
1.90M Q=0.550 k=1.069 fQ= 0.231,1.38e-09 P_v_P= 0.368746
1.95M Q=0.050 k=0.557 fQ= 0.0734,1.39e-06 P_v_P= 0.371233
2.00M Q=0.250 k=0.117 fQ= 1.07,0.000718 P_v_P= 0.368296
2.05M Q=0.050 k=0.234 fQ= 0.0341, 0.00018 P_v_P= 0.364906
2.10M Q=1.450 k=1.387 fQ= 0.278,5.38e-11 P_v_P= 0.362080
2.15M Q=0.550 k=0.646 fQ= 0.478,4.61e-06 P_v_P= 0.451072
2.20M Q=2.150 k=0.425 fQ=7.32e-16,0.000155 P_v_P= 0.333293
2.25M Q=0.050 k=0.215 fQ= 13.2, 3.02 P_v_P= 0.299682
2.30M Q=0.250 k=0.248 fQ= 4.74, 0.00041 P_v_P= 0.336661
2.35M Q=2.550 k=0.112 fQ=9.35e-20, 2.11 P_v_P= 0.369136
2.40M Q=0.850 k=1.057 fQ= 4.06,9.75e-05 P_v_P= 0.375645
2.45M Q=2.550 k=1.460 fQ=2.87e-48,7.85e-06 P_v_P= 0.344133
2.50M Q=1.150 k=1.221 fQ= 14.6, 4.2e-06 P_v_P= 0.373481
2.55M Q=1.050 k=0.828 fQ= 0.414,2.02e-05 P_v_P= 0.394234
2.60M Q=0.050 k=0.351 fQ= 0.839,0.000111 P_v_P= 0.376308
2.65M Q=0.550 k=0.491 fQ= 11.1, 0.00317 P_v_P= 0.377960
2.70M Q=0.150 k=0.371 fQ= 17.3, 0.00743 P_v_P= 0.373365
2.75M Q=0.350 k=0.136 fQ= 109, 12.5 P_v_P= 0.373851
2.80M Q=1.350 k=0.484 fQ= 0.00039, 0.698 P_v_P= 0.367397
2.85M Q=0.050 k=0.616 fQ= 14.9, 0.0306 P_v_P= 0.376282
2.90M Q=0.550 k=0.880 fQ= 0.00215,6.08e-10 P_v_P= 0.372476
2.95M Q=0.150 k=0.163 fQ= 0.0401,1.56e-07 P_v_P= 0.388285
3.00M Q=0.250 k=0.519 fQ= 0.179,1.47e-07 P_v_P= 0.389491
Total acceptance rate= 0.73076 k-acceptance= 0.8176526296458263 q-acceptance= 0.29695605363609673
k-trials= 0.8331223333333333 q-trial= 0.16687766666666667
t_simulate= 13.09 t_meassure= 9.24 t_recompute= 7.65 t_print= 0.32 t_total= 30.62
%matplotlib inline
plt.plot(qx,Pval, 'o-')
plt.plot(qx, exp(-qx**2));
Next plotting the auxiliary function $f_m$ projections $g(r)$ to all $r$.
gx = mweight.gx
for ik in range(len(gx)):
plt.plot(linspace(0,p.cutoff,shape(gx)[1]), gx[ik,:])
Here is the auxiliary function $f_m$ for convolutions $h(r)$ versus $r$.
hx = mweight.gx_off
for ik in range(len(hx)):
plt.plot(linspace(0,p.cutoff,shape(gx)[1]), hx[ik,:])
1D Convolutions¶
The power of Metropolis integration is that we have freedom to pick an appropriate normalized function. This can come from physical intuition into processes being modeled. In most physical process the convolutions (correlations between particles) turn out to be important, hence convolution type ansatz considerably improves the precision. The convolutions can still be worked out analytically, even though they are more tedious to derive.
To derive the integral, we will concentrate on a specific form of convolution,i.e., \begin{eqnarray} f_m(x_1,x_2,\cdots,x_n)= \sum_{j=1}^n g_j(x_j)\prod_{i=1,i\ne j}^n g_i(x_i) h_{ij}(x_j-x_i) \end{eqnarray} As before, the two functions can be determined self-consistently by projections \begin{eqnarray} &g_i(x)=&\int dy_1 dy_2\cdots dy_n |f(y_1,y_2,\cdots,y_n)|\delta(y_i-x)\\ &h_{ij}(x_j-x_i)=&\int dy_1 dy_2\cdots dy_n |f(y_1,y_2,\cdots,y_n)|\delta(x_j-x_i-(y_j-y_i)) \end{eqnarray}
To normalize $f_m$ we need to evaluate the integral \begin{eqnarray} \int dx_1\cdots dx_n f_m = \sum_{j=1}^n \int dx_j g(x_j) \prod_{i\ne j}^{n} \int dx_i g_i(x_i) h_{ij}(x_j-x_i) \end{eqnarray} Without loss of generality, we will work out one term in the sum, namely, \begin{eqnarray} I^N = \int dx_N g(x_N) \prod_{i\ne N} \int dx_i g_i(x_i) h_{i N}(x_N-x_i) \end{eqnarray} so that the end result is \begin{eqnarray} \int dx_1\cdots dx_n f_m = \sum_j I^j \end{eqnarray}
This integral is cumbersome because all the functions are piecewise constant, which leads to somewhat lengthy derivations. We can write $x_N= \Delta (j_N + t)$, $x_i = \Delta(j_i + u)$ with $t\in[0,1]$ and $u\in[0,1]$ and $j_i$ integers. Note that $g(\Delta(j+u))=g[j]$ for any $u\in [0,1]$. For simplicity, below we will drop $\Delta$ inside function arguments, i.e., $g(\Delta(j+u))\equiv g(j+u)$
The integral can thus be turned into \begin{eqnarray} \int f_m = \Delta \sum_{j_N} \int_0^1 dt g(j_N+t) \prod_{i=1}^{N-1} \Delta \sum_{j_i} \int_0^1 du g_i(j_i+u) h_i(j_N+t-j_i-u) \\ =\Delta^N \sum_{j_N} g[j_N] \int_0^1 dt \prod_{i=1}^{N-1} \sum_{j_i} g_i[j_i] \int_0^1 du\; h_i(j_N-j_i+t-u) \end{eqnarray} Since both $t$ and $u$ are in the interval $[0,1]$, $t-u$ is in the interval $[-1,1]$, and there are two possibilities,
- $t-u<0$ $\rightarrow$ $h_i(j_N-j_i+t-u)=h_i[j_N-j_i-1]$
- $t-u>0$ $\rightarrow$ $h_i(j_N-j_i+t-u)=h_i[j_N-j_i]$
we thus recognize \begin{eqnarray} \int_0^1 du\; h_i(j_N-j_i+t-u) = \int_0^1 du\; \left(\begin{array}{c} h_i[j_N-j_i] \Theta(0<u<t)) \\ h_i[j_N-j_i-1] \Theta(t<u<1) \end{array}\right) \\ =h_i[j_N-j_i-1] (1-t) + h_i[j_N-j_i] t %\\=h_i[j_N-j_i] + (h_i[j_N-j_i-1]-h_i[j_N-j_i])(1-t) \end{eqnarray}
We can define new arrays \begin{eqnarray} a_i[j_N] &=& \Delta \sum_j g_i[j] h_i[j_N-j-1] \\ b_i[j_N] &=& \Delta \sum_j g_i[j] (h_i[j_N-j]-h_i[j_N-j-1])\\ \end{eqnarray} to obtain the final integral \begin{eqnarray} I^N =\Delta \sum_{j_N} g[j_N] \int_0^1 dt \prod_{i=1}^{N-1} \left( a_i[j_N] + b_i[j_N] t \right) \end{eqnarray} which can be expanded to a polynomial of $N-1$-th order, and evaluated \begin{eqnarray} I^N =\Delta \sum_{j_N} g[j_N] \left( \prod_{i=1}^{N-1} a_i[j_N]+ \cdots + \frac{1}{N}\prod_{i=1}^{N-1} b_i[j_N] \right) \end{eqnarray} Once we know the integral $\int f_m$, we scale all $h_i$ by $h_i \rightarrow \frac{h_i}{(\int f_m)^{1/(N-1)}}$
3D convolutions¶
Multiple 3D-type integrals are very common, and deserve special attention. It is often physically more appropriate to write the ansatz in terms of radial functions $g(|\vec{r}_i|)$ rather than use separate $g(x)$, $g(y)$, $g(z)$. We might want to use a convolution ansatz of the form \begin{eqnarray} f_m(\vec{r}_1,\vec{r}_2,\cdots,\vec{r}_n)= g_1(r_1) h_1(|\vec{r}_n-\vec{r}_1|) g_2(r_2)h_2(|\vec{r}_n-\vec{r}_2|)\cdots g_n(r_n) \end{eqnarray} The histogram for projections to $|\vec{r}_i|$ and $|\vec{r}_n-\vec{r}_i|$ is straightforward to obtain during simulation.
The analytic integral $\int f_m$ is somewhat more challenging for 3D case. We derive it below: \begin{eqnarray} \int f_m = \int d^3r_n g_n(r_n)\prod_i \int d^3 r_i g_i(r_i) h_i(|\vec{r}_n-\vec{r}_i|) \\= 4\pi \int d r_n r_n^2 g_n(r_n)\prod_{i=1}^{n-1}\int dr_i 2\pi r_i^2 \\ \int_{-1}^1 d(\cos\theta)g_i(r_i) h_i(\sqrt{r_n^2+r_i^2-2 r_n r_i \cos(\theta)}) \end{eqnarray}
\begin{eqnarray} \int f_m = 2 (2\pi)^n \int d r_n r_n^{3-n} g_n(r_n)\prod_{i=1}^{n-1}\int dr_i r_i g_i(r_i) \int_{|r_n-r_i|}^{r_n+r_i} dx\, x\, h_i(x) \end{eqnarray} Next we integrate over piecewise constant functions \begin{eqnarray} r_n = j_n + t\\ r_i = j + u \end{eqnarray} with $t\in[0,1]$ and $u\in[0,1]$, and we get \begin{eqnarray} &&\int f_m = 2 (2\pi\Delta^3)^n \sum_{j_n} g_n[j_n]\int_0^1 dt (j_n+t)^{3-n}\times \nonumber\\ && \times \prod_{i=1}^{n-1}\sum_j g_i[j] \int_0^1 du (j+u) \int_{|j_n-j+t-u|}^{j_n+j+t+u} dx\, x\, h_i(x) \end{eqnarray} Let us define \begin{eqnarray} F_i(j_n+t) \equiv \sum_j g_i[j] \int_0^1 du (j+u) \int_{|j_n-j+t-u|}^{j_n+j+t+u} dx\, x\, h_i(x) \end{eqnarray} and by power counting we can see that $F_i(t)$ is polynomial in $t$ of the fourth order.
The derivation of polynomials $F_i[j_n](t)$ is somewhat tedious and will be given below in Sec.(Integrals $K_n$). But before that, let us show how to compute the integral $\int f_m$ if the polynomials $F_i[j_n](t)$ are given: \begin{eqnarray} \int f_m = 2 (2\pi\Delta^3)^n \sum_{j_n} g_n[j_n]\int_0^1 dt (j_n+t)^{3-n} \prod_{i=1}^{n-1} F_i[j_n](t) \label{Eq:31} \end{eqnarray} Note that $\prod_{i=1}^{n-1} F_i[j_n](t)$ is a polynomial of $4(n-1)$-th order, and we write it as \begin{eqnarray} \prod_{i=1}^{n-1} F_i[j_n](t) \equiv \sum_{k=0}^{4(n-1)} a_k t^k \end{eqnarray} Such multiplication of polynomials can be straightforwardly implemented on the computer, and if polynomials $F_i[j_n](t)$ are known, the coefficients $a_k$ are easy to determine.
The integral of the function $f_m$ then requires one to evaluate \begin{eqnarray} K_n[j_n]= \int_0^1 dt (j_n+t)^{3-n} \sum_{k=0}^{4(n-1)} a_k t^k \end{eqnarray} so that the final result becomes \begin{eqnarray} \int f_m =2 (2\pi\Delta^3)^n \sum_{j_n} g_n[j_n] K_n[j_n] \end{eqnarray}
Integrals $K_n$¶
For $n \le 3$ the exponent $3-n$ is nonnegative, so the binomial expansion is finite and we can write \begin{eqnarray} K_n[j]= \sum_{p=0}^{3-n} {3-n\choose p}(j)^p \sum_{k=0}^{4(n-1)} a_k \int_0^1 dt\, t^{3-n-p+k} \\= \sum_{p=0}^{3-n} {3-n\choose p} (j)^p \sum_{k=0}^{4(n-1)} \frac{a_k}{4+k-n-p} \end{eqnarray} For $n=4$ we have \begin{eqnarray} K_n[j]= \sum_{k=0}^{4(n-1)} a_k \int_0^1 dt \frac{t^k}{j+t} \end{eqnarray} which can be computed by recursion. Let's define \begin{eqnarray} I_k[j]\equiv \int_0^1 dt \frac{t^k}{j+t} \end{eqnarray} so that \begin{eqnarray} K_n[j]= \sum_{k=0}^{4(n-1)} a_k I_k[j] \end{eqnarray} It is easy to see that $I_0[j]=\log(\frac{j+1}{j})$ and that $$I_{k+1}[j]=\int_0^1 t^k dt - j I_k[j]= \frac{1}{k+1} - j I_k[j]$$ which gives $$I_k[j] = \sum_{p=0}^{k-1}\frac{ (-j)^p}{k-p} + (-j)^k \log(\frac{j+1}{j})$$
Finally, for $n>4$, we define $$ I^p_k[j] = \int_0^1 \frac{t^k}{(j+t)^{p+1}} dt$$ so that $K_n$ can be simply computed by \begin{eqnarray} K_n[j_n]= \sum_{k=0}^{4(n-1)} a_k I_k^{n-4}[j_n] \end{eqnarray} and we derive the recursion relation for integrals $I_k^p[j]$. Notice that the previous case $n=4$ corresponds to $p=0$, but now we will derive recursion for any $n \ge 4$.
We notice that \begin{eqnarray} I_{k+1}^p= I_k^{p-1}- j\, I_k^p, \label{Eq:recursion} \end{eqnarray} which follows from the definition \begin{eqnarray} I^p_{k+1} = \int_0^1 \frac{t^k(t+j-j)}{(j+t)^{p+1}} dt = \int_0^1 \frac{t^k}{(j+t)^{p}} dt -j\int_0^1 \frac{t^k}{(j+t)^{p+1}} dt \end{eqnarray} This can be used to compute any $I_k^p$ if we know $I^{-1}_k$, which is simply given by $$I^{-1}_k=\frac{1}{k+1}$$ and $I_0^p$ for arbitrary $p$. We notice that \begin{eqnarray} I^{p>0}_{0} = \int_0^1 \frac{1}{(j+t)^{p+1}} dt = \frac{1}{p}\left(\frac{1}{j^p}-\frac{1}{(j+1)^p}\right) \end{eqnarray} and $I^0_0 = \log\left(\frac{j+1}{j}\right)$ hence the above recursion gives an arbitrary $I_k^p$.
To show that all $I_k^p$ are now determined, let us show this for the first few $p$. For $p=0$ we get \begin{eqnarray} I^0_{k+1}= I^{-1}_k - j I^0_k = \frac{1}{k+1} - j I^0_k \end{eqnarray} which is exactly the recursion relation we derived earlier. Once all $I^0_k$ are determined, we can proceed to compute $I^1_{k}$ by the recursion \begin{eqnarray} I^1_{k+1}= I^{0}_k - j I^1_k \end{eqnarray} Since we know $I^1_0$, all $I^1_k$ can readily be obtained from this recursion relation. And once $I^1_k$ are known, $I^2_k$ are determined by the recursion relation specified above $I_{k+1}^p= I_k^{p-1}- j\, I_k^p$
Homework¶
Using Metropolis integration evaluate the following Lindhard function:
\begin{eqnarray} P(\Omega,\vec{q}) = -2 \int \frac{d^3k}{(2\pi)^3} \frac{f(\varepsilon_{\vec{k}+\vec{q}})-f(\varepsilon_{\vec{k}})}{\Omega-\varepsilon_{\vec{k}+\vec{q}}+\varepsilon_\vec{k}+i\delta} \end{eqnarray}
Here $\varepsilon_\vec{k}=k^2-k_F^2$.
We will use $k_F=\frac{(\frac{9\pi}{4})^{1/3}}{rs}$ with $r_s=2$, $f(x) = \frac{1}{\exp(x/T)+1}$, $T=0.02 k_F^2$, $\delta = 0.002 k_F^2$, and cutoff is $3 k_F$.
We will use linear mesh of frequency $\Omega=[0,k_F^2]$ with 100 points, and $q$ mesh $q=[0.1 k_F,0.2 k_F,0.3 k_F,0.4 k_F]$. We will plot the family of curves for $P(\Omega,q)$.
We will run for p.Nitt=5000000 steps.
The result for $P(\Omega=0,q<< k_F)$ should be close to $-n_F$, where $n_F = \frac{k_F}{2\pi^2}$.
We will use Lindhard function from previous homework, but slightly modify it, so that the input momentum contains $\vec{q}$ as the first vector and $\vec{k}$ as the second vector. (The dimension Ndim will thus be set to 2.) The function will return an array of values, corresponding to all frequencies.
The Metropolis algorithm has to be modified so that it takes an array of values. The probability will be proportional to the value at zero frequency $P(\Omega=0)$, but we will measure all frequencies at the same time.
Here we summarize all the necessary changes to the IntegrateByMetropolis3 routine¶
We marked all lines that require change by
# Next line needs CORRECTION for homework
Pval[iq,iOm]becomes $q$ and $\Omega$ array.When we compute ratio, we need to take only the zero frequency value of the function, i.e.,
abs(fQ_new[0][0])andfQ[0][0].In measurement, the weight
Wshould depend only zero frequency value only, to cancel the probability from the Metropolis, i.e.,abs(fQ[0][0])When measuring, we need to properly update the values
Pval[iQ,:]+= f0.The physical weight $\widetilde{V}_{physical}$ for determining if
V0is of the right magnitude, needs to be changed so that it depends on zero frequency onlyf0[0]When we reset the stored values in
Pval, we need to create array of proper size and typePval = zeros(shape(Pval), dtype=complex)Printing should be modified, for example
ratiohas to be correctly modified to depend on zero frequency only, and only the zero frequency value of the function is printed out.