This repository hosts the final report for the Theoretikum module at TU Dortmund (Fall 2024). The project investigates the complex behavior of hard sphere systems using Event-Chain Monte Carlo (ECMC) simulations.
Authors: Lukas A., Stefan N., Rene-Marcel L.
This project was a collaborative effort between three students. While the theoretical analysis and report generation were shared, we specialized in different technical implementations mid-project.
Specific contributions that are highlighted in this repository:
- Section 3: Advanced Simulation Techniques (Grid-based Ray Tracing).
- Section 8: Sedimentation of Hard Spheres.
Code Status: The simulation code for these sections was originally developed in C++ and later ported to Rust. Unfortunately, the source code is unavailable due to a data loss incident (self-inflicted WSL2 partition corruption following a not-self-inflicted Windows failure; hello Blue Screen).
Anticipating early on that we would specialize our codebases for distinct tasks, we relied on exchanging code snippets and files rather than maintaining a shared Git repository. Reflecting on this with the experience we have gained since, we would now undoubtedly utilize a centralized GitHub repository with feature branches. This repository serves as a permanent archive of the scientific methodology and results detailed in the report.
This study explores the complex behaviors of hard sphere systems, traditionally a baseline for more complex molecular dynamics. While the full report covers crystallization and 2D phase transitions, this summary focuses on the implementation of efficient event-chain algorithms and their application to sedimentation phenomena.
To overcome the scaling limits of standard collision detection, a custom spatial partitioning system was implemented specifically optimized for the Event-Chain Monte Carlo (ECMC) algorithm.
(a) Grid partitioning of the simulation volume into cells. Blue cells contain spheres. Only the center point of each sphere is considered; overlaps into multiple cells are not relevant.
(b) Comparison of naïve search and ray tracing in 2D. In the naïve approach, the chain vector serves as radius to determine the neighborhood, but checking shells iteratively leads to exponential cell growth. Blue center cell: starting cell. Blue cells indicate the traversed path, orange cells are additionally checked for collisions.
(c) Scaling behavior of both methods. The naïve method exhibits exponential growth in checked cells, while ray tracing maintains a constant number of checks per unit distance.
The Optimization Pipeline:
- Grid Decomposition (a): The simulation volume is discretized into a grid where the cell size corresponds strictly to the particle diameter. This creates a lookup table that maps particles to specific coordinates, reducing interactions from global to local.
- The Bottleneck of Naïve Search (b): Standard neighbor lists search a spherical volume around the active particle. In low-density systems where the mean free path is long, the "search radius" expands, forcing the algorithm to check an exponentially increasing number of empty cells (the "halo"). This results in cubic scaling .
- Ray Tracing Solution (c): To solve this, Bresenham’s line algorithm (classically used in computer graphics for drawing lines on pixels) was adapted to 3D simulation space. Instead of checking a volume, the algorithm calculates the exact flight path vector of the particle. It strictly traverses only the sequence of cells that the particle will actually enter.
Result: This shifts the complexity from scaling with volume to scaling with linear path length. The number of cell checks per unit of distance becomes constant, significantly outperforming shell-based methods in sparse systems.
The Event-Chain algorithm was extended to simulate particles under a gravitational field, allowing observation of phase transitions driven purely by local density changes within a single simulation box.
(a) Four possible events during movement in the positive z-direction: (1) gravitational event, where the particle exhausts its energy budget; (2) collision with another particle; (3) collision with a fixed wall; and (4) no event, where the particle moves freely.
(b) Bottom view of the lowest layers showing FCC and HCP structures for selected frames at different time intervals. Only particles in the height range 0 ≤ z ≤ 6.5 are displayed.
(c) 3D visualization of the system at different time points, highlighting the evolution of FCC and HCP crystal structures.
From Gravity to Thermodynamics:
- Implementing Gravity (a): Unlike standard Metropolis algorithms, gravity was handled via an "energy budget" method. A particle moving upwards against gravity "spends" kinetic energy. If it exhausts its budget before colliding, a "lifting event" occurs, reversing its vertical velocity. This creates a realistic sedimenting column with a dense bottom layer and a sparse top layer.
- Emergent Phase Transitions (b): The system naturally self-organizes into distinct phases based on height. As seen in Figure b, the bottom layers form into a solid, showing crystalline order (HCP/FCC stacking). There is a transition into a coexistence region, marked by strong density fluctuations, before settling into a fluid gas phase at the top.
- Physical Validation (c): To verify the correctness of the custom algorithm, the local pressure was derived from the density profile. In the report, the simulation data is compared against the theoretical Carnahan-Starling equation of state. The near-perfect agreement confirms that the modified Event-Chain algorithm correctly reproduces the thermodynamics of hard spheres under external fields.
This project was completed as part of the Theoretikum at TU Dortmund.
I would like to thank my colleagues Lukas A. and Stefan N. for their collaboration on the foundational event-chain algorithms. I really enjoyed our time in front of the whiteboard. It was a fun process with plenty of ups and downs as we wrestled with the logic.
[1] T. A. Kampmann et al. "Event-Chain Monte-Carlo Simulations of Dense Soft Matter Systems". In: Frontiers in Physics (2021).
[2] M. Michel, S. C. Kapfer, and W. Krauth. "Generalized event-chain Monte Carlo: Constructing rejection-free global-balance algorithms from infinitesimal steps". In: The Journal of Chemical Physics (2014).
[3] J. E. Bresenham. "Algorithm for Computer Control of a Digital Plotter". In: IBM Systems Journal (1965).
[4] Matthieu Marechal, Michiel Hermes, and Marjolein Dijkstra. "Stacking in sediments of colloidal hard spheres". In: The Journal of Chemical Physics (2011).
[5] L. Annuss, S. Nienhaus, and R.-M. Lehner. "Theoretikum: Final Report". TU Dortmund, 2024.