Elsevier

Journal of Computational Physics

Volume 259, 15 February 2014, Pages 318-330
Journal of Computational Physics

Controlling the weights of simulation particles: adaptive particle management using k-d trees

https://doi.org/10.1016/j.jcp.2013.12.005Get rights and content

Abstract

In particle simulations, the weights of particles determine how many physical particles they represent. Adaptively adjusting these weights can greatly improve the efficiency of the simulation, without creating severe nonphysical artifacts. We present a new method for the pairwise merging of particles, in which two particles are combined into one. To find particles that are ‘close’ to each other, we use a k-d tree data structure. With a k-d tree, close neighbors can be searched for efficiently, and independently of the mesh used in the simulation. The merging can be done in different ways, conserving for example momentum or energy. We introduce probabilistic schemes, which set properties for the merged particle using random numbers. The effect of various merge schemes on the energy distribution, the momentum distribution and the grid moments is compared. We also compare their performance in the simulation of the two-stream instability.

Introduction

Particle-based simulations are widely used, for example to study fluid flows or plasmas. The physical particles of interest are often not simulated individually, but as groups of particles, called super-particles or macro-particles. Most systems contain so many particles that simulating them individually would be very slow or impossible. And for many macroscopic properties of a system, individual particle behavior is not important. On the other hand, a sufficient number of particles is required to limit stochastic fluctuations.

The weight of a simulation particle indicates how many physical particles it represents. Traditionally, particles had a fixed weight [1], [2]. More recently, Lapenta and Brackbill [3], [4], [5], Assous et al. [6], Welch et al. [7] and others have introduced methods that adapt the weight of particles during a simulation. As discussed in [6], adaptive methods have significant advantages if:

  • 1.

    Many new particles are created in the simulation. Adaptive re-weighting is required to limit the total number of particles. Examples can be found in [8] and [9].

  • 2.

    The system has a multiscale nature. In some regions more macro-particles are required, especially if some type of mesh refinement is employed, see for example [10].

  • 3.

    Control is needed over the number of particles per cell, for example to limit stochastic noise to a realistic value.

Our motivation for investigating the adaptive creation of super-particles originated from the simulation of streamer discharges, as these discharges have both a multiscale nature and strong source terms [9], [11].

When changing the weights of simulation particles, the goal is to reduce the number of simulation particles while not altering the physical evolution of the simulated system. Most methods operate on a single grid cell at a time; arguments for this approach are given in [5]. There are different ways to change the number of particles. One option is to merge two (or sometimes three) particles, to form particles with higher weights. Reversely, splitting can be performed to reduce weights. Another option is to replace all the particles in a cell by a new set of particles, with different weights. We will use the name ‘adaptive particle management’, introduced in [7], for all such algorithms.

We present a technique for the merging of particles, that extends earlier work of Lapenta [3]. This method can operate independently of the mesh, and in any space dimension. The main idea is to store the particle coordinates (typically position and velocity) in a k-d tree. A k-d tree is a space partitioning data structure that given N points enables searching for neighbors in O(logN) time [12]. We can then efficiently locate pairs of particles with similar coordinates, and these pairs can be merged. Because the merged particles are similar, the total distribution of particles is not significantly altered.

In Section 2, we briefly discuss the general principles of particle management and k-d trees. The implementation of the new particle management algorithm is discussed in Section 3, where we also introduce different ways to merge particles, which we call ‘merge schemes’. In Section 4, we compare how the merging of particles affects the particle distribution function for two test distributions. We also study the effect on the grid moments, such as the particle density, and compare different ways of constructing a k-d tree. As a more practical example, we show how the different merge schemes affect the evolution of the two-stream instability.

Section snippets

Adaptive particle management and k-d trees

As stated in the introduction, it is typically impossible to simulate all the physical particles in a system individually. Therefore super-particles are used, representing multiple physical particles. Often, the simulation can run faster or give more accurate results if the weight of these super-particles is controlled adaptively. Different names have been introduced for these algorithms: ‘adaptive particle management’ [7], ‘control of the number of particles’ [5], ‘particle coalescence’ [6],

Implementation

We will discuss the implementation of our adaptive particle management algorithm in Section 3.1. Different schemes that can be used for particle merging are given in Section 3.2.

Numerical tests and results

It is difficult to come up with a general test of the performance of an APM algorithm. The algorithm should not significantly alter the simulation results, compared to a run without super-particles. At the same time, it should decrease the computational cost as much as possible. But whether these criteria are met depends on the particular simulation that is performed. Therefore we first perform tests on a simplified 2D system, using two Gaussian velocity distributions. In these tests we do not

Conclusion

Adaptively adjusting the weights of simulated particles can greatly improve the efficiency of simulations. We follow Welch et al. [7] and call algorithms that do this ‘adaptive particle management’ (APM) algorithms. In this work, we have focused on the pairwise merging of particles. We found that the use of a k-d tree offers several important advantages over present methods. First, only particles that are ‘close together’ are merged. ‘Close together’ can be defined as desired (for example close

Acknowledgements

We would like to thank both referees for their comments, that significantly improved this article. J. Teunissen was supported by STW-project 10755.

References (16)

There are more references available in the full text version of this article.

Cited by (62)

  • Enhancing higher-energy spectral resolution for electron particle simulations in air

    2022, Computer Physics Communications
    Citation Excerpt :

    In this article, the suffix “super-” will be used for quantities that ignore the stochastic weight w of simulation particles when being calculated. To our knowledge, although several codes implemented various approaches for preferential particle sampling, their methodology systematically relies upon a simulation-domain partition into two [11], three [24], M [13], etc. respectively and is in some cases limited to particle pair-coalescence [25,26] which either imposes a restriction upon the particle resolution or relaxes the control over the number of simulation particles. Our methodology takes a different approach which preserves flexibility on resolution while maintaining control over the super-particle number.

View all citing articles on Scopus
View full text