betaFeedback

WorksPhysics and Astronomy

Fast inverse transform sampling of non-Gaussian distribution functions in space plasmas

Abstract

Non-Gaussian distributions are commonly observed in collisionless space plasmas. Generating samples from non-Gaussian distributions is critical for the initialization of particle-in-cell simulations that investigate their driven and undriven dynamics. To this end, we report a computationally efficient, robust tool, Chebsampling, to sample general distribution functions in one and two dimensions. This tool is based on inverse transform sampling with function approximation by Chebyshev polynomials. We demonstrate practical uses of Chebsampling through sampling typical distribution functions in space plasmas.

Key Points

  • New computational tool for fast sampling of arbitrary particle distribution functions is presented.

  • Chebyshev polynomial interpolation allows to approximate grid-based distributions and accelerates the solution of inversion problem.

  • We illustrate the use of Chebsampling via sampling non-Harris current sheets and non-Maxwellian velocity distributions.

Corresponding author: Xin An, [email protected]

Introduction

Non-Gaussian distribution functions are commonly observed in space plasma systems, in which the extremely low frequency of particle collisions allows velocity distributions quite different from the equilibrium solutions (Maxwellians or isotropic Gaussians) of the Boltzmann equation [20]. Except for planetary and solar atmospheres, the entire heliosphere, a region filled with plasma of solar origin, can usually be considered as a weakly collisional medium where charged particle velocity distributions may significantly deviate from the Gaussian distribution. Such velocity distributions include multicomponent distributions consisting of localized peaks in 6D phase space of velocities and coordinates, power-law distributions in which particles have a significant probability of achieving a velocity very different from the mean velocity, and distributions resulting from collisionless relaxation of plasma instabilities. Sampling from these non-Gaussian distributions in either configuration or velocity space is often used to load particles in kinetic simulations for further investigation of their driven and undriven dynamics. This problem in space plasmas calls for a flexible, fast sampling algorithm that can handle any non-Gaussian distributions.

More broadly, generating pseudo-random samples from a prescribed distribution is a procedure important to computational plasma physics as well as other branches of computational physics. Particle-in-cell simulations, Monte Carlo simulations, molecular dynamics simulations, and gravitational simulations, for example, all use certain sampling algorithms to initialize various distribution functions. One of these algorithms, inverse transform sampling, is a simple method of generating samples XX from any probability distribution function (PDF) by inverting its cumulative distribution function (CDF) as FX−1(U)F_X^{-1}(U), where UU is uniformly distributed on [0,1][0,1] and FXF_X denotes the CDF. The application of inverse transform sampling is limited in practice, however, because it requires either a closed form of FX−1F_X^{-1} or a complete approximation to FXF_X regardless of the desired sample size, it does not generalize to multiple dimensions, and it is less efficient than other approaches [10, 25, 11]. Instead, rejection sampling [e.g. 10] is usually used for low-dimensional distributions, and the Metropolis-Hastings algorithm [15] is used for high-dimensional distributions.

The development of Chebyshev technology [e.g. 23, 9] (see chebfun.org) has enabled a complete approximation to a smooth function using Chebyshev polynomials. Furthermore, approximation by Chebyshev polynomials to an analytic function converges geometrically fast [see 23]. For this reason, in inverse transform sampling the CDF can be well approximated to a high precision by the Chebyshev projection and can be evaluated efficiently. The use of Chebyshev projection in sampling has been only recently explored by Olver and Townsend [16], who showed that inverse transform sampling with Chebyshev polynomial approximation is computa tionally efficient and robust in one dimension. They extended the approach to two dimensions but required that the CDF be well approximated by a low-rank function.

Here we report a numerical tool to apply inverse transform sampling with Chebyshev polynomial approximation to distribution functions in one and two dimensions. In Section 2, we describe the algorithm and the implementation of our numerical tool Chebsampling. In Section 3, we demonstrate the accuracy and efficiency of our algorithm by sampling representative distribution functions (in either the configuration space or in the velocity space) in space plasmas. In Section 4, we summarize the results and discuss the pros and cons of our method.

Methodology

Inverse transform sampling

We briefly recap the inverse transform sampling method with one and two variables. In one dimension (1D), let f(x)f(x) be a PDF defined on the interval [a,b][a,b]. Its CDF FX(x)F_X(x) is a strictly increasing function. To generate NN samples x1,x2,…,xNx_1,x_2,\ldots,x_N that are distributed according to f(x)f(x), we invert the corresponding CDF, i.e.,

xj=FX−1(uj)(j=1,2,…,N),(1)x_j = F_X^{-1}(u_j) \qquad(j=1,2,\ldots,N), \tag*{(1)}

where uju_j is uniform on [0,1][0,1]. This is inverse transform sampling. In practice, we find xjx_j by finding the root of FX(xj)=ujF_X(x_j)=u_j, because the inverse transform FX−1F_X^{-1} often cannot be easily obtained. Thus, generating NN samples requires solving NN root-finding problems.

In two dimensions (2D), let f(x,y)f(x,y) be a joint PDF defined on the rectangular domain [a,b]×[c,d][a,b]\times[c,d]. This joint distribution may be written as

f(x,y)=fY(y)⋅fX∣Y(x∣y),(2)f(x,y)=f_Y(y)\cdot f_{X|Y}(x|y), \tag*{(2)}

where fYf_Y is the marginal distribution in the yy direction, and fX∣Yf_{X|Y} is the conditional distribution in the xx direction for a given value of yy. We do not require that f(x,y)f(x,y) be approximated by a low-rank function as in [16], because this approximation is not always valid in our applications. Let FYF_Y and FX∣YF_{X|Y} be the CDFs of fYf_Y and fX∣Yf_{X|Y}, respectively. First, NyN_y samples y1,y2,…,yNyy_1,y_2,\ldots,y_{N_y} are generated by solving the root-finding problem

FY(yk)=uk,(k=1,2,…,Ny),(3)F_Y(y_k)=u_k,\qquad(k=1,2,\ldots,N_y), \tag*{(3)}

where uku_k is uniform on [0,1][0,1]. Second, for each yky_k in Equation (3), NxN_x samples x1k,x2k,…,xNxkx_{1k},x_{2k},\ldots,x_{N_xk} are generated by finding the root for

FX∣Y(xjk∣yk)=uj,(j=1,2,…,Nx),(4)F_{X|Y}(x_{jk}|y_k)=u_j,\qquad(j=1,2,\ldots,N_x), \tag*{(4)}

where uku_k is uniform on [0,1][0,1]. Thus, sampling of a joint 2D PDF is reduced to sampling of two 1D PDFs. As indicated by Equations (3) and (4), generation of Nx⋅NyN_x\cdot N_y samples requires solving (Nx+1)⋅Ny(N_x+1)\cdot N_y root-finding problems. In the special case of the separable distribution function (i.e., f(x,y)=fY(y)⋅fX(x)f(x,y)=f_Y(y)\cdot f_X(x)), only Nx+NyN_x+N_y root-finding problems need to be solved to generate Nx⋅NyN_x\cdot N_y samples.

Chebyshev polynomial approximation

The efficiency of inverse transform sampling depends on the computational cost of root finding, so we adopt the bisection method for root finding. Because the CDFs increase monotonically, this method is guaranteed to converge to a high precision [6]. We should note that it is possible to speed up the root finding further by using a hybrid bisection combined with a Newton method (since calculating derivatives with Chebyshev polynomials is fast), but it is not necessary to do so in our application, and the performance of the bisection method is acceptable. Most of the computing time in root finding is spent on evaluation of the functions (i.e., CDFs). Fortunately, most of these functions can be accurately approximated by Chebyshev polynomials, and there are well-developed fast algorithms to evaluate them. Below we describe representation of a function by Chebyshev polynomials and rapid evaluation of this function at an arbitrary point in the domain.

Chebyshev polynomials are defined on the interval [−1,1][-1,1] to which other interval [a,b][a,b] can be scaled. We consider the Chebyshev points

xk=cos⁡(kπn)(k=0,1,…,n),(5)x_k = \cos\left(\frac{k\pi}{n}\right) \qquad(k=0,1,\ldots,n), \tag*{(5)}

which are extrema of the nnth Chebyshev polynomial Tn(x)=cos⁡(n⋅arccos⁡x)T_n(x)=\cos\left(n\cdot\arccos x\right). The Chebyshev points are clustered near the two ends of the interval, −1-1 and 11. Unlike polynomial interpolation at equispaced points (see chap. 13 in Refs. Trefethen, [23]; Platte et al., [19]), which is associated with a well-known numerical instability (the Runge phenomenon), polynomial interpolation at the Chebyshev points is numerically stable. The Chebyshev polynomials T0(x)T_0(x), T1(x)T_1(x), …\ldots, Tn(x)T_n(x) on these points are orthogonal to each other (see sec. 4.6.1 in Ref. Mason & Handscomb, [14]), i.e.,

∑k=0n′′Ti(xk)Tj(xk)={0,(0≤i,j≤n; i≠j),n2,(0<i=j<n),n,(i=j=0 or n),(6)\sum_{k=0}^{n}{}^{\prime\prime} T_i(x_k)T_j(x_k)= \begin{cases} 0, & (0\le i,j\le n;\ i\ne j),\\ \frac{n}{2}, & (0<i=j<n),\\ n, & (i=j=0\text{ or }n), \end{cases} \tag*{(6)}

where the double dash in ∑k=0n′′\sum_{k=0}^{n}{}^{\prime\prime} denotes the first and last terms in the sum are to be halved. This discrete orthogonality property leads us to a very efficient interpolation formula.

We approximate ff by the nnth degree polynomial

pn(x)=∑k=0n′′ckTk(x),(7)p_n(x)=\sum_{k=0}^{n}{}^{\prime\prime} c_kT_k(x), \tag*{(7)}

which interpolates ff at the Chebyshev points, i.e., pn(xj)=f(xj)p_n(x_j)=f(x_j) with xj=cos⁡(jπ/n)x_j=\cos(j\pi/n). The interpolation coefficients ckc_k are given by

ck=2n∑j=0n′′f(xj)Tk(xj)(k=0,1,…,n).(8)c_k=\frac{2}{n}\sum_{j=0}^{n}{}^{\prime\prime} f(x_j)T_k(x_j)\qquad(k=0,1,\ldots,n). \tag*{(8)}

The evaluation of ckc_k can be done in O(nlog⁡n)O(n\log n) operations by using the Fast Fourier Transform (FFT), which is detailed in Appendix A.

To determine the degree nn of the polynomial that is sufficient to approximate ff, we adopt an adaptive procedure introduced in the Chebfun software system (Driscoll et al., [9]). In this procedure, we progressively select nn to be 24=162^4=16, 25=322^5=32, 26=642^6=64 and so on. For a given nn, the ff data at the n+1n+1 Chebyshev points is converted to n+1n+1 Chebyshev coefficients. If the tail of these coefficients falls below a relative level of prescribed precision, then the Chebyshev points are judged to be fine enough. We truncate the tail and keep only the non-negligible terms. The complex engineering details of truncating a Chebyshev series are given by Aurentz and Trefethen [4] (see the function “standardChop” in Chebfun).

Once the Chebyshev coefficients ckc_k have been obtained, the original data ff can be discarded. These Chebyshev coefficients are then repetitively used to efficiently evaluate ff (also ∫f dx\int f\,\mathrm{d}x and df/dx\mathrm{d}f/\mathrm{d}x) for arbitrary points in the domain. One way of achieving this is to use the Clenshaw algorithm [7] (details of this algorithm are described in Appendix § 7). To better visualize our approach desribed by Equations (1)–(8), we sketch the main idea of the fast inverse transform sampling with function approximation by Chebyshev polynomials in Figure 1.

Conceptual sketch for the fast inverse transform sampling with function approximation by Chebyshev polynomials

Figure 1. Conceptual sketch for the fast inverse transform sampling with function approximation by Chebyshev polynomials. Panels on the left of the arrows represent the inversion problem FX(x)=uF_X(x)=u, where uu is uniformly distributed in the interval [0,1][0,1] and FXF_X is the CDF. Panels on the right of the arrows represent the Chebyshev polynomials, which are used as the basis functions to interpolate and evaluate the CDF.

Implementation

With the above considerations, we implemented Chebsampling in Fortran 90 with parallelization using MPI. The logical flows of 1D and 2D inverse transform sampling programs are summarized in Algorithms 1 and 2, respectively. Notably, our input PDF data are defined on grid, which is more flexible when an analytical expression of the input PDF is not available. For the 2D joint PDF, we apply the 1D sampling algorithm repetitively to generate samples from marginal and conditional distribution functions. As demonstrated in § 3, inverse transform sampling using the Chebyshev polynomial approximation is very efficient.

To generate a large number of samples, we parallelize the 2D inverse transform sampling algorithm. First, NpyN_{py} samples of yy are drawn from the marginal distribution function fY(y)f_Y(y), which is executed on all processors. Second, the tasks of sampling the conditional distribution function fX∣Y(x∣y)f_{X|Y}(x|y) are evenly divided among processors based on the yy samples, such that the load is balanced on each processor. The xx samples drawn from the conditional distribution function are stored in local memory. This parallelization scheme yields nearly ideal scaling of the computational cost against the number of processors (see performance tests in § 3).

Algorithm 1: 1D inverse transform sampling using the Chebyshev polynomial approximation.

Input: PDF data f(xj)f(x_j) defined on a 1D uniform grid (j=1,2,⋯ ,Ngj=1,2,\cdots,N_g) and the desired number of samples NsamplesN_{\mathrm{samples}}.

Output: Samples xmx_m (m=1,2,⋯ ,Nsamplesm=1,2,\cdots,N_{\mathrm{samples}}) distributed according to f(x)f(x).

  • Calculate the cumulative sum of f(xj)f(x_j) using the recursive relation F(xj)=F(xj−1)+(f(xj−1)+f(xj))/2F(x_j)=F(x_{j-1})+(f(x_{j-1})+f(x_j))/2 where F(x1)=0F(x_1)=0 and j=2,3,⋯ ,Ngj=2,3,\cdots,N_g;

  • Normalize the cumulative sum as F(xj)=F(xj)/F(xNg)F(x_j)=F(x_j)/F(x_{N_g});

  • Progressively select n=16,32,64,⋯n=16,32,64,\cdots as in a loop, compute the Chebyshev coefficients clc_l (l=0,1,⋯ ,nl=0,1,\cdots,n) using (8), and exit the loop if the tail of these coefficients falls below a relative level of prescribed precision;

  • Generate samples xmx_m by solving the root-finding problem F(xm)=umF(x_m)=u_m with the bisection method, where F(x)=∑l=0NcutoffclTl(x)F(x)=\sum_{l=0}^{N_{\mathrm{cutoff}}}c_lT_l(x), um=(m−0.5)/Nsamplesu_m=(m-0.5)/N_{\mathrm{samples}}, and m=1,2,⋯ ,Nsamplesm=1,2,\cdots,N_{\mathrm{samples}}.

Algorithm 2: 2D inverse transform sampling using the Chebyshev polynomial approximation.

Input: PDF data f(xj,yk)f(x_j,y_k) defined on a 2D uniform grid (j=1,2,⋯ ,Ngxj=1,2,\cdots,N_{gx}; k=1,2,⋯ ,Ngyk=1,2,\cdots,N_{gy}); the desired number of samples in xx direction NpxN_{px}; the desired number of samples in yy direction NpyN_{py}.

Output: Samples (xmn,yn)(x_{mn},y_n) (m=1,2,⋯ ,Npxm=1,2,\cdots,N_{px}; n=1,2,⋯ ,Npyn=1,2,\cdots,N_{py}) distributed according to f(x,y)f(x,y).

  • Calculate the marginal distribution function fY(yk)=∑j=1Ngxf(xj,yk)f_Y(y_k)=\sum_{j=1}^{N_{gx}}f(x_j,y_k);

  • Draw samples yny_n (n=1,2,⋯ ,Npyn=1,2,\cdots,N_{py}) from the marginal distribution fY(y)f_Y(y) by performing 1D inverse transform sampling using the Chebyshev polynomial approximation;

  • For each sample yny_n (n=1,2,⋯ ,Npyn=1,2,\cdots,N_{py}):

    • Construct the conditional distribution function fX∣Y(xj∣yn)f_{X\mid Y}(x_j\mid y_n) by interpolating f(xj,yk)f(x_j,y_k) (j=1,2,⋯ ,Ngxj=1,2,\cdots,N_{gx}; k=1,2,⋯ ,Ngyk=1,2,\cdots,N_{gy}) into sampled locations yny_n;

    • Draw samples xmnx_{mn} (m=1,2,⋯ ,Npxm=1,2,\cdots,N_{px}) from the conditional distribution fX∣Y(x∣y)f_{X\mid Y}(x\mid y) by performing 1D inverse transform sampling with the Chebyshev polynomial approximation.

Numerical examples

Below we illustrate the performance and accuracy of our algorithm by applying it to representative distribution functions in space plasmas.

2D Maxwellian current sheets

We first consider the density distribution relevant to a very important plasma equilibrium, the 2D current sheet, which is believed to be formed in the solar corona and has been commonly observed in planetary magnetospheres. In their seminal paper, [13] constructed a two-dimensional current sheet at equilibrium that resembles the planetary magnetotail configuration. In this model, the magnetic field lines in the xx-zz plane are described by the vector potential Ay(εx,z)eyA_y(\varepsilon x,z)e_y, where ∣ε∣≪1|\varepsilon|\ll1 indicates weak dependence of AyA_y on xx. The vector potential is determined by Ampere’s law

∂2∂z2Ay=−4π∑αqαn0vDαcexp⁡(−qαΦTα0+vDαqαAycTα0),(9)\frac{\partial^2}{\partial z^2}A_y=-4\pi\sum_\alpha q_\alpha n_0\frac{v_{D\alpha}}{c}\exp\left(-\frac{q_\alpha\Phi}{T_{\alpha0}}+\frac{v_{D\alpha}q_\alpha A_y}{cT_{\alpha0}}\right), \tag*{(9)}

where φ(x,z)\varphi(x,z) is the electrostatic potential, n0n_0 is the reference density, vDαv_{D\alpha} is the drift velocity, Tα0T_{\alpha0} is the temperature of current sheet particles, qαq_\alpha is the charge, and cc is the speed of light. The subscript α=e,i\alpha= e, i represents electrons and ions, respectively. Note that ∂2Ay/∂x2\partial^2 A_y/\partial x^2 is omitted in Equation (9), and thus the equation is precise to order ε\varepsilon. The current density in Equation (9) is derived by integrating the Boltzmann-type distribution in velocity space. The electrostatic potential φ\varphi is determined by the quasi-neutrality condition

∑αqαn0exp⁡(−qαφTα0+vDαqαAycTα0)+qαnbexp⁡(−qαφTαb)=0.(10)\sum_\alpha q_\alpha n_0 \exp\left(-\frac{q_\alpha\varphi}{T_{\alpha0}}+\frac{v_{D\alpha}q_\alpha A_y}{cT_{\alpha0}}\right)+q_\alpha n_b\exp\left(-\frac{q_\alpha\varphi}{T_{\alpha b}}\right)=0. \tag*{(10)}

Here two populations, the current sheet population (i.e., the current-carrying one) and the background population (i.e., the non-current-carrying one), are represented by the first and the second terms, respectively. In this example, we solve Equations (9) and (10) in the rectangular domain [−Lz/2≤z≤Lz/2]×[−Lx≤x≤0][-L_z/2 \leq z \leq L_z/2] \times[-L_x \leq x \leq0] with the boundary condition Ay∣z=0=εB0xA_y|_{z=0}=\varepsilon B_0x, ∂Ay/∂z∣z=0=0\partial A_y/\partial z|_{z=0}=0. Here B0B_0 refers to the asymptotic magnetic field at z→±∞z \to\pm\infty, and εB0\varepsilon B_0 gives the zz component of the magnetic field at z=0z=0. An analytical solution of AyA_y and φ\varphi is not available except for the particular choice of parameters, i.e., vDi/Ti0=−vDe/Te0v_{Di}/T_{i0}=-v_{De}/T_{e0}. To handle more general scenarios, we solve Equations (9) and (10) numerically and obtain AyA_y and φ\varphi on grid.

Table 1 shows the two sets of parameters that are used as examples below. The first set of parameters satisfies vDi/Ti0=−vDe/Te0v_{Di}/T_{i0}=-v_{De}/T_{e0} so the electrostatic potential is zero everywhere in the domain (a nonpolarized current sheet). The second set of parameters has the relation ∣vDi/Ti0∣<∣vDe/Te0∣|v_{Di}/T_{i0}|<|v_{De}/T_{e0}|, and thus gives a nonzero electric field (a polarized current sheet). This plasma equilibrium is used as an initial condition for numerical simulations helpful in solving many problems related to plasma stability and dynamics in planetary magnetotails. Therefore, a critical task is to generate a 2D spatial distribution of plasma particles for a given numerical solution of scalar and vector potentials. For purposes of demonstration, we apply our method to sample the density distribution of the current sheet population,

vDivA\frac{v_{Di}}{v_A}vDevA\frac{v_{De}}{v_A}Ti0mivA2\frac{T_{i0}}{m_i v_A^2}Te0mivA2\frac{T_{e0}}{m_i v_A^2}TibmivA2\frac{T_{ib}}{m_i v_A^2}TebmivA2\frac{T_{eb}}{m_i v_A^2}nbn0\frac{n_b}{n_0}Lxdi\frac{L_x}{d_i}Lzdi\frac{L_z}{d_i}
Nonpolarized512\frac{5}{12}−112-\frac{1}{12}512\frac{5}{12}112\frac{1}{12}512\frac{5}{12}112\frac{1}{12}0.20.232321616
Polarized13\frac{1}{3}−43-\frac{4}{3}512\frac{5}{12}112\frac{1}{12}512\frac{5}{12}112\frac{1}{12}0.20.232321616

Table 1. Two sets of parameters for nonpolarized and polarized Lembege-Pellat current sheets. The velocities are normalized to the Alfvén velocity vA=B0/4πn0miv_A = B_0/\sqrt{4\pi n_0m_i}, the temperatures are normalized to mivA2m_i v_A^2, the densities are normalized to n0n_0, and the length is normalized to the ion inertial length did_i.

nα0=n0exp⁡(−qαφTα0+vDαqαAycTα0).(11)n_{\alpha0}=n_0\exp\left(-\frac{q_\alpha\varphi}{T_{\alpha0}}+\frac{v_{D\alpha}q_\alpha A_y}{cT_{\alpha0}}\right). \tag*{(11)}

For the first set of parameters, the density distribution of the ion current sheet is identical to that of the electron current sheet. To sample this density distribution, we use Npx=20000N_{px}=20000 particles in the xx direction and Npz=10000N_{pz}=10000 particles in the zz direction, which gives a total of Npx⋅Npz=2×108N_{px}\cdot N_{pz}=2\times10^8 particles. Figure 2(a) through 2(c) show the excellent agreement between the ground truth density and the sampled density. The errors [≲ 1%; Figure 2(c)] come from the low-density region and are negligible for our application (particle-in-cell simulations). This sampling takes about 628 seconds on a single processor. Using the parallelization scheme outlined in § 2, we observe that the sampling takes about 1 second on 512 processors. As shown in Figure 3, the wall-clock time used in sampling scales ideally against the number of processors.

Inverse transform sampling of the Lembege-Pellat current sheet

Figure 2. Inverse transform sampling of the Lembege-Pellat current sheet. (a)-(c) The nonpolarized Lembege-Pellat current sheet set up using the first set of parameters in Table 1. (d)-(i) The ion component [(d), (e), (f)] and the electron component [(g), (h), (i)] of the polarized Lembege-Pellat current sheet. This current sheet is obtained using the second set of parameters in Table 1. The displayed distributions are for the current sheet population only, as shown in Equation (11). The three rows from top to bottom show the ground-truth density distributions, the sampled density distributions, and the difference between the sampled and ground-truth distributions, respectively.

Strong scaling of Chebsampling for sampling the nonpolarized Lembege-Pellat current sheet

Figure 3. Strong scaling of Chebsampling for sampling the nonpolarized Lembege-Pellat current sheet. The xx and yy axes represent the number of processors and the elapsed wall-clock time, respectively. The dashed line represents the ideal scaling.

Similarly, we generate 2×1082 \times10^{8} samples for the polarized current sheet. The results are shown in Figure 2(d) through 2(i). In this case, the electron current sheet [Figure 2(g)] is embedded in the ion current sheet [Figure 2(d)]. Sampling the electron current sheet is challenging because of the steep gradient at its edge. The Chebyshev projection, which is able to capture the main characteristics of the electron current sheet, gives an accurate sampled distribution [Figure 2(h)-(Figure 2i)].

In Table 2, we compare the performance of inverse transform sampling with rejection sampling for the distributions shown in Figure 2. For relatively fat distribution functions as in Figure 2(a) and Figure 2(d), rejection sampling is more efficient than inverse transform sampling. For highly peaked distribution functions as in Figure 2(g), however, inverse transform sampling outperforms rejection sampling. To represent such a distribution function, inverse transform sampling must only add more Chebyshev coefficients that do not add much computational cost, whereas rejection sampling rejects a significant fraction of samples that does add much computational cost (because the ratio of the area under the distribution function to that under the rectangular hat function is small). Therefore, inverse transform sampling avoids the practical limit in rejection sampling and gives a more consistent performance across distribution functions with vastly different shapes.

ITS [seconds]RS [seconds]
Nonpolarized current sheet3.20.75
Polarized ion current sheet3.60.6
Polarized electron current sheet9.730.6

Table 2. Performance comparison of inverse transform sampling (ITS) with rejection sampling (RS). In this comparison, 2×1062 \times10^{6} samples are generated using a single processor for each case. The current sheet distributions in the three rows correspond to Figures 2(a), 2(d), and 2(g), respectively.

Non-Maxwellian velocity distributions

Furthermore, we consider three non-Maxwellian velocity distributions in the solar wind and the terrestrial magnetosphere:

  1. Halo electrons in the solar wind (Štverák et al. [21]):

f(v⊥,v∥)={1−[1+12δ(v⊥2vc⊥2+v∥2vc∥2)]p−q}×[1+12κh−3(v⊥2vh⊥2+v∥2vh∥2)]−κh−1(12)f(v_\perp,v_\parallel) = \left\{1-\left[1+\frac{1}{2\delta}\left(\frac{v_\perp^2}{v_{c\perp}^2}+\frac{v_\parallel^2}{v_{c\parallel}^2}\right)\right]^{p-q}\right\}\times\left[1+\frac{1}{2\kappa_h-3}\left(\frac{v_\perp^2}{v_{h\perp}^2}+\frac{v_\parallel^2}{v_{h\parallel}^2}\right)\right]^{-\kappa_h-1} \tag*{(12)}

with κh=3\kappa_h=3, vh∥=vT=1v_{h\parallel}=v_T=1, vh⊥=1/2v_{h\perp}=1/\sqrt{2}, vc∥=0.3v_{c\parallel}=0.3, vc⊥=0.3v_{c\perp}=0.3, δ=0.9\delta=0.9, p=10p=10 and q=1q=1;

  1. Electrons in the force-free current sheet [12]:

f(vx,vy,vz)=exp⁡(−βvx2+vy2+vz22)×[exp⁡(βuy(vy+Ay))+acos⁡(βux(vx+Ax))+b](13)f(v_x,v_y,v_z)=\exp\left(-\beta\frac{v_x^2+v_y^2+v_z^2}{2}\right)\times\left[\exp\left(\beta u_y(v_y+A_y)\right)+a\cos\left(\beta u_x(v_x+A_x)\right)+b\right] \tag*{(13)}

with β=vT−2=1\beta=v_T^{-2}=1, ux=uy=2u_x=u_y=\sqrt{2}, Ax=Ay=0A_x=A_y=0, a=1a=1 and b=2b=2;

  1. Electrons in the injection regions in the Earth’s magnetotail [8, 24, 2]:

f(v⊥,v∥)=[1+1κ(v⊥2vc⊥2+v∥2vc∥2)]−κ−1exp⁡(−v⊥22vh⊥2−v∥22vh∥2)(14)f(v_\perp,v_\parallel)=\left[1+\frac{1}{\kappa}\left(\frac{v_\perp^2}{v_{c\perp}^2}+\frac{v_\parallel^2}{v_{c\parallel}^2}\right)\right]^{-\kappa-1}\exp\left(-\frac{v_\perp^2}{2v_{h\perp}^2}-\frac{v_\parallel^2}{2v_{h\parallel}^2}\right) \tag*{(14)}

with κ=0.2\kappa=0.2, vh∥=vT=1v_{h\parallel}=v_T=1, vh⊥=2v_{h\perp}=\sqrt{2}, vc⊥=3/800vh⊥v_{c\perp}=\sqrt{3/800}v_{h\perp} and vc∥=2vc⊥v_{c\parallel}=\sqrt{2}v_{c\perp}.

The velocity distributions in Equations (12) and (14) are uniform in gyrophase, and the velocity distribution in Equation (13) obeys a Maxwellian in the zz direction that is separable from the xx and yy directions. Thus, these sampling problems are essentially two dimensional. Figure 4 shows the results of generating 2×1082 \times10^8 samples for each of the three velocity distributions. The sampling times for these three cases are about 7–9 seconds on 64 processors. The sampled distributions capture the main trends of the original distributions. The errors are located at the high-energy tails, where the number of particles is limited. For our application in particle-in-cell simulations, such errors will not cause any problem, because the fraction of high-energy particles is very small, and thus their contribution to the charge and current deposition is small compared to the bulk of the distribution. It is noteworthy that the Chebyshev projection can fit the flat-top part of the halo electron distribution [i.e., the truncated core of the distribution with almost no electrons; see Figure 4(a) and Figure 4(b)]. Because such flat-top distributions have also been found in the magnetic reconnection region [3] and the shock region [26], sampling them could be useful for other studies.

Inverse transform sampling of velocity distributions in space plasmas

Figure 4. Inverse transform sampling of velocity distributions in space plasmas. (a)-(c) Halo electrons in the solar wind. (d)-(f) The electron distribution in the force-free current sheet. (g)-(i) The electron distribution in the injection regions in Earth’s magnetotail. The three rows from top to bottom show the ground-truth velocity distributions, the sampled velocity distributions, and the difference between the sampled and ground-truth distributions, respectively. The sampling errors appearing as lines instead of random dots are caused by setting nonrandom, evenly distributed uk=(k−0.5)/Nyu_k = (k - 0.5)/N_y (where k=1,2,⋯ ,Nyk = 1, 2, \cdots, N_y) in Equation (3) [similarly for uju_j in Equation (4)] instead of random samples uniformly distributed in the interval [0,1][0, 1], which corresponds to the “quiet start” ([5]).

We list the computational details in sampling the six representative distribution functions in Table 3. From each distribution, 2×1082 \times10^8 samples are generated on 64 processors. For all cases, the time it takes to compute the Chebyshev coefficients (tchebt_{\mathrm{cheb}}) is about 1000 times shorter than that of the bisection root finding (tbisct_{\mathrm{bisc}}). For distributions that have steep gradients such as in the polarized current sheet, the number of Chebyshev coefficients can be large and thus it takes longer to compute those coefficients.

ϵCheb\epsilon_{\mathrm{Cheb}}NcutoffN_{\mathrm{cutoff}}tChebt_{\mathrm{Cheb}} [ms]ϵbisc\epsilon_{\mathrm{bisc}}NbiscN_{\mathrm{bisc}}tbisct_{\mathrm{bisc}} [s]
Nonpolarized current sheet10−810^{-8}7–388.210−1410^{-14}46–4811.3
Polarized ion current sheet10−810^{-8}16–1441610−1410^{-14}46–4848.1
Polarized electron current sheet10−810^{-8}24–1905910−1410^{-14}4869.2
Halo electrons in the solar wind10−810^{-8}14–3606.810−1410^{-14}47–488.5
Electrons in force-free current sheets10−810^{-8}24–287.910−1410^{-14}487.9
Electrons in the injection fronts10−810^{-8}12–3764.610−1410^{-14}47–486.4

Table 3. Computational details of the six representative distribution functions. ϵCheb\epsilon_{\mathrm{Cheb}} and ϵbisc\epsilon_{\mathrm{bisc}} are the relative error controls in Chebyshev polynomial interpolation and bisection root finding, respectively. NcutoffN_{\mathrm{cutoff}} is the number of Chebyshev coefficients to interpolate each distribution using Chebyshev polynomials. NbiscN_{\mathrm{bisc}} is the number of iteration for convergence of root finding using the bisection method. tChebt_{\mathrm{Cheb}} and tbisct_{\mathrm{bisc}} are the time costs of Chebyshev polynomial interpolation and bisection root finding, respectively. Note that NcutoffN_{\mathrm{cutoff}} is shown as a range because it varies for the marginal and conditional distributions.

Summary and discussion

We developed a novel tool, Chebsampling, for accurate, efficient sampling of distribution functions in one and two dimensions. It features the use of function approximation by Chebyshev polynomials, which accelerates root finding in the inverse transform sampling. Chebsampling is implemented on massively parallel computers and has the potential to be used for fully three-dimensional sampling in physical systems. The practical use of this tool is illustrated through typical examples in space plasmas.

Inverse transform sampling is efficient for any distribution functions that can be numerically approximated and evaluated with low cost. The distribution function can be well approximated in one dimension by Chebyshev polynomials, and the inverse sampling method is practical. The sample size in two or three dimensions is relatively small and the time cost is affordable with parallelizations. With increasing sample size, however, using the inverse transform sampling in higher dimensions is challenging, because one needs to perform approximately the same number of inversions as the sample size. Although function approximation in two dimensions starts to emerge [22], fundamental algorithmic issues on how to numerically approximate general distribution functions with more variables remain. Once these issues have been resolved, the inverse transform sampling method will be immediately usable in higher dimensions. Rejction sampling has a similar problem in higher dimensions. As the dimensions get larger, the ratio of the embedded volume to the total volume goes to zero. Thus a significant number of unwanted samples are rejected before a useful sample is obtained. In high dimensions, the Metropolis-Hastings algorithm is usually used, which is beyond the scope of our study.

Open research

The code Chebsampling that has been developed in this manuscript is publicly available at https://doi.org/10.5281/zenodo.6109523. A compute capsule for reproducing the runs in this manuscript has been set up at https://codeocean.com/capsule/0988490/tree/v2.

Computation of the Chebyshev coefficients ckc_k

The evaluation of the Chebyshev coefficients ckc_k through the use of FFT has been well established (see Refs. Mason & Handscomb, [14]; Ahmed & Fisher, [1]; Orszag, [17, 18]). Equation (8) can be viewed as the discrete Chebyshev transform f(xk)→ckf(x_k) \to c_k. The connection to discrete Fourier transform can be seen through a change in variables

g(θ)=f(cos⁡θ),ϕk=kπn,xk=cos⁡(ϕk).(15)g(\theta)=f(\cos\theta),\quad\phi_k=\frac{k\pi}{n},\quad x_k=\cos(\phi_k). \tag*{(15)}

(8) can be rewritten as

ck=2n∑j=0n′′g(jπn)cos⁡(jkπn)(k=0,1,…,n).(16)c_k=\frac{2}{n}\sum_{j=0}^{n}{}^{\prime\prime}g\left(\frac{j\pi}{n}\right)\cos\left(\frac{jk\pi}{n}\right)\quad(k=0,1,\ldots,n). \tag*{(16)}

Since cos⁡θ\cos\theta and thus g(θ)g(\theta) are even functions of θ\theta, we can rewrite Equation (16)

ck=1n∑j=−nn′′g(jπn)exp⁡(jkπn)(k=−n,−n+1,…,n).(17)c_k=\frac{1}{n}\sum_{j=-n}^{n}{}^{\prime\prime}g\left(\frac{j\pi}{n}\right)\exp\left(\frac{jk\pi}{n}\right)\quad(k=-n,-n+1,\ldots,n). \tag*{(17)}

Furthermore, since cos⁡θ\cos\theta and thus g(θ)g(\theta) are 2π2\pi-periodic functions of θ\theta, we can rewrite (17) in the form of discrete Fourier transform

ck=1n∑j=02n−1g(jπn)exp⁡(ijkπn),(k=0,1,⋯ ,2n−1).(18)c_k = \frac{1}{n}\sum_{j=0}^{2n-1}g\left(\frac{j\pi}{n}\right)\exp\left(i\frac{jk\pi}{n}\right), \qquad(k=0,1,\cdots,2n-1). \tag*{(18)}

Evaluation of the Chebyshev sum

The Clenshaw algorithm is a recursive method to calculate the sum of Chebyshev polynomials. Let us consider a general sum

Sn(x)=∑j=0najPj(x),(19)S_n(x)=\sum_{j=0}^{n}a_jP_j(x), \tag*{(19)}

where Pj(x)P_j(x) satisfies the recurrence relation

Pr+1(x)+αrPr(x)+βrPr−1(x)=0,(20)P_{r+1}(x)+\alpha_rP_r(x)+\beta_rP_{r-1}(x)=0, \tag*{(20)}

and αr\alpha_r, βr\beta_r may be functions of xx as well as of rr.

We construct the sequence bn,bn−1,⋯ ,b0b_n,b_{n-1},\cdots,b_0, where bn+1=bn+2=0b_{n+1}=b_{n+2}=0 and

br+αrbr+1+βr+1br+2=ar,(r=n,n−1,⋯ ,0).(21)b_r+\alpha_rb_{r+1}+\beta_{r+1}b_{r+2}=a_r,\qquad(r=n,n-1,\cdots,0). \tag*{(21)}

By replacing aja_j in (19) with the sequence {bj}\{b_j\} and using the recurrence relation (B2), we obtain

Sn(x)=b0P0(x)+b1{α0P0(x)+P1(x)}.(22)S_n(x)=b_0P_0(x)+b_1\{\alpha_0P_0(x)+P_1(x)\}. \tag*{(22)}

In the case of Chebyshev polynomials, we have

Pr(x)=Tr(x),α=−2x,β=1.(23)P_r(x)=T_r(x),\qquad\alpha=-2x,\qquad\beta=1. \tag*{(23)}

The recurrence relation is

br−2xbr+1+br+2=ar,(r=n,n−1,⋯ ,0).(24)b_r-2xb_{r+1}+b_{r+2}=a_r,\qquad(r=n,n-1,\cdots,0). \tag*{(24)}

The Chebyshev sum is

Sn(x)=∑j=0najTj(x)=b0−b1x.(25)S_n(x)=\sum_{j=0}^{n}a_jT_j(x)=b_0-b_1x. \tag*{(25)}

Acknowledgments

We are grateful to J. Hohl for editing the manuscript. The work was supported by NASA awards 80NSSC18K1122, 80NSSC20K1788, 80NSSC20K0917, and NSF award 2108582. We would like to acknowledge high-performance computing support from Cheyenne (doi:10.5065/D6RX99HX) provided by NCAR’s Computational and Information Systems Laboratory, sponsored by the National Science Foundation.

References

  1. [1]Ahmed, N., & Fisher, P. (1968). Study of algorithmic properties of chebyshev coefficients. International Journal of Computer Mathematics, 2(1-4), 307–317.DOI
  2. [2]Artemyev, A., Zhang, X.-J., Angelopoulos, V., Mourenas, D., Vainchtein, D., Shen, Y., … Runov, A. (2020). Ionosphere feedback to electron scattering by equatorial whistler mode waves. Journal of Geophysical Research: Space Physics, 125(9), e2020JA028373.DOI
  3. [3]Asano, Y., Nakamura, R., Shinohara, I., Fujimoto, M., Takada, T., Baumjohann, W., . . . others (2008). Electron flat-top distributions around the magnetic reconnection region. Journal of Geophysical Research: Space Physics, 113(A1).DOI
  4. [4]Aurentz, J. L., & Trefethen, L. N. (2017). Chopping a chebyshev series. ACM Transactions on Mathematical Software (TOMS), 43(4), 1–21.
  5. [5]Birdsall, C. K., & Langdon, A. B. (2018). Plasma physics via computer simulation. CRC press.
  6. [6]Burden, R. L., Faires, J. D., & Burden, A. M. (2015). Numerical analysis. Cengage learning.
  7. [7]Clenshaw, C. W. (1955). A note on the summation of chebyshev series. Mathematics of Computation, 9(51), 118–120.DOI
  8. [8]Damiano, P., Johnson, J., & Chaston, C. (2015). Ion temperature effects on magnetotail alfvén wave propagation and electron energization. Journal of Geophysical Research: Space Physics, 120(7), 5623–5632.
  9. [9]Driscoll, T. A., Hale, N., & Trefethen, L. N. (2014). Chebfun guide. Pafnuty Publications, Oxford.
  10. [10]Gentle, J. E. (2003). Random number generation and monte carlo methods (Vol. 381). Springer.
  11. [11]Givens, G. H., & Hoeting, J. A. (2012). Computational statistics (Vol. 703). John Wiley & Sons.DOI
  12. [12]Harrison, M. G., & Neukirch, T. (2009). One-dimensional vlasov-maxwell equilibrium for the force-free harris sheet. Physical Review Letters, 102(13), 135003.
  13. [13]Lembege, B., & Pellat, R. (1982). Stability of a thick two-dimensional quasineutral sheet. The Physics of Fluids, 25(11), 1995–2004.DOI
  14. [14]Mason, J. C., & Handscomb, D. C. (2002). Chebyshev polynomials. CRC press.
  15. [15]Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of state calculations by fast computing machines. The journal of chemical physics, 21(6), 1087–1092.
  16. [16]Olver, S., & Townsend, A. (2013). Fast inverse transform sampling in one and two dimensions. arXiv preprint arXiv:1307.1223.
  17. [17]Orszag, S. A. (1971a). Accurate solution of the orr–sommerfeld stability equation. Journal of Fluid Mechanics, 50(4), 689–703.DOI
  18. [18]Orszag, S. A. (1971b). Galerkin approximations to flows within slabs, spheres, and cylinders. Physical Review Letters, 26(18), 1100.
  19. [19]Platte, R. B., Trefethen, L. N., & Kuijlaars, A. B. (2011). Impossibility of fast stable approximation of analytic functions from equispaced samples. SIAM review, 53(2), 308–318.
  20. [20]Sinitsyn, A., Dulov, E., & Vedenyapin, V. (2011). Kinetic Boltzmann, Vlasov and Related Equations. Elsevier.DOI
  21. [21]Štverák, Š., Maksimovic, A., Trávníček, P. M., Marsch, E., Fazakerley, A. N., & Scime, E. E. (2009). Radial evolution of nonthermal electron populations in the low-latitude solar wind: Helios, cluster, and ulysses observations. Journal of Geophysical Research: Space Physics, 114(A5).
  22. [22]Townsend, A., & Trefethen, L. N. (2013). An extension of chebfun to two dimensions. SIAM Journal on Scientific Computing, 35(6), C495–C518.DOI
  23. [23]Trefethen, L. N. (2019). Approximation theory and approximation practice, extended edition. SIAM.DOI
  24. [24]Vasko, I., Agapitov, O., Mozer, F., Bonnell, J., Artemyev, A., Krasnoselskikh, V., . . . Hospodarsky, G. (2017). Electron-acoustic solitons and double layers in the inner magnetosphere. Geophysical Research Letters, 44(10), 4575–4583.DOI
  25. [25]Wilks, D. S. (2011). Statistical methods in the atmospheric sciences (Vol. 100). Academic press.
  26. [26]Wilson III, L. B., Chen, L.-J., Wang, S., Schwartz, S. J., Turner, D. L., Stevens, M. L., . . . others (2019). Electron energy partition across interplanetary shocks. i. methodology and data product. The Astrophysical Journal Supplement Series, 243(1), 8.

Paper details

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

views · 5

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