Efficient collision algorithms in DSMC for rarefied gas dynamics: Markovian NTC-pre-scan and Bernoulli-trial schemes
Ahmad Shoja-Sani, Ehsan Roohi, Maryam Javani, Hassan Akhlaghi, Stefan Stefanov · Vacuum · 2026
The collision process is essential to the Direct Simulation Monte Carlo (DSMC) method, as it incorporates the fundamental principles of the Boltzmann and Kac stochastic equations. The primary impetus of this paper is to rectify a long-standing theoretical flaw in the widely used no-time-counter (NTC) collision algorithm. We demonstrate that the standard NTC scheme is fundamentally non-Markovian, relying on a fixed majorant product that introduces a system ‘memory’ and leads to inaccuracies at low particle counts. We propose a new algorithm, NTC-Pre-Scan, which transforms the scheme into a fully Markovian process. When repeated collisions are not crucial, our new NTC scheme, called NTC-Pre-Scan, can operate accurately with a very low number of particles per cell (PPC), with average PPC < 1 (e.g., PPC = 0.01), resulting in several empty cells in simulations. This contrasts with the standard NTC schemes, which typically require a PPC greater than 1. Then, a systematic evaluation of different Bernoulli-Trial (BT)-based collision partner selection schemes, including the simplified Bernoulli trials (SBT), generalized Bernoulli trials (GBT), symmetrized and simplified Bernoulli trials (SSBT), and the newly proposed symmetrized and generalized Bernoulli trials (SGBT), is conducted to treat some benchmark rarefied gas dynamics problems. The results show that the BT-based collision algorithms and NTC-Pre-scan successfully maintain the collision frequency as the number of particles per cell decreases. Simulation of the Bobylev-Krook-Wu (BKW) problem, for which an exact solution of the Boltzmann equation is available, indicates that, like the GBT, the SGBT algorithm yields the same results as theory for the average of the fourth moment of the velocity distribution function (VDF). The simulation on the three-dimensional computational grid for the GBT and SGBT schemes matches the fourth moment of the velocity component of the VDF exactly with the analytical solution. Performance analysis in a micro cavity reveals that the GBT, SSBT, and SGBT decrease the computational cost of simulation. Specifically, the computational cost of the SGBT scheme has been reduced by around 40 % when an appropriate selection number ( N sel ) is chosen, and this scheme requires a sample size of 0.62 of the NTC scheme. Finally, we demonstrate that all algorithms successfully capture complex flow phenomena, such as shock waves, in the case of hypersonic flow over a cylinder. Moreover, in the cylinder problem, the SGBT scheme can achieve the same level of accuracy with 28 % less computational cost and an outstanding sample size of 0.319 of the nearest neighbor (NN) scheme, which is the modern invariant of the NTC scheme. These advancements enable accurate simulation of rarefied gases with fewer particles (NTC-Pre-Scan) and lower computational cost (SGBT), which is directly beneficial for the design of complex vacuum systems.