betaFeedback

WorksPhysics and Astronomy

Adaptive sampling accelerates the hybrid deviational particle simulations

Abstract

To avoid ineffective collisions between the equilibrium states, the hybrid method with deviational particles (HDP) has been proposed to integrate the Vlasov-Poisson-Landau system, while leaving a new issue in sampling deviational particles from the high-dimensional source term. In this paper, we present an adaptive sampling (AS) strategy that first adaptively reconstructs a piecewise constant approximation of the source term based on sequential clustering via discrepancy estimation, and then samples deviational particles directly from the resulting adaptive piecewise constant function without rejection. The mixture discrepancy, which can be easily calculated thanks to its explicit analytical expression, is employed as a measure of uniformity instead of the star discrepancy the calculation of which is NP-hard. The resulting method, dubbed the HDP-AS method, samples deviational particles through adaptive sampling instead of the acceptance-rejection method in the original HDP method. In the Landau damping, two stream instability, bump on tail and Rosenbluth's test problems, the HDP-AS method runs approximately ten times faster than the HDP method while keeping the same accuracy.

Introduction

As a fundamental mathematical model for the kinetic theory, the Vlasov–Poisson–Landau (VPL) system

∂tf+v⋅∇xf−E⋅∇vf=Q(f,f),−∇x⋅E=ρ(x,t),(1)\begin{aligned} \partial_t f + v \cdot\nabla_x f - E \cdot\nabla_v f &= Q(f,f),\\ -\nabla_x \cdot E &= \rho(x,t), \tag*{(1)} \end{aligned}

describes the evolution of the charged particles in phase space (x,v)∈R3×R3(x,v) \in\mathbb{R}^3 \times\mathbb{R}^3 [1, 2], where f=f(x,v,t)f=f(x,v,t) gives the time-dependent distribution function, ρ(x,t)=∫R3f(x,v,t) dv\rho(x,t)=\int_{\mathbb{R}^3} f(x,v,t)\,\mathrm{d}v the spatial density and Q(f,f)Q(f,f) the Landau collision operator. The form of the VPL system (1) adopted in this paper is consistent with that presented in [3]. Numerical resolution of the VPL system encounters some fundamental obstacles due to the notorious curse of dimensionality and thus particle-based methods play a prevalent role benefiting from their (possible) dimension independence. The DSMC-PIC method, an often-used particle method, which exploits the operator splitting technique and combines the direct simulation Monte Carlo (DSMC) (such as the TA method by Takizuka and Abe [4] and the Nanbu method [5]) for the collision step

∂tf=Q(f,f),(2)\partial_t f = Q(f,f), \tag*{(2)}

Email addresses: [email protected] (Zhengyang Lei), [email protected] (Sihong Shao) and the particle in cell (PIC) [6, 7] for the advection step

∂tf+v⋅∇xf−E⋅∇vf=0,−∇x⋅E=ρ(x,t),(3)\partial_t f + \boldsymbol{v} \cdot\nabla_x f - \boldsymbol{E} \cdot\nabla_v f = 0, \\ -\nabla_x \cdot\boldsymbol{E} = \rho(x,t), \tag*{(3)}

has been widely recognized in the literature. Accordingly, a key challenge arises in the collision step (2) due to the high-dimensionality and nonlinearity of Q(f,f)Q(f,f). The DSMC may become inefficient when the distribution function f(x,v,t)f(x,\boldsymbol{v},t) approaches the equilibrium state, denoted by m(x,v,t)m(x,\boldsymbol{v},t) (see Eq. (5)), as the collisions between equilibrium parts satisfy Q(m,m)≡0Q(m,m) \equiv0 which results in no net effect. To address this, a class of hybrid methods has been proposed to improve the efficiency via explicitly avoiding sampling from the ineffective collisions Q(m,m)Q(m,m) by the decomposition

f(x,v,t)=m(x,v,t)+fd(x,v,t),f(x,\boldsymbol{v},t) = m(x,\boldsymbol{v},t) + f_d(x,\boldsymbol{v},t),

e.g., the micro-macro approach for the BGK operator [8], the thermalization/dethermalization method for the spatial homogeneous Coulomb collisions [9] and the low-variance deviational simulation Monte Carlo methods for rarefied gas [10, 11]. For the VPL system (1), a hybrid method with deviational particles (HDP) was proposed along this line and allows the deviation fdf_d to be negative [12, 3]. Namely, the HDP method decomposes the distribution as follows

f(x,v,t)=m(x,v,t)+fp(x,v,t)−fn(x,v,t),(4)f(x,\boldsymbol{v},t) = m(x,\boldsymbol{v},t) + f_p(x,\boldsymbol{v},t) - f_n(x,\boldsymbol{v},t), \tag*{(4)}

where fp(x,v,t)≥0f_p(x,\boldsymbol{v},t) \ge0 and fn(x,v,t)≥0f_n(x,\boldsymbol{v},t) \ge0 denote the positive part and negative part of the difference f(x,v,t)−m(x,v,t)f(x,\boldsymbol{v},t) - m(x,\boldsymbol{v},t), respectively. After that, how to sample new deviational particles from the high-dimensional source term Q(fp−fn,m)Q(f_p-f_n,m) at each collision step (see Eq. (11)) becomes a new issue. The source term is a 5-D integral with singularity. HDP ingeniously approximates it as a 1-D integral and samples new deviational particles from it using the acceptance-rejection method [12]. Nevertheless, this part remains very time-consuming in actual numerical simulations as a result of the low acceptance rate (see Figure 4) and the time spent on it accounts for, e.g., roughly 90% of the total wall time (see Figure 1) in the linear Landau damping. Actually, high-dimensional sampling poses challenges in scientific computing. The common methods, including the acceptance-rejection method and Markov Chain Monte Carlo method [13], can be used to sample from general distribution. However, it is hard to find a high acceptance rate upper bound that is convenient to sample for the acceptance-rejection method and the Markov Chain Monte Carlo method may get stuck in configuration space when the proposal variance is too high [14]. This work aims to solve this high-dimensional sampling problem from Q(fp−fn,m)Q(f_p-f_n,m) at the collision step.

Image not extracted

Figure 1. The wall time consumed by sampling new deviational particles, simulating collisions via TA and others for HDP and HDP-AS in the linear Landau damping corresponding to Figure 3. We find that sampling new deviational particles takes up only 22% (89.91s/403.26s) of the total wall time in HDP-AS, whereas nearly 90% (4120.41s/4629.91s) of the total wall time in HDP.

Image not extracted

Figure 4. Linear Landau damping with α=0.01\alpha= 0.01, Neff=5×10−6N_{\mathrm{eff}} = 5 \times10^{-6}, NeffF=1×10−5N_{\mathrm{eff}}^{F} = 1 \times10^{-5} and tfin=5t_{fin} = 5: Histogram of the acceptance rates in HDP for all grid points xkx_k and time tt. Over 73% of the acceptance rates less than 0.01, and over 95% of them less than 0.1. Low acceptance rates lead to low efficiency in the acceptance-rejection sampling within the HDP method.

We propose an HDP method based on adaptive sampling (AS) for solving the VPL system (1). The resulting method, dubbed the HDP-AS method, reconstructs an adaptive piecewise constant approximation of Q(fp−fn,m)Q(f_p-f_n,m) from the point distribution, which can be readily sampled from (see Figure 2 for a quick demonstration), and the wall time consumed by sampling new deviational particles is significantly reduced (see Figure 1). This two-phase architecture — first constructing a piecewise constant approximation of the target distribution and then sampling from the resulting piecewise constant approximation — can trace its lineage to the 1960s zig­gurat algorithm [15, 16] and dramatically enhance the sampling efficiency. Moreover, HDP-AS partially borrows the idea from the discrepancy-based density estimation [17], which employs the star discrepancy to measure irregularity of points distribution and then constructs an adaptive approximation of high-dimensional unknown function. Considering the fact that the complexity of calculating the star discrepancy is NP-hard [18] and a high computational cost may be inevitable for a large sample sizes, HDP-AS replaces the star discrepancy with the mixture discrepancy which can be calculated explicitly [19]. The only difference between HDP and HDP-AS lies in that HDP samples new deviational particles by the acceptance-rejection method, whereas HDP-AS employs adaptive sampling. The other steps remain the same for both methods. Numerical results for the Landau damping, two stream instability, bump on tail and Rosenbluth’s test problem demonstrates that HDP-AS achieves about ten times acceleration compared with HDP while maintaining the same accuracy.

Image not extracted

(a) HDP: acceptance-rejection sampling.

Image not extracted

(b) HDP-AS: adaptive sampling.

Figure 2. One-dimensional schematic diagram: The HDP-AS method samples new particles from an adaptive piecewise constant approximation without rejection while the HDP method employs the acceptance-rejection sampling [12, 3].

The rest of this paper is organized as follows. In Section 2, we first present some preliminaries of the VPL system, and then introduce related numerical attempts, including the TA method and the HDP method, which lay the groundwork for the proposed HDP-AS method. Section 3 details the HDP-AS method. Numerical experiments are conducted in Section 4 for comparing HDP-AS with HDP. The paper is concluded in Section 5. This paper addresses sampling new deviational particles from the source term in the collision step of the HDP method. Other components like the advection step’s macro-micro decomposition and collision step’s particle annihilation remain identical between HDP-AS and HDP and are thus omitted here for brevity. The interested readers can refer to [12, 3] for more details.

Preliminaries and background

The Landau collision operator in Eq. (1) modules the binary collisions governed by the long range Coulomb interaction and has the form

Q(f,f)(x,v,t)=∇v⋅∫R3Φ(v−v∗)[∇vf(x,v,t)f(x,v∗,t)−∇v∗f(x,v∗,t)f(x,v,t)]dv∗Q(f,f)(x,v,t)=\nabla_v\cdot\int_{\mathbb{R}^3}\Phi(v-v^*)\left[\nabla_v f(x,v,t)f(x,v^*,t)-\nabla_{v^*}f(x,v^*,t)f(x,v,t)\right]\mathrm{d}v^*

where Φ(v)=I∣v∣−v⊗v∣v∣3\Phi(v)=\frac{I}{|v|}-\frac{v\otimes v}{|v|^3} with II being the 3×33\times3 identity matrix. For the equilibrium state given by the Maxwellian form

m(x,v,t)=ρ(x,t)(2πT(x,t))3/2exp⁡(−∣v−u(x,t)∣22T(x,t)),(5)m(x,v,t)=\frac{\rho(x,t)}{(2\pi T(x,t))^{3/2}}\exp\left(-\frac{|v-u(x,t)|^2}{2T(x,t)}\right), \tag*{(5)}

it can be easily verified that Q(m,m)≡0Q(m,m)\equiv0, where the macroscopic velocity uu and temperature TT are defined by

u=1ρ∫R3fvdv,T=13ρ∫R3f∣v−u∣2dv.(6)u=\frac{1}{\rho}\int_{\mathbb{R}^3}fv\mathrm{d}v,\qquad T=\frac{1}{3\rho}\int_{\mathbb{R}^3}f|v-u|^2\mathrm{d}v. \tag*{(6)}

A hybrid representation of the distribution function, which involves both grids and particles, is widely used to integrate the VPL system (1). In the spatial direction, uniform grids CkC_k, k=1,…,Nxk=1,\ldots,N_x are constructed with xkx_k being the center point of CkC_k. The macroscopic quantities ρ\rho, uu and TT depend only on the position, and thus are defined on the spatial grids. In the velocity direction, the particle representation is employed. The positive part fpf_p and negative part fnf_n are represented by particles called P-particles and N-particles respectively. Denote the sets of these particles at xkx_k and time tt as Pk(t)\mathcal{P}_k(t) and Nk(t)\mathcal{N}_k(t), the size of which is Np,kN_{p,k} and Nn,kN_{n,k}, respectively.

To solve the VPL system (1), we also start with an operator splitting between the collision part (2) and the advection part (3). In the HDP-AS method, the simulation of advection part employs the identical micro-macro decomposition framework [20] as that utilized in HDP, so it will not be repeated here. Below we illustrate how the TA [4] and HDP [3] methods simulate collisions in one time step Δt\Delta t, which lay the groundwork for the proposed HDP-AS method.

The TA method

The Landau operator Q(g,h)Q(g,h) describes the changes in hh resulting from collisions with gg and we refer to it as G-H collisions. The particles with the distribution gg and that with the distribution hh are respectively named as G-particles and H-particles. Denote the sets of G-particles and H-particles at grid point xkx_k and time tt as Gk(t)G_k(t) and Hk(t)H_k(t), whose size is Ng,kN_{g,k} and Nh,kN_{h,k}, respectively. It is required that Ng,k≥Nh,kN_{g,k}\ge N_{h,k}. The TA method randomly matches the H-particles with G-particles to simulate binary collisions. Suppose the current velocities of a certain pair of particles are vgv^g and vhv^h, and the velocities after the collision are v~g\widetilde{v}^g and v~h\widetilde{v}^h. When the particle masses are equal, the conservation of momentum and energy yields

vg+vh=v~g+v~h,(7)v^g+v^h=\widetilde{v}^g+\widetilde{v}^h, \tag*{(7)}
∣vg∣2+∣vh∣2=∣v~g∣2+∣v~h∣2.(8)|v^g|^2+|v^h|^2=|\widetilde{v}^g|^2+|\widetilde{v}^h|^2. \tag*{(8)}

and thus

v~g=vg+12Δu,v~h=vh−12Δu,(9)\begin{aligned} \widetilde{v}^g&=v^g+\frac{1}{2}\Delta u,\\ \widetilde{v}^h&=v^h-\frac{1}{2}\Delta u, \tag*{(9)} \end{aligned}

where Δu=(v~h−v~g)−(vh−vg)\Delta u=(\widetilde{v}^h-\widetilde{v}^g)-(v^h-v^g) is the change of relative velocity. During the collision process, the magnitude of the relative velocity remains unchanged, but its direction is altered by the scattering angle Θ\Theta and azimuthal angle Φ\Phi, which characterize the nature of the Coulomb collisions. In the TA method, Φ\Phi is chosen randomly with a uniform distribution in [0,2π][0,2\pi] and Θ=2arctan⁡(δ)\Theta= 2\arctan(\delta), where δ\delta is sampled from the normal distribution N(0,CΔt)\mathcal{N}(0,C\Delta t) and CC is determined by some physical constants as well as the magnitude of the relative velocity (see [4] for more details). Let vh−vg:=(ux,uy,uz)\mathbf{v}^{h}-\mathbf{v}^{g} := (u_x,u_y,u_z) and u:=ux2+uy2+uz2u := \sqrt{u_x^2+u_y^2+u_z^2}. The change of relative velocity Δu:=(Δux,Δuy,Δuz)\Delta\mathbf{u} := (\Delta u_x,\Delta u_y,\Delta u_z) can be computed by

Δux=uxux2+uy2uzsin⁡Θcos⁡Φ−uyux2+uy2usin⁡Θsin⁡Φ−ux(1−cos⁡Θ),Δuy=uxux2+uy2uzsin⁡Θcos⁡Φ+uxux2+uy2usin⁡Θsin⁡Φ−uy(1−cos⁡Θ),Δuz=−ux2+uy2sin⁡Θcos⁡Φ−uz(1−cos⁡Θ).(10)\begin{aligned} \Delta u_x &= \frac{u_x}{\sqrt{u_x^2+u_y^2}}u_z\sin\Theta\cos\Phi-\frac{u_y}{\sqrt{u_x^2+u_y^2}}u\sin\Theta\sin\Phi-u_x(1-\cos\Theta),\\ \Delta u_y &= \frac{u_x}{\sqrt{u_x^2+u_y^2}}u_z\sin\Theta\cos\Phi+\frac{u_x}{\sqrt{u_x^2+u_y^2}}u\sin\Theta\sin\Phi-u_y(1-\cos\Theta),\\ \Delta u_z &= -\sqrt{u_x^2+u_y^2}\sin\Theta\cos\Phi-u_z(1-\cos\Theta). \tag*{(10)} \end{aligned}

Once Δu\Delta\mathbf{u} is determined, the velocities after the collision v~g\widetilde{\mathbf{v}}^{g} and v~h\widetilde{\mathbf{v}}^{h} can be obtained according to Eq. (9). Algorithm 1 presents the pseudo-code of the TA method.

Algorithm 1 Simulate the G-H collisions with the TA method

Input: Grid number NxN_x, the set of G-particles Gk(t)\mathbb{G}_k(t) and the set of H-particles Hk(t)\mathbb{H}_k(t), k=1,…,Nxk=1,\ldots,N_x.

Output: The set of H-particles Hk(t+Δt)\mathbb{H}_k(t+\Delta t) after the Coulomb collisions, k=1,…,Nxk=1,\ldots,N_x.

  1. for k=1:Nxk=1:N_x do

  2. Hk(t+Δt)←\mathbb{H}_k(t+\Delta t)\leftarrow an empty set;

  3. Nh,k←N_{h,k}\leftarrow the size of Hk(t)\mathbb{H}_k(t);

  4. Generate a random permutation vector (σ(1),…,σ(Nh,k))(\sigma(1),\ldots,\sigma(N_{h,k})) of (1,…,Nh,k)(1,\ldots,N_{h,k});

  5. for i=1:Nh,ki=1:N_{h,k} do

  6. vg←\mathbf{v}^{g}\leftarrow the velocity of the σ(i)\sigma(i)-th G-particles;

  7. vh←\mathbf{v}^{h}\leftarrow the velocity of the ii-th H-particles;

  8. Generate randomly the scattering angle Θ\Theta and azimuthal angle Φ\Phi;

  9. Compute the change of relative velocity Δu\Delta\mathbf{u} according to Eq. (10);

  10. Compute the velocity after the collision v~h\widetilde{\mathbf{v}}^{h} according to Eq. (9);

  11. Append v~h\widetilde{\mathbf{v}}^{h} to the set Hk(t+Δt)\mathbb{H}_k(t+\Delta t);

  12. end for

  13. end for

The HDP method

The TA method may become inefficient when the distribution f(x,v,t)f(\mathbf{x},\mathbf{v},t) approaches the equilibrium state m(x,v,t)m(\mathbf{x},\mathbf{v},t), as the collisions between equilibrium parts do not produce actual effect. According to the decomposition (4), the HDP method solves the following system of equations [12, 3]

∂tf~=Q(f~,f~),∂tm=0,∂tfp=Q(f~,fp)+(Q(fp,m)−Q(fn,m))+,∂tfn=Q(f~,fn)+(Q(fp,m)−Q(fn,m))−.(11)\begin{aligned} \partial_t\widetilde{f} &= Q(\widetilde{f},\widetilde{f}),\\ \partial_t m &= 0,\\ \partial_t f_p &= Q(\widetilde{f},f_p)+\left(Q(f_p,m)-Q(f_n,m)\right)_+,\\ \partial_t f_n &= Q(\widetilde{f},f_n)+\left(Q(f_p,m)-Q(f_n,m)\right)_-. \tag*{(11)} \end{aligned}

explicitly removing the collisions Q(m,m)Q(m,m) of the equilibrium parts, where h±=12(∣h∣±h)h_{\pm}=\frac{1}{2}(|h|\pm h) gives the positive/negative part. Here the notation f~\widetilde{f} is used to distinguish it from the desired solution f=m+fp−fnf=m+f_p-f_n in (4). It is introduced in HDP as a coarse approximation of ff and used in simulating collisions Q(f~,fp)Q(\widetilde{f},f_p) and Q(f~,fn)Q(\widetilde{f},f_n). The distribution f~\widetilde{f} is represented by F-particles and the set of these particles at xk\mathbf{x}_k and time tt is denoted as Fk(t)\mathbb{F}_k(t), the size of which is Nf,kN_{f,k}. The three parts f~\tilde{f}, fpf_p, fnf_n are presented respectively by the F-particles, P-particles and N-particles, i.e., ∀φ(v)∈H02(R3)\forall\varphi(v) \in H_0^2(\mathbb{R}^3), ∀k∈{1,…,Nx}\forall k \in\{1,\ldots,N_x\},

⟨φ,f~(xk,v,t)⟩≈NeffF∑vf~∈Fk(t)φ(vf~),⟨φ,fp(xk,v,t)⟩≈Neff∑vfp∈Pk(t)φ(vfp),⟨φ,fn(xk,v,t)⟩≈Neff∑vfn∈Nk(t)φ(vfn),(12)\begin{aligned} \langle\varphi,\tilde{f}(x_k,v,t)\rangle&\approx N_{\mathrm{eff}}^F \sum_{v_{\tilde{f}}\in\mathbb{F}_k(t)} \varphi(v_{\tilde{f}}),\\ \langle\varphi,f_p(x_k,v,t)\rangle&\approx N_{\mathrm{eff}} \sum_{v_{f_p}\in\mathbb{P}_k(t)} \varphi(v_{f_p}),\\ \langle\varphi,f_n(x_k,v,t)\rangle&\approx N_{\mathrm{eff}} \sum_{v_{f_n}\in\mathbb{N}_k(t)} \varphi(v_{f_n}), \tag*{(12)} \end{aligned}

where the standard inner product ⟨g,h⟩=∫R3gh dv\langle g,h\rangle= \int_{\mathbb{R}^3} gh\,\mathrm{d}v is adopted. The effective number NeffFN_{\mathrm{eff}}^F and NeffN_{\mathrm{eff}} represent the physical densities per numerical particle and satisfy

Nf,kNeffF≈ρ(xk,t)=∫R3f~(xk,v,t) dv,Np,kNeff≈ρp(xk,t)=∫R3fp(xk,v,t) dv,Nn,kNeff≈ρn(xk,t)=∫R3fn(xk,v,t) dv.(13)\begin{aligned} N_{f,k}N_{\mathrm{eff}}^F &\approx\rho(x_k,t)=\int_{\mathbb{R}^3}\tilde{f}(x_k,v,t)\,\mathrm{d}v,\\ N_{p,k}N_{\mathrm{eff}} &\approx\rho_p(x_k,t)=\int_{\mathbb{R}^3}f_p(x_k,v,t)\,\mathrm{d}v,\\ N_{n,k}N_{\mathrm{eff}} &\approx\rho_n(x_k,t)=\int_{\mathbb{R}^3}f_n(x_k,v,t)\,\mathrm{d}v. \tag*{(13)} \end{aligned}

Eq. (13) can be obtained by taking φ≡1\varphi\equiv1 in Eq. (12). A key ingredient is that F-particles are not necessary to be a very accurate approximation of ff, and one only needs Nf,k≥Np,k+Nn,kN_{f,k} \ge N_{p,k}+N_{n,k} to ensure there are enough F-particles to simulate collisions Q(f~,fp)Q(\tilde{f},f_p) and Q(f~,fn)Q(\tilde{f},f_n). An error analysis shows that F-particles introduces a negligible error (see Section 3.3 in [12]). Eq. (11) guides the evolution of the F-particles, P-particles and N-particles in a prediction–correction manner. The F-particles act as a prediction of ff, and they are still simulated by the TA method. As corrections, P-particles and N-particles contain two parts in their evolution: One is collisions with F particles, simulated using the TA method; the other is sampling new particles from the source term

Δmk(v):=Δt(Q(fp(xk,v,t),m(xk,v,t))−Q(fn(xk,v,t),m(xk,v,t))).(14)\Delta m_k(v) := \Delta t\left(Q(f_p(x_k,v,t),m(x_k,v,t))-Q(f_n(x_k,v,t),m(x_k,v,t))\right). \tag*{(14)}

Algorithm 2 exhibits the pseudo-code of the HDP method. We focus on the main steps of HDP. There are some other steps (such as enforcing conservation and particle resampling to alleviate the growth of the particle number [12, 3]) for which HDP-AS and HDP are consistent and are not listed in Algorithm 2 for brevity.

Algorithm 2 Simulate the Coulomb collisions with the HDP method

Input: Grid number NxN_x, the set of F-particles Fk(t)\mathbb{F}_k(t), the set of P-particles Pk(t)\mathbb{P}_k(t) and the set of N-particles Nk(t)\mathbb{N}_k(t), k=1,…,Nxk=1,\ldots,N_x.

Output: The set of F-particles Fk(t+Δt)\mathbb{F}_k(t+\Delta t), P-particles Pk(t+Δt)\mathbb{P}_k(t+\Delta t) and N-particles Nk(t+Δt)\mathbb{N}_k(t+\Delta t) after the Coulomb collisions, k=1,…,Nxk=1,\ldots,N_x.

  1. Simulate F-F collisions via the TA method in Algorithm 1 and obtain Fk(t+Δt)\mathbb{F}_k(t+\Delta t), k=1,…,Nxk=1,\ldots,N_x;

  2. Simulate F-P collisions via the TA method in Algorithm 1 and obtain Pk(t+Δt)\mathbb{P}_k(t+\Delta t), k=1,…,Nxk=1,\ldots,N_x;

  3. Simulate F-N collisions via the TA method in Algorithm 1 and obtain Nk(t+Δt)\mathbb{N}_k(t+\Delta t), k=1,…,Nxk=1,\ldots,N_x;

  4. for k=1:Nxk=1:N_x do

  5. Sample new P-particles from Δmk(v)+\Delta m_k(v)_+ and add them to Pk(t+Δt)\mathbb{P}_k(t+\Delta t);

  6. Sample new N-particles from Δmk(v)−\Delta m_k(v)_- and add them to Nk(t+Δt)\mathbb{N}_k(t+\Delta t);

  7. end for

The acceptance-rejection sampling (see Figure 2) was adopted to sample new P-particles and N-particles respectively from Δmk(v)+\Delta m_k(v)_+ and Δmk(v)−\Delta m_k(v)_- required by Algorithm 2 [12, 3]. Suppose that ∣Δmk(v)∣|\Delta m_k(\boldsymbol{v})| has an upper bound Δmk^(v)\widehat{\Delta m_k}(\boldsymbol{v}) satisfying ∣Δmk(v)∣≤Δmk^(v)|\Delta m_k(\boldsymbol{v})| \le\widehat{\Delta m_k}(\boldsymbol{v}). One can sample particles from Δmk^(v)/∫R3Δmk^(v)dv\widehat{\Delta m_k}(\boldsymbol{v})/\int_{\mathbb{R}^3}\widehat{\Delta m_k}(\boldsymbol{v})\mathrm{d}\boldsymbol{v}. For one particle with coordinate v0\boldsymbol{v}_0, accept it with probability ∣Δmk(v0)∣/Δmk^(v0)|\Delta m_k(\boldsymbol{v}_0)|/\widehat{\Delta m_k}(\boldsymbol{v}_0) and label it a P or N particle in accordance with the sign of Δmk(v0)\Delta m_k(\boldsymbol{v}_0). There are two prerequisites for such acceptance-rejection sampling to be efficient: (a) The upper bound function Δmk^(v)\widehat{\Delta m_k}(\boldsymbol{v}) is easy to sample, and (b) the acceptance probability ∣Δmk(v)∣/Δmk^(v)|\Delta m_k(\boldsymbol{v})|/\widehat{\Delta m_k}(\boldsymbol{v}) is high. However, (a) and (b) are usually not compatible. If Δmk(v)\Delta m_k(\boldsymbol{v}) is a general function and Δmk^(v)\widehat{\Delta m_k}(\boldsymbol{v}) is a readily sampled probability density, then the gap between them is usually relatively large, which will lead to the low acceptance probability ∣Δmk(v)∣/Δmk^(v)|\Delta m_k(\boldsymbol{v})|/\widehat{\Delta m_k}(\boldsymbol{v}). This also constitutes the main reason why we try to develop an adaptive sampling strategy for the HDP simulations.

Adaptive sampling

Different from the acceptance-rejection sampling in the HDP method [12, 3], HDP-AS proposes an adaptive high-dimensional sampling approach to sample from Δmk(v)±\Delta m_k(\boldsymbol{v})^{\pm} required by Algorithm 2. There exist two steps in the HDP-AS method: (a) Provide an adaptive piecewise constant approximation of the function Δmk(v)\Delta m_k(\boldsymbol{v}), denoted by Δmk^(v)\widehat{\Delta m_k}(\boldsymbol{v}), and (b) sample new deviational particles directly from Δmk^(v)\widehat{\Delta m_k}(\boldsymbol{v}) instead of Δmk(v)\Delta m_k(\boldsymbol{v}). In contrast to the acceptance-rejection sampling, the implementation of sampling from a piecewise constant function in (b) is much more straightforward and without rejection. Moreover, we employ adaptive piecewise constants instead of uniform ones to alleviate the curse of dimensionality. As the implementation of (b) is straightforward, we focus exclusively on how to achieve (a) in an efficient manner in the following.

It involves two processes: (a1) Simulate the Coulomb collisions Q(fp,m)Q(f_p,m) and Q(fn,m)Q(f_n,m) in the function Δmk(v)\Delta m_k(\boldsymbol{v}) via the TA method in Algorithm 1 and obtain the point distribution Wk(v)W_k(\boldsymbol{v}) (see Eq. (15)), approximating Q(fp,m)−Q(fn,m)Q(f_p,m)-Q(f_n,m) in the weak sense, and (a2) adaptively reconstruct Δmk^(v)\widehat{\Delta m_k}(\boldsymbol{v}) from the point distribution Wk(v)W_k(\boldsymbol{v}). Denote the particles with the equilibrium distribution mm as M-particles, which are not tracked and only sampled from (5) whenever needed. In Δmk(v)\Delta m_k(\boldsymbol{v}), Q(fp,m)Q(f_p,m) and Q(fn,m)Q(f_n,m) represent that P-M collisions and N-M collisions respectively, both of which can be simulated by the TA method. Let Mk+\mathrm{M}_k^+ and Mk−\mathrm{M}_k^- collect all the M-particles after P-M collisions and N-M collisions at grid point xk\boldsymbol{x}_k and time tt, respectively. They can form a point distribution

Wk(v)=Neff∑a∈Mk+δ(v−a)−Neff∑a∈Mk−δ(v−a),(15)W_k(\boldsymbol{v})=N_{\mathrm{eff}}\sum_{\boldsymbol{a}\in\mathrm{M}_k^+}\delta(\boldsymbol{v}-\boldsymbol{a})-N_{\mathrm{eff}}\sum_{\boldsymbol{a}\in\mathrm{M}_k^-}\delta(\boldsymbol{v}-\boldsymbol{a}), \tag*{(15)}

where δ(v)\delta(\boldsymbol{v}) is the Dirac distribution in R3\mathbb{R}^3. Actually, the TA method ensures that WkW_k in Eq. (15) may approximate Q(fp,m)−Q(fn,m)Q(f_p,m)-Q(f_n,m) in the weak sense, i.e., ∀φ(v)∈H02(R3), ∀k∈{1,…,Nx}\forall\varphi(\boldsymbol{v})\in H_0^2(\mathbb{R}^3),\ \forall k\in\{1,\ldots,N_x\},

⟨φ,Q(fp(xk,v,t),m(xk,v,t))−Q(fn(xk,v,t),m(xk,v,t))⟩≈⟨φ,Wk⟩(16)\langle\varphi,Q(f_p(\boldsymbol{x}_k,\boldsymbol{v},t),m(\boldsymbol{x}_k,\boldsymbol{v},t))-Q(f_n(\boldsymbol{x}_k,\boldsymbol{v},t),m(\boldsymbol{x}_k,\boldsymbol{v},t))\rangle\approx\langle\varphi,W_k\rangle \tag*{(16)}

with

⟨φ,Wk⟩=Neff∑a∈Mk+φ(a)−Neff∑a∈Mk−φ(a).(17)\langle\varphi,W_k\rangle=N_{\mathrm{eff}}\sum_{\boldsymbol{a}\in\mathrm{M}_k^+}\varphi(\boldsymbol{a})-N_{\mathrm{eff}}\sum_{\boldsymbol{a}\in\mathrm{M}_k^-}\varphi(\boldsymbol{a}). \tag*{(17)}

Algorithm 3 details the way of obtaining Mk±\mathrm{M}_k^{\pm} in Eq. (15).

Next, we need to accomplish the process (a2). Starting from the weak approximation (16), the HDP-AS method seeks the adaptive piecewise constant approximation Δmk^(v)\widehat{\Delta m_k}(\boldsymbol{v}) of Δmk(v)\Delta m_k(\boldsymbol{v}). Let Ω=[a,b]3⊂R3\Omega=[a,b]^3\subset\mathbb{R}^3 be the computational domain containing all particles in the sets Mk+\mathrm{M}_k^+ and Mk−\mathrm{M}_k^-, and it can be decomposed into

Ω=[a,b]3=⋃l=1LΩl,(18)\Omega=[a,b]^3=\bigcup_{l=1}^{L}\Omega_l, \tag*{(18)}

Algorithm 3 Simulate the Coulomb collisions in Δmk(v)\Delta m_k(v) for k=1,…,Nxk = 1,\ldots,N_x

Input: Grid number NxN_x, the set of P-particles Pk(t)\mathbb{P}_k(t), the set of N-particles Nk(t)\mathbb{N}_k(t), the macroscopic velocity u(xk,t)\boldsymbol{u}(x_k,t) and temperature T(xk,t)T(x_k,t).

Output: Particle sets Mk±\mathbb{M}_k^{\pm} in Eq. (15).

  1. for k=1:Nxk = 1:N_x do

  2. Mk←\mathbb{M}_k \leftarrow an empty set;

  3. Np,k←N_{p,k} \leftarrow the size of Pk(t)\mathbb{P}_k(t);

  4. Sample Np,kN_{p,k} particles from the Maxwellian distribution (5) and add them to Mk\mathbb{M}_k;

  5. end for

  6. Simulate P-M collisions via the TA method in Algorithm 1 and obtain Mk+\mathbb{M}_k^{+};

  7. for k=1:Nxk = 1:N_x do

  8. Mk←\mathbb{M}_k \leftarrow an empty set;

  9. Nn,k←N_{n,k} \leftarrow the size of Nk(t)\mathbb{N}_k(t);

  10. Sample Nn,kN_{n,k} particles from the Maxwellian distribution (5) and add them to Mk\mathbb{M}_k;

  11. end for

  12. Simulate N-M collisions via the TA method in Algorithm 1 and obtain Mk−\mathbb{M}_k^{-};

such that Δmk(v)\Delta m_k(v) can be approximated as a constant clΔtc_l\Delta t in each sub-domain Ωl\Omega_l, namely,

Δmk(v)≈Δmk‾(v):=∑l=1LclΔt1Ωl(v),(19)\Delta m_k(v) \approx\overline{\Delta m_k}(v) := \sum_{l=1}^{L} c_l\Delta t 1_{\Omega_l}(v), \tag*{(19)}

where LL, clc_l and Ωl\Omega_l depends on the position xkx_k, but for brevity of notation, we omit the subscript kk representing such dependence. Taking the test function φ\varphi as the indicator function 1Ωl1_{\Omega_l} in Eq. (16), we have

cl≈1μ(Ωl)∫Ωl(Q(fp(xk,v,t),m(xk,v,t))−Q(fn(xk,v,t),m(xk,v,t)))dv≈Neff∑a∈Mk+1Ωl(a)μ(Ωl)−Neff∑a∈Mk−1Ωl(a)μ(Ωl),(20)\begin{aligned} c_l \approx\frac{1}{\mu(\Omega_l)}\int_{\Omega_l}\left(Q(f_p(x_k,v,t),m(x_k,v,t))-Q(f_n(x_k,v,t),m(x_k,v,t))\right)\mathrm{d}v \\ &\approx N_{\mathrm{eff}}\sum_{a\in\mathbb{M}_k^{+}}\frac{1_{\Omega_l}(a)}{\mu(\Omega_l)}-N_{\mathrm{eff}}\sum_{a\in\mathbb{M}_k^{-}}\frac{1_{\Omega_l}(a)}{\mu(\Omega_l)}, \tag*{(20)} \end{aligned}

where μ(Ωl)\mu(\Omega_l) gives the Lebesgue measure of Ωl\Omega_l. A simple idea for the domain decomposition in Eq. (18) is to utilize uniform grids, that is, Ωl\Omega_l, l=1,…,Ll=1,\ldots,L are hypercubes with the same side lengths. In spite of its simplicity and easy implementation, uniform grids tend to cause large errors. Small approximation error is achieved only if the side lengths of Ωl\Omega_l are small, whereas uniform grids of small lengths may lead to few particles within the grids and thus an increase in stochastic error. HDP-AS replaces the uniform grids with adaptive ones, and the idea originates from [17]. It seeks an adaptive partition of Ω\Omega via a recursive binary splitting until the particles inside each sub-domain Ωl\Omega_l are close to uniform distribution, which means that Δmk(v)\Delta m_k(v) can be approximately considered as a constant within Ωl\Omega_l. Algorithm 4 details the process of this adaptive partitioning. Let PL={Ω1,…,ΩL}\mathcal{P}_L=\{\Omega_1,\ldots,\Omega_L\} be the collection of sub-domains whose union is Ω\Omega. In the beginning, P1={Ω1}\mathcal{P}_1=\{\Omega_1\} and Ω1=Ω\Omega_1=\Omega. At level L+1L+1, PL+1\mathcal{P}_{L+1} is generated by splitting one of the regions in PL\mathcal{P}_L along one coordinate and then merging both resulting sub-domains with the remaining regions in PL\mathcal{P}_L.

Two key issues remains to be specified in the recursive binary splitting: Where to split and whether to split.

  • Where to split: Suppose Ωl=[a1(l),b1(l)]×[a2(l),b2(l)]×[a3(l),b3(l)]\Omega_l=[a_1^{(l)},b_1^{(l)}]\times[a_2^{(l)},b_2^{(l)}]\times[a_3^{(l)},b_3^{(l)}] and si0,j0(l)=aj0(l)+i0q(bi0(l)−ai0(l))s_{i_0,j_0}^{(l)}=a_{j_0}^{(l)}+\frac{i_0}{q}\left(b_{i_0}^{(l)}-a_{i_0}^{(l)}\right) are some partition points to be selected where i0=1,2,…,q−1i_0=1,2,\ldots,q-1, j0=1,2,3j_0=1,2,3. To further divide

Algorithm 4 Reconstruct the adaptive piecewise constant approximation $\Delta m_k(v)$
Input: The domain $\Omega$, particle sets $\mathbf{M}_k^{+}$ and $\mathbf{M}_k^{-}$, parameters $\vartheta$, $q$.
Output: The piecewise constant function $\overline{\Delta m_k(v)}$.
1: $L=1$, $\Omega_1=\Omega$, $\mathcal{P}_1=\{\Omega_1\}$;
2: $N_{p,k}\leftarrow$ the size of $\mathbf{M}_k^{+}$;
3: $N_{n,k}\leftarrow$ the size of $\mathbf{M}_k^{-}$;
4: $N=N_{p,k}+N_{n,k}$;
5: while true do
6:     flag $=0$;
7:     for all $\Omega_l\in\mathcal{P}_L$ do
8:         $\mathbf{M}_{\mathrm{cur}}^{+}\leftarrow$ the subset of particles in $\mathbf{M}_k^{+}$ that fall within $\Omega_l$;
9:         $\mathbf{M}_{\mathrm{cur}}^{-}\leftarrow$ the subset of particles in $\mathbf{M}_k^{-}$ that fall within $\Omega_l$;
10:        $N_{+}\leftarrow$ the size of $\mathbf{M}_{\mathrm{cur}}^{+}$;
11:        $N_{-}\leftarrow$ the size of $\mathbf{M}_{\mathrm{cur}}^{-}$;
12:        Calculate the discrepancies $D(\mathbf{M}_{\mathrm{cur}}^{+})$ and $D(\mathbf{M}_{\mathrm{cur}}^{-})$;
13:        if $D(\mathbf{M}_{\mathrm{cur}}^{+})>\frac{\vartheta\sqrt{N}}{\max(N_{+},N_{-})}$ or $D(\mathbf{M}_{\mathrm{cur}}^{-})>\frac{\vartheta\sqrt{N}}{\max(N_{+},N_{-})}$ then
14:            Choose a splitting node $\widetilde{s}_{i_0,j_0}^{(l)}$ according to {xref}`Eq. (21)`;
15:            Divide $\Omega_l$ into $\Omega_l^{(1)}\cup\Omega_l^{(2)}$ as {xref}`Eq. (22)`;
16:            $\Omega_l\leftarrow\Omega_l^{(1)}$, $\mathcal{Q}_{L+1}\leftarrow\Omega_l^{(2)}$;
17:            flag $=1$;
18:            Break;
19:        end if
20:    end for
21:    if flag $=1$ then
22:        $\mathcal{P}_{L+1}\leftarrow\{\Omega_1,\ldots,\Omega_{L+1}\}$;
23:        $L\leftarrow L+1$;
24:    else
25:        Break;
26:    end if
27: end while
28: Calculate piecewise constants $c_l$, $l=1\ldots L$ according to {xref}`Eq. (20)`;
29: $\overline{\Delta m_k(v)}\leftarrow\sum_{l=1}^{L}c_l\Delta t\mathbb{1}_{\Omega_l}(v)$;

the non-uniform sub-domains, the (sub)-optimal split points, denoted by s~i0,j0(l)\widetilde{s}_{i_0,j_0}^{(l)}, are suggested to maximize the difference gap

s~i0,j0(l)=arg⁡max⁡s~i0,j0(l)∣N+<+N−<N++N−−i0q∣,(21)\widetilde{s}_{i_0,j_0}^{(l)} = \underset{\widetilde{s}_{i_0,j_0}^{(l)}}{\arg\max} \left| \frac{N_{+}^{<}+N_{-}^{<}}{N_{+}+N_{-}}-\frac{i_0}{q} \right|, \tag*{(21)}

where Ωl\Omega_l is divided into Ωl(1)\Omega_l^{(1)} and Ωl(2)\Omega_l^{(2)},

Ωl(1)=∏j=1j0−1[aj(l),bj(l)]×[aj0(l),s~i0,j0(l)]×∏j=j0+13[aj(l),bj(l)],\Omega_l^{(1)} = \prod_{j=1}^{j_0-1}[a_j^{(l)},b_j^{(l)}] \times [a_{j_0}^{(l)},\widetilde{s}_{i_0,j_0}^{(l)}] \times \prod_{j=j_0+1}^{3}[a_j^{(l)},b_j^{(l)}],
Ωl(2)=Ωl\Ωl(1),(22)\Omega_l^{(2)}=\Omega_l\backslash\Omega_l^{(1)}, \tag*{(22)}

and N+<N_{+}^{<} and N−<N_{-}^{<} count the number of particles in Mcur+\mathbf{M}_{\mathrm{cur}}^{+} and Mcur−\mathbf{M}_{\mathrm{cur}}^{-} (see Lines 8 and 9 in Algorithm 4) that fall within Ωl(1)\Omega_l^{(1)}, respectively. The intuition behind Eq. (21) is to dig out the most non-uniform sub-domain after fixing the selectable partition points.

  • Whether to split: We use the discrepancies D(Mcur+)D(\mathrm{M}_{\mathrm{cur}}^{+}) and D(Mcur−)D(\mathrm{M}_{\mathrm{cur}}^{-}) as indicators to measure the uniformity of the points distribution. Small discrepancies indicate a relatively uniform particle distribution and no further partitioning is necessary. Discrepancy is a broad category and contains various specific definitions [21, 22]. The star discrepancy is used in [17], the definition of which for point set (v1,…,vn)⊂[0,1]3n(\boldsymbol{v}_1,\ldots,\boldsymbol{v}_n) \subset[0,1]^{3n} is stated as follows

D∗(v1,…,vn)=sup⁡u∈[0,1]3∣1n∑i=1n1[0,u)(vi)−vol⁡([0,u))∣.(23)D^{*}(\boldsymbol{v}_1,\ldots,\boldsymbol{v}_n)=\sup_{\boldsymbol{u}\in[0,1]^3}\left|\frac{1}{n}\sum_{i=1}^{n}\mathbb{1}_{[0,\boldsymbol{u})}(\boldsymbol{v}_i)-\operatorname{vol}([0,\boldsymbol{u}))\right|. \tag*{(23)}

The complexity of calculating the star discrepancy is NP-hard. Although there are heuristic algorithms [18, 23], a high computational cost is likely to be unavoidable when the sample sizes are large. To ensure efficient partitioning, we employ the mixture discrepancy (take DD in Algorithm 4 as DmixD^{\mathrm{mix}} in Eq. (24)) to substitute the star discrepancy as the uniformity measure, which possesses an explicit expression [19]

Dmix(v1,…,vn)=(1912)3−2n∑i=1n∏j=13(53−14∣vij−12∣−14∣vij−12∣2)+1n2∑i=1n∑k=1n∏j=13(158−14∣vij−12∣−14∣vkj−12∣−34∣vij−vkj∣+12∣vij−vkj∣2).(24)\begin{aligned} D^{\mathrm{mix}}(\boldsymbol{v}_1,\ldots,\boldsymbol{v}_n) ={}&\left(\frac{19}{12}\right)^3-\frac{2}{n}\sum_{i=1}^{n}\prod_{j=1}^{3}\left(\frac{5}{3}-\frac{1}{4}\left|v_{ij}-\frac{1}{2}\right|-\frac{1}{4}\left|v_{ij}-\frac{1}{2}\right|^2\right)\\ &+\frac{1}{n^2}\sum_{i=1}^{n}\sum_{k=1}^{n}\prod_{j=1}^{3}\left(\frac{15}{8}-\frac{1}{4}\left|v_{ij}-\frac{1}{2}\right|-\frac{1}{4}\left|v_{kj}-\frac{1}{2}\right|\right.\\ &\left.\qquad\qquad-\frac{3}{4}\left|v_{ij}-v_{kj}\right|+\frac{1}{2}\left|v_{ij}-v_{kj}\right|^2\right). \tag*{(24)} \end{aligned}

where vi=(vi1,vi2,vi3)\boldsymbol{v}_i=(v_{i1},v_{i2},v_{i3}). Let Mcur+={v1+,…,vN++}\mathrm{M}_{\mathrm{cur}}^{+}=\{\boldsymbol{v}_1^{+},\ldots,\boldsymbol{v}_{N_{+}}^{+}\}, Mcur−={v1−,…,vN−−}\mathrm{M}_{\mathrm{cur}}^{-}=\{\boldsymbol{v}_1^{-},\ldots,\boldsymbol{v}_{N_{-}}^{-}\}. The discrepancy, for two sequences Mcur+\mathrm{M}_{\mathrm{cur}}^{+} and Mcur−\mathrm{M}_{\mathrm{cur}}^{-} in Ωl\Omega_l, can be defined by a linear scaling ιl:Ωl→[0,1]3\iota_l:\Omega_l\to[0,1]^3,

Dmix(Mcur+)=Dmix(ιl(v1+),…,ιl(vN++)),Dmix(Mcur−)=Dmix(ιl(v1−),…,ιl(vN−−)),(25)\begin{aligned} D^{\mathrm{mix}}(\mathrm{M}_{\mathrm{cur}}^{+})&=D^{\mathrm{mix}}(\iota_l(\boldsymbol{v}_1^{+}),\ldots,\iota_l(\boldsymbol{v}_{N_{+}}^{+})),\\ D^{\mathrm{mix}}(\mathrm{M}_{\mathrm{cur}}^{-})&=D^{\mathrm{mix}}(\iota_l(\boldsymbol{v}_1^{-}),\ldots,\iota_l(\boldsymbol{v}_{N_{-}}^{-})), \tag*{(25)} \end{aligned}

with

ιl(v1,v2,v3)=(v1−a1(l)b1(l)−a1(l),v2−a2(l)b2(l)−a2(l),v3−a3(l)b3(l)−a3(l)).(26)\iota_l(v_1,v_2,v_3)=\left(\frac{v_1-a_1^{(l)}}{b_1^{(l)}-a_1^{(l)}},\frac{v_2-a_2^{(l)}}{b_2^{(l)}-a_2^{(l)}},\frac{v_3-a_3^{(l)}}{b_3^{(l)}-a_3^{(l)}}\right). \tag*{(26)}

The specified stopping criterion is

Dmix(Mcur+)≤ϑNmax⁡(N+,N−),Dmix(Mcur−)≤ϑNmax⁡(N+,N−),(27)D^{\mathrm{mix}}(\mathrm{M}_{\mathrm{cur}}^{+})\le\frac{\vartheta\sqrt{N}}{\max(N_{+},N_{-})},\qquad D^{\mathrm{mix}}(\mathrm{M}_{\mathrm{cur}}^{-})\le\frac{\vartheta\sqrt{N}}{\max(N_{+},N_{-})}, \tag*{(27)}

where the parameter ϑ\vartheta governs the depth of partition, and NN, N±N_{\pm} are given in Lines 4, 10 and 11 in Algorithm 4. A smaller ϑ\vartheta leads to a finer partitioning. The above criterion (27) treats the P-particles and N-particles on the same footing and has been successfully applied into an efficient stochastic particle simulation of the Wigner-Coulomb quantum dynamics [24].

In contrast to the low acceptance rate of the acceptance-rejection method employed by HDP (see Figure 4), sampling from the piecewise constant functions Δm‾k(v)\Delta\overline{m}_k(\boldsymbol{v}) in HDP-AS is straightforward and without rejection, thereby significantly enhancing the sampling efficiency. Using this improvement, the main time-consuming steps of HDP-AS become simulating collisions and advection, while sampling new deviational particles is no longer time-consuming now (see Figure 1).

Remark 1. The iconic ziggurat algorithm [15, 16] efficiently generates samples by partitioning the desired distribution functions into equal-area segments. Knuth praises it as “a very pretty example of mathematical theory intimately interwoven with programming ingenuity—a fine illustration of the art of computer programming!” in his famous book [25]. This work inherits the idea of the ziggurat algorithm to solve the sampling problem in the HDP method. The main challenges in current applications lie in the desired distribution Δmk(v)\Delta m_k(\mathbf{v}) is a three-dimensional function and we need efficiently construct a piecewise constant approximation from its point cloud form (15). Our HDP-AS method addresses these specific challenges through an adaptive domain partitioning based on the mixture discrepancy.

Numerical experiments

This section conducts five typical numerical experiments on the 1-D spatial and 3-D velocity coordinates, including the linear and nonlinear Landau damping problems, two stream instability problem, Bump on Tail problem and Rosenbluth’s problem. A careful benchmark of HDP on the linear and nonlinear Landau damping against PIC-DSMC [3], which combines a Particle in Cell (PIC) method on the advection and a Direct Simulation Monte Carlo (DSMC) method on the collisions, as well as on Bump on Tail problem and Rosenbluth’s problem against the TA method [12], has been conducted and demonstrates the accuracy and efficiency of HDP. Therefore this section only focuses on a clear and one-to-one comparison between HDP-AS and HDP. We set the spatial domain to be x∈[0,4π]x \in[0,4\pi] with periodic boundary condition and choose Nx=100N_x = 100 grids with the spatial spacing Δx=4πNx\Delta x = \frac{4\pi}{N_x}. The time step is set as Δt=Δx/10\Delta t = \Delta x/10. The partitioning parameters for the adaptive reconstruction in Algorithm 4 are set as ϑ=0.1\vartheta= 0.1, q=16q = 16 unless otherwise specified. We control the numerical particle numbers by the parameters NeffN_{\mathrm{eff}} and NeffFN_{\mathrm{eff}}^F. In order to visualize the high-dimensional numerical solutions, we adopt the following 1-D and 2-D projections

p1d(v1,t)=∫R3f(x,v,t) dxdv2dv3,p2d(x,v1,t)=∫R2f(x,v,t) dv2dv3.(28)p_{1d}(v_1,t) = \int_{\mathbb{R}^3} f(x,\mathbf{v},t)\,\mathrm{d}x\mathrm{d}v_2\mathrm{d}v_3,\quad p_{2d}(x,v_1,t) = \int_{\mathbb{R}^2} f(x,\mathbf{v},t)\,\mathrm{d}v_2\mathrm{d}v_3. \tag*{(28)}

Meanwhile, we use the relative L2L^2 error of the 2-D projection

E2[p2d](t)=∥p2dnum(x,v1,t)−p2dref(x,v1,t)∥2∥p2dref(x,v1,t)∥2(29)\mathcal{E}_2[p_{2d}](t) = \frac{\left\|p_{2d}^{\mathrm{num}}(x,v_1,t)-p_{2d}^{\mathrm{ref}}(x,v_1,t)\right\|_2}{\left\|p_{2d}^{\mathrm{ref}}(x,v_1,t)\right\|_2} \tag*{(29)}

to measure the accuracy. The reference solutions p2dref(x,v1,t)p_{2d}^{\mathrm{ref}}(x,v_1,t) are produced by the DSMC-PIC method with NeffF=6.25×10−7N_{\mathrm{eff}}^F = 6.25 \times10^{-7}. All simulations via C++ implementations run on the High-Performance Computing Platform of Peking University: 2*Intel Xeon E5-2697A-v4 (2.60GHz, 40MB Cache, 9.6GT/s QPI Speed, 16 Cores, 32 Threads) with 256GB Memory × 16.

Linear Landau damping

First we consider the linear Landau damping problem. The initial data are equilibrium distribution f(x,v,0)=m(x,v,0)f(x,v,0) = m(x,v,0) with the macroscopic quantities

{ρ(x,0)=1+αsin⁡(x),u(x,0)=0,T(x,0)=1,(30)\begin{cases} \rho(x,0) = 1 + \alpha\sin(x),\\ u(x,0) = 0,\\ T(x,0) = 1, \tag*{(30)} \end{cases}

where the constant α\alpha characterizes the amplitude of the perturbation. We conduct the tests until the final time tfin=5t_{fin} = 5. Table 1 presents the efficiency tests for α=0.001,0.01,0.1\alpha= 0.001,0.01,0.1 and different sample sizes. The HDP-AS method runs roughly ten times faster than the HDP method, along with smaller errors. For example, when α=0.01\alpha= 0.01, Neff=5×10−6N_{\mathrm{eff}} = 5 \times10^{-6} and NeffF=1×10−5N_{\mathrm{eff}}^F = 1 \times10^{-5}, HDP-AS takes 403.26 seconds while HDP takes 4626.91 seconds, achieving an acceleration of 11.47 times. In terms of the accuracy, the relative L2L^2 error E2[p2d](tfin)\mathcal{E}_2[p_{2d}](t_{fin}) of HDP-AS (0.0264) is also preferable to that of HDP (0.0451). Figure 3 displays the snapshots of p2d(x,v1,tfin)p_{2d}(x,v_1,t_{fin}) produced by HDP and HDP-AS corresponding to this group of parameters and as excepted, a good agreement can be readily observed. Figure 4 displays the histogram of the acceptance rates in HDP. More than 73% of the acceptance rates are less than 0.01. The low acceptance rate leads to a high sampling cost. On the contrary, HDP-AS achieves high-dimensional sampling without rejection by approximating the source term Δmk(v)\Delta m_k(v) with an adaptive piecewise constant function Δm‾k(v)\overline{\Delta m}_k(v) defined in Eq. (19). Figure 5 plots ∫R3Δm‾k(v) dv3\int_{\mathbb{R}^3}\overline{\Delta m}_k(v)\,\mathrm{d}v_3, the projection of adaptive piecewise constant approximation Δm‾k(v)\overline{\Delta m}_k(v) in v1v2v_1v_2-plane with k=50k=50. In accordance with the changes of the distribution f(x,v,t)f(x,v,t) (see Figure 3 for the 2-D projections in v1xv_1x-plane), this projection exhibits significant changes in the region (v1,v2)∈[−2,2]×[−2,2](v_1,v_2)\in[-2,2]\times[-2,2], which reflects the intrinsic adaptivity of HDP-AS. Just because of the adaptivity of Δm‾k(v)\overline{\Delta m}_k(v), new deviational particles sampled by HDP-AS are of higher quality than those by HDP and thus able to capture the characteristics of Δmk(v)\Delta m_k(v) accurately with a smaller size. For instance, HDP-AS samples 177 new P-particles and 166 new N-particles, whereas HDP samples 412 new P-particles and 370 new N-particles for α=0.01\alpha=0.01, Neff=5×10−6N_{\mathrm{eff}}=5\times10^{-6}, NeffF=1×10−5N_{\mathrm{eff}}^{F}=1\times10^{-5} and t=1t=1 in this example. Much less new deviational particles being added may enable other remaining steps such as simulating collisions via TA and advection to take less time (see Figure 1).

α\alphaNeffN_{\mathrm{eff}}NeffFN_{\mathrm{eff}}^{F}HDP E2[p2d](tfin)\mathcal{E}_2[p_{2d}](t_{fin})HDP Time/sHDP-AS E2[p2d](tfin)\mathcal{E}_2[p_{2d}](t_{fin})HDP-AS Time/s
2×10−52\times10^{-5}4×10−54\times10^{-5}0.13791951.410.052397.79
0.0011×10−51\times10^{-5}2×10−52\times10^{-5}0.08292194.630.0306183.39
5×10−65\times10^{-6}1×10−51\times10^{-5}0.03242692.260.0228359.10
2×10−52\times10^{-5}4×10−54\times10^{-5}0.16793049.580.0577111.58
0.011×10−51\times10^{-5}2×10−52\times10^{-5}0.09743833.220.0381216.10
5×10−65\times10^{-6}1×10−51\times10^{-5}0.04514626.910.0264403.26
2×10−52\times10^{-5}2×10−52\times10^{-5}0.20207281.120.0999345.94
0.11×10−51\times10^{-5}1×10−51\times10^{-5}0.12757736.820.0688626.06
5×10−65\times10^{-6}5×10−65\times10^{-6}0.068112435.640.05841380.85

Table 1. Linear Landau damping: Total wall time and the relative L2L^2 error E2[p2d](tfin)\mathcal{E}_2[p_{2d}](t_{fin}) (see Eq. (29)) under different α\alpha and sample sizes. HDP-AS attains an acceleration of approximately ten times against HDP and maintains smaller errors.

Image not extracted

(a) HDP.

Image not extracted

(b) HDP-AS.

Figure 3. Linear Landau damping: Snapshots of p2d(x,v1,tfin)p_{2d}(x,v_1,t_{fin}) produced by HDP and HDP-AS with α=0.01\alpha= 0.01, Neff=5×10−6N_{\mathrm{eff}} = 5 \times10^{-6}, NeffF=1×10−5N_{\mathrm{eff}}^{F} = 1 \times10^{-5} and tfin=5t_{fin} = 5.

Image not extracted

Figure 5. Linear Landau damping with α=0.01\alpha= 0.01, Neff=5×10−6N_{\mathrm{eff}} = 5 \times10^{-6}, NeffF=1×10−5N_{\mathrm{eff}}^{F} = 1 \times10^{-5} and tfin=5t_{fin} = 5: The projection of adaptive piecewise constant approximation Δmk‾(v)\overline{\Delta m_k}(v) in v1v2v_1v_2-plane with k=50k = 50 at different instants. In accordance with the changes of the distribution f(x,v,t)f(x,v,t) (see Figure 3 for the 2-D projections in v1xv_1x-plane), the projection exhibits significant changes in the region (v1,v2)∈[−2,2]×[−2,2](v_1,v_2) \in[-2,2] \times[-2,2], and thus we depict the snapshots only for v2∈[−2,2]v_2 \in[-2,2].

Nonlinear Landau damping

We consider the nonlinear Landau damping problem with α=0.4\alpha=0.4 in Eq. (30). Figure 6 illustrates the good agreement of solutions p2d(x,v1,5)p_{2d}(x,v_1,5) between the HDP method and the HDP-AS method. Figure 7 presents the convergence tests and all methods show a half order convergence. Furthermore, both HDP and HDP-AS exhibit smaller errors than DSMC-PIC after taking the same sample size. For the Landau damping problem, the damping of electric field energy

Image not extracted

Figure 6. Nonlinear Landau damping: Snapshots of p2d(x,v1,tfin)p_{2d}(x,v_1,t_{fin}) produced by HDP and HDP-AS with α=0.4\alpha= 0.4, Neff=1×10−6N_{\mathrm{eff}} = 1 \times10^{-6}, NeffF=1×10−6N_{\mathrm{eff}}^{F} = 1 \times10^{-6} and tfin=5t_{fin} = 5.

Image not extracted

Figure 7. Nonlinear Landau damping with α=0.4\alpha= 0.4 and tfin=0.5t_{\mathrm{fin}} = 0.5: The HDP, HDP-AS and DSMC-PIC methods all exhibit a half order convergence. When the sample sizes are identical, the errors of both HDP and HDP-AS are smaller than that of DSMC-PIC.

∥E∥2=Δx∑k=1Nx(Ek)2(31)\lVert E\rVert^2=\Delta x\sum_{k=1}^{N_x}(E_k)^2 \tag*{(31)}

is also be studied, where EkE_k is the value of the electric field EE at the position xkx_k. Figure 8 shows clearly the Landau damping phenomenon, and the curve produced by HDP-AS agrees well with that by HDP.

Image not extracted

Figure 8. Nonlinear Landau damping with α=0.4\alpha= 0.4, Neff=1×10−6N_{\mathrm{eff}} = 1 \times10^{-6}, NeffF=1×10−6N_{\mathrm{eff}}^{F} = 1 \times10^{-6} and tfin=5t_{\mathrm{fin}} = 5: Comparison of the decay of energy ∥E∥2\lVert E\rVert^{2} between HDP and HDP-AS.

Two stream instability

In this numerical experiment, the initial data are

f(x,v,0)=112π(1+0.5cos⁡(0.5x))exp⁡(−v12+v22+v322)(1+5v12),(32)f(x,\mathbf{v},0)=\frac{1}{12\pi}(1+0.5\cos(0.5x))\exp\left(-\frac{v_1^2+v_2^2+v_3^2}{2}\right)(1+5v_1^2), \tag*{(32)}

and we run the tests up to the final time tfin=8t_{fin}=8. Figure 9 presents the snapshots of p2d(x,v1,t)p_{2d}(x,v_1,t) at different instants. The two stream is observed when t=2t=2, and the distribution p2d(x,v1,t)p_{2d}(x,v_1,t) approaches the equilibrium state for t≥4t\geq4 due to the effect of collisions. Figure 10 exhibits the relative L2L^2 error E2[p2d](t)\mathcal{E}_2[p_{2d}](t) and the wall time throughout the simulation process. Up to tfin=8t_{fin}=8, HDP-AS takes 2190 seconds whereas HDP needs 13866 seconds. In a word, HDP-AS significantly reduces the wall time compared to HDP while maintaining the same accuracy.

Image not extracted

Figure 9. Two stream instability: Plots of p2d(x,v1,t)p_{2d}(x,v_1,t) at t=2,4,8t = 2, 4, 8 for the HDP and HDP-AS solutions with Neff=1×10−6N_{\mathrm{eff}} = 1 \times10^{-6} and NeffF=1×10−6N_{\mathrm{eff}}^{F} = 1 \times10^{-6}.

(a) E2[p2d](t)\mathcal{E}_2[p_{2d}](t).

Image not extracted

(b) The wall time.

Figure 10. Two stream instability: History of the relative L2L^2 error E2[p2d](t)\mathcal{E}_2[p_{2d}](t) and the wall time for HDP and HDP-AS with Neff=1×10−6N_{\mathrm{eff}} = 1 \times10^{-6}, NeffF=1×10−6N_{\mathrm{eff}}^{F} = 1 \times10^{-6}. The error evolutions of the two methods are comparable, yet the wall time of HDP-AS is significantly less than that of HDP.

Bump on tail

In this case, we test the bump on tail problem, whose initial data contain a central Maxwellian and a small bump at high energy,

f(x,v,0)=[β(2πTa)3/2exp⁡(−∣v∣22Ta)+1−β(2πTb)3/2exp⁡(−∣v−ub∣22Tb)]1(2πTx)1/2exp⁡(−(x−xc)22Tx),(33)f(x,\mathbf{v},0)=\left[\frac{\beta}{(2\pi T_a)^{3/2}}\exp\left(-\frac{|\mathbf{v}|^2}{2T_a}\right)+\frac{1-\beta}{(2\pi T_b)^{3/2}}\exp\left(-\frac{|\mathbf{v}-\mathbf{u}_b|^2}{2T_b}\right)\right]\frac{1}{(2\pi T_x)^{1/2}}\exp\left(-\frac{(x-x_c)^2}{2T_x}\right), \tag*{(33)}

where β=0.9,Ta=1,Tb=0.001,ub=[5,0,0],xc=2π,Tx=0.25\beta=0.9,T_a=1,T_b=0.001,\mathbf{u}_b=[5,0,0],x_c=2\pi,T_x=0.25. Here we set the final time tfin=2t_{fin}=2. Figure 11 plots the HDP-AS solutions against the HDP ones. We are able to observe there that the high energy part decays and shifts towards the Maxwellian state for both solutions. Table 2 shows the sensitivity tests about parameters ν\nu and qq needed in Algorithm 4. The parameter ν\nu defined in Eq. (27) adjusts the depth of partition and the parameter qq defined in Eq. (21) is related to the number of selectable partition points. Numerical results in Table 2 demonstrates that HDP-AS is insensitive to these two parameters. The errors E2[p2d](tfin)\mathcal{E}_2[p_{2d}](t_{fin}) of the nine groups of data are all around 0.12, which is close to the error 0.1378 of HDP. The wall time of HDP-AS slightly increases with the decrease of ν\nu and the increase of qq, because a smaller ν\nu means a finer partition and a larger qq means more selectable partition points to be examined. On the whole, the wall time of HDP-AS is around 300 seconds, significantly lower than 2414.43 seconds of HDP.

Methodν\nuqqE2[p2d](tfin)\mathcal{E}_2[p_{2d}](t_{fin})Time/s
HDP--0.13782414.43
HDP-AS0.140.1117243.57
HDP-AS0.1160.1150247.36
HDP-AS0.1640.1160258.94
HDP-AS0.0540.1225244.41
HDP-AS0.05160.1073248.30
HDP-AS0.05640.1161261.08
HDP-AS0.0140.1250359.29
HDP-AS0.01160.1209364.07
HDP-AS0.01640.1087385.95

Table 2. Bump on tail: Sensitivity tests about the parameters ν\nu and qq in Algorithm 4 with Neff=1×10−6N_{\mathrm{eff}}=1\times10^{-6} and Neff′=1×10−6N_{\mathrm{eff}}^{\prime}=1\times10^{-6}. It can be readily seen that HDP-AS is not sensitive to ν\nu and qq, and runs approximately ten times faster than HDP while keeping the same accuracy.

Image not extracted

(a) t=0.0t = 0.0.

Image not extracted

(b) t=0.5t = 0.5.

Image not extracted

(c) t=1.0t = 1.0.

Image not extracted

(d) t=2.0t = 2.0.

Figure 11. Bump on tail: Time evolutions of p1d(v1,t)p_{1d}(v_1,t) for the HDP and HDP-AS methods with Neff=1×10−6N_{\mathrm{eff}} = 1 \times10^{-6}, NeffF=1×10−6N_{\mathrm{eff}}^{F} = 1 \times10^{-6}, ν=0.1\nu= 0.1 and q=16q = 16.

Rosenbluth’s test problem

Finally we examine the Rosenbluth’s test problem and the initial data are given by

f(x,v,0)=0.01exp⁡(−10(∣v∣−1)2)(1+0.5sin⁡(0.5x)).(34)f(x,v,0)=0.01\exp\left(-10(|v|-1)^2\right)(1+0.5\sin(0.5x)). \tag*{(34)}

Here we adopt the final time tfint_{fin} as 1. Figure 12 illustrates the good agreement between the solutions obtained from HDP-AS and HDP at different instants. Table 3 presents the sensitivity tests for Rosenbluth’s test problem. HDP-AS method is insensitive to the parameters and it runs approximately ten times (191.91-385.95 seconds) faster than the HDP method (3946.71 seconds) with smaller errors.

Image not extracted

Figure 12. Rosenbluth’s test problem: Time evolutions of p1d(v1,t)p_{1d}(v_1,t) for HDP and HDP-AS with Neff=1×10−6N_{\mathrm{eff}}=1 \times10^{-6}, NeffF=5×10−7N_{\mathrm{eff}}^{F}=5 \times10^{-7}, ν=0.1\nu=0.1 and q=16q=16.

Methodν\nuqqE2[p2d](tfin)\mathcal{E}_2[p_{2d}](t_{\mathrm{fin}})Time/s
HDP--0.09653946.71
HDP-AS0.140.0225191.91
HDP-AS0.1160.0225193.08
HDP-AS0.1640.0220195.86
HDP-AS0.0540.0217193.52
HDP-AS0.05160.0217194.13
HDP-AS0.05640.020197.58
HDP-AS0.0140.0230285.12
HDP-AS0.01160.0223290.17
HDP-AS0.01640.0233385.95

Table 3. Rosenbluth’s test problem: Sensitivity tests about the parameters ν\nu and qq in Algorithm 4 on the HDP-AS method with Neff=1×10−6N_{\mathrm{eff}}=1 \times10^{-6} and NeffF=5×10−7N_{\mathrm{eff}}^{F}=5 \times10^{-7}.

Conclusion and discussion

The main contributions of this work include two parts:

  • Proposing an alternative adaptive strategy for sampling from Δmk(v)±\Delta m_k(v)_{\pm} in the HDP method. It constructs an adaptive piecewise constant approximation of Δmk(v)±\Delta m_k(v)_{\pm} at first, and then the sampling is conducted directly from the piecewise constant function without rejection.

  • Employing the mixture discrepancy in place of the star discrepancy as the uniformity measure accelerates the reconstruction of the adaptive piecewise constant approximation in [17]. The mixture discrepancy has an explicit expression and no external solver is required.

Owing to the above two improvements, the proposed HDP-AS method successfully reduces the computational cost of the HDP method. The same idea could be applied to other sampling tasks, provided that each part of the function to be sampled has already been represented by multiple particle sets (e.g., in this work, the Q(fp,m)Q(f_p,m) and Q(fn,m)Q(f_n,m) in Δmk(v)±\Delta m_k(v)_{\pm} are represented by particle sets M+\mathbb{M}^{+} and M−\mathbb{M}^{-} in Eq. (15)). There remain some aspects to be explored, such as the error analysis of HDP-AS, the application to practical problems in higher dimensions, and whether more efficient uniformity measure manner can further accelerate the reconstruction of the adaptive piecewise constant approximation.

Acknowledgement

This research was supported by the National Natural Science Foundation of China (Nos. 12325112, 12288101) and the High-performance Computing Platform of Peking University. The authors are sincerely grateful to Dr. Bokai Yan, the author of [3], for providing us the source code of HDP, which greatly facilitates our implementation of HDP-AS as well as the comparison between HDP and HDP-AS.

References

  1. [1]C. Cercignani, The Boltzmann Equation and its Applications, Springer, 1988.DOI
  2. [2]C. Villani, A review of mathematical topics in collisional kinetic theory, in: Handbook of Mathematical Fluid Dynamics, vol. I, North-Holland, Amsterdam, 2002, pp. 71–305.DOI
  3. [3]B. Yan, A hybrid method with deviational particles for spatial inhomogeneous plasma, Journal of Computational Physics 309 (2016) 18–36.DOI
  4. [4]T. Takizuka, H. Abe, A binary collision model for plasma simulation with a particle code, Journal of Computational Physics 25 (1977) 205–219.DOI
  5. [5]K. Nanbu, Theory of cumulative small-angle collisions in plasmas, Physical Review E 55 (1997) 4642.DOI
  6. [6]C. K. Birdsall, A. B. Langdon, Plasma Physics via Computer Simulation, Institute of Physics Publishing, 1991.
  7. [7]Y. N. Grigoriev, V. A. Vshivkov, M. P. Fedoruk, Numerical “Particle-in-Cell” Methods: Theory and Applications, Walter de Gruyter, 2012.
  8. [8]A. Crestetto, N. Crouseilles, M. Lemou, Kinetic/fluid micro-macro numerical schemes for Vlasov-Poisson-BGK equation using particles, Kinetic and Related Models 5 (2012) 787–816.DOI
  9. [9]R. Caflisch, C. Wang, G. Dimarco, B. Cohen, A. Dimits, A hybrid method for accelerated simulation of Coulomb collisions in a plasma, Multiscale Modeling and Simulation 7 (2008) 865–887.
  10. [10]L. L. Baker, N. G. Hadjiconstantinou, Variance reduction for Monte Carlo solutions of the Boltzmann equation, Physics of Fluids 17 (2005) 051703.DOI
  11. [11]T. M. Homolle, N. G. Hadjiconstantinou, A low-variance deviational simulation Monte Carlo for the Boltzmann equation, Journal of Computational Physics 226 (2007) 2341–2358.
  12. [12]B. Yan, R. E. Caflisch, A Monte Carlo method with negative particles for Coulomb collisions, Journal of Computational Physics 298 (2015) 711–740.DOI
  13. [13]W. E. T. Li, E. Vanden-Eijnden, Applied Stochastic Analysis, volume 199, American Mathematical Society, 2019.
  14. [14]G. O. Roberts, J. S. Rosenthal, Optimal scaling for various Metropolis-Hastings algorithms, Statistical Science 16 (2001) 351–367.DOI
  15. [15]G. Marsaglia, Expressing a random variable in terms of uniform random variables, Annals of Mathematical Statistics 32 (1961) 894 – 898.DOI
  16. [16]G. Marsaglia, W. Tsang, The ziggurat method for generating random variables, Journal of Statistical Software 5 (2000) 1–7.DOI
  17. [17]D. Li, K. Yang, W. Wong, Density estimation via discrepancy based adaptive sequential partition, Advances in Neural Information Processing Systems (2016) 1099–1107.
  18. [18]M. Gnewuch, M. Wahlström, C. Winzen, A new randomized algorithm to approximate the star discrepancy based on threshold accepting, SIAM Journal on Numerical Analysis 50 (2012) 781–807.DOI
  19. [19]Y. Zhou, K. Fang, J. Ning, Mixture discrepancy for quasi-random point sets, Journal of Complexity 29 (2013) 283–301.DOI
  20. [20]M. Bennoune, M. Lemou, L. Mieussens, Uniformly stable numerical schemes for the Boltzmann equation preserving the compressible Navier-Stokes asymptotics, Journal of Computational Physics 227 (2008) 3781–3803.DOI
  21. [21]F. Pausinger, A. M. Svane, A Koksma–Hlawka inequality for general discrepancy systems, Journal of Complexity 31 (2015) 773–797.DOI
  22. [22]F. Hickernell, A generalized discrepancy and quadrature error bound, Mathematics of Computation 67 (1998) 299–322.DOI
  23. [23]P. Winker, K. Fang, Application of threshold-accepting to the evaluation of the discrepancy of a set of points, SIAM Journal on Numerical Analysis 34 (1997) 2028–2042.DOI
  24. [24]Y. Xiong, S. Shao, Overcoming the numerical sign problem in the Wigner dynamics via particle annihilation, SIAM Journal on Scientific Computing 46 (2024) B107–B136.
  25. [25]D. Knuth, The Art of Computer Programming Volume 2: Seminumerical Algorithms, third ed., Addison–Wesley, 1997.

Paper details

vlnc:W_5pn7t8fg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Not recorded for this paper

View statement
Looking for related papers…
Contents