Controlling the weights of simulation particles: adaptive particle management using k-d trees
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.
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 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)
Particle rezoning for multidimensional kinetic particle-in-cell simulations
J. Comput. Phys.
(2002)- et al.
Dynamic and selective control of the number of particles in kinetic plasma simulations
J. Comput. Phys.
(1994) - et al.
Control of the number of particles in fluid and MHD particle in cell methods
Comput. Phys. Commun.
(1995) - et al.
A new method for coalescing particles in PIC codes
J. Comput. Phys.
(2003) - et al.
Adaptive particle management in a particle-in-cell code
J. Comput. Phys.
(2007) - et al.
A pic-mcc code for simulation of streamer propagation in air
J. Comput. Phys.
(2008) - et al.
Spatially hybrid computations for streamer discharges: II. Fully 3d simulations
J. Comput. Phys.
(2012) - et al.
Method to increase the simulation speed of particle-in-cell (PIC) code
Comput. Phys. Commun.
(2001)
Cited by (62)
Stochastic and self-consistent 3D modeling of streamer discharge trees with Kinetic Monte Carlo
2024, Journal of Computational PhysicsA dynamical particle merging and splitting algorithm for Particle-In-Cell simulations
2024, Computer Physics CommunicationsFLEKS: A flexible particle-in-cell code for multi-scale plasma simulations
2023, Computer Physics CommunicationsIntegrative simulation of a 2 cm electron cyclotron resonance ion source with full particle-in-cell method
2022, Computer Physics CommunicationsEnhancing higher-energy spectral resolution for electron particle simulations in air
2022, Computer Physics CommunicationsCitation 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.