Simulating a flock means computing how every agent steers toward the average velocity of the agents around it. When each agent listens to many others, the cost grows with the square of the number of agents. That is already a problem in two dimensions and becomes far worse in three. The standard way out, borrowed from plasma physics, is particle-in-cell coupling: deposit the agents onto a mesh, compute the smoothed interaction fields there, and read the forces back at each agent. We propose a version of this for flocking in which agents stay as free particles but the long-range alignment fields are computed on a high-order discontinuous Galerkin mesh. A discontinuous Galerkin (DG) method stores a separate polynomial in each mesh cell and couples neighbouring cells only through their shared faces. In our scheme, depositing agents onto the mesh and reading forces back off it are exact mathematical transposes of each other. Under that construction the total momentum of the flock is conserved to machine precision, just as it is in the exact all-pairs model.
The reason to care is scientific, not only computational. Order in a flock comes from a contest between alignment and noise. Kun showed that flocks can undergo discontinuous, hysteretic order–disorder transitions as noise is varied (Keeping Speed and Distance for Aligned Motion). A mesh coupling that leaks or injects momentum adds noise of its own, and that numerical noise can move the very transition one is trying to measure. The effect should be worse in 3D: for a fixed agent count, the number of agents per mesh cell falls with the cube of the resolution, so deposition noise rises. Our core claim is that a conservative, high-order, positivity-limited DG coupling recovers the all-pairs transition point and hysteresis in 3D at agent-per-cell counts where conventional low-order coupling measurably shifts them. It does this in bounded domains with walls and obstacles, where Fourier-transform mesh solvers do not apply.
Core Claim
The Cucker–Smale model is the standard alignment model. Each agent $i$ with velocity $v_i$ at position $x_i$ feels a force $F_i = \frac{1}{N}\sum_j K(x_i - x_j)(v_j - v_i)$. Here $N$ is the number of agents and $K$ is a decreasing interaction kernel. This sum can be rewritten exactly as two field evaluations:
$$F_i = (K * m)(x_i) - v_i\,(K * \rho)(x_i),$$
where $\rho$ is the agents' number density and $m$ is their momentum density. The key design choice is to take $K$ to be the Green's function of a fourth-order screened operator. The Green's function is the field produced by a single point source, and in 3D it is bounded and decreasing: $K(r) \propto e^{-r/\ell}$, with $\ell$ the interaction length. With this choice, each field $\phi = K * \rho$ satisfies
$$(1 - \ell^2 \Delta)^2 \phi = \rho,$$
which splits into two second-order screened Poisson solves. Here $\Delta$ is the Laplacian. These elliptic problems suit hybridized DG (HDG), a DG variant that adds unknowns on cell faces so that cell interiors can be eliminated before the linear solve. Walls and obstacles then enter as ordinary boundary conditions.
Momentum conservation follows from three conditions. Deposition must be the $L^2$ projection of the particles onto the DG polynomial space. Force interpolation must be pointwise evaluation of the DG field, which is the transpose of that projection. The discrete solution operator must be symmetric, which a Galerkin discretization of a self-adjoint operator is. Under these conditions, the change in total momentum reduces to $\langle m_h, K_h \rho_h\rangle - \langle \rho_h, K_h m_h\rangle = 0$, where the subscript $h$ marks mesh quantities and $K_h$ is the discrete solution operator.
One danger remains. The projection of sparse particle data onto high-degree polynomials can produce negative density at some points. Negative density turns alignment into anti-alignment. We remove this with the cell-average-preserving physicality limiter of Glines et al., which damps the polynomial toward its cell average until it is physical again. Because the cell average is untouched, conservation survives the limiter.
Relation to Prior Work
Three lines of work motivate the proposal. Carrillo et al. derive the kinetic Cucker–Smale equation and prove exponential decay of velocity variance with bounds independent of $N$, but only for heavy-tailed kernels. Their work is purely theoretical: it has no walls or noise and no discretization. It motivates treating the flock through fields. Our exponential kernel falls in the conditional-flocking regime they leave open, so our simulations probe territory their theorems do not cover. Kun establishes 2D collision-driven alignment, a "Goldilocks" density at which order forms fastest, and hysteretic transitions. This supplies the observable we will measure in 3D. MAgent (Zheng et al.) reaches a million agents only by giving up continuous space and 3D. Flightmare (Song et al.) keeps full 3D dynamics but stops at about 150 vehicles. Together they mark the gap between scale and physical fidelity that we target.
Two papers supply the method. van Rees et al. couple Lagrangian particles to an HDG mesh through a conservation-constrained $\ell^2$ projection, achieving machine-precision local conservation. Their particles are passive fluid tracers. We reuse the projection idea for self-propelled agents, whose force feeds back nonlinearly on the particles. Wang and Pan show that 3D DG kernels map well onto GPUs with one cell per thread block. They report 10x–11x speedup on a V100 over an 8-core CPU, and they handle only smooth passive gas flow, with no limiter. We adopt their GPU layout and add the limiter that sparse agent data requires.
One cited line constrains the design. Sparse-grid DG for Vlasov-type models (Sparse-grid DG for Vlasov-Poisson-Lenard-Bernstein) shows how costly it is to discretize the full 3D-position plus 3D-velocity space. This is why we keep velocity on particles rather than meshing all six dimensions.
Research Program
We will build a GPU solver with four parts. First, agents are advanced in time with self-propulsion toward a cruise speed, as in Kun's model, plus angular noise of strength $\eta$. Second, short-range repulsion between agents is computed directly with a neighbour hash, since it is too sharp for any mesh. Third, the long-range alignment fields come from HDG screened-Poisson solves at polynomial degree $p = 0$ to $3$ on tetrahedral meshes. Fourth, the projection and interpolation are written as exact transposes, with the positivity limiter applied in between.
The analysis has two parts. We will prove semi-discrete momentum conservation. We will also try to prove monotone decay of velocity variance under the limiter, a discrete analogue of Carrillo's flocking functional. That second result is not guaranteed, and we will report it empirically if the proof fails.
The scientific deliverable answers three questions. Where does the noise-driven transition $\eta_c(\rho, \ell)$ sit for 3D flocks? Is that transition discontinuous with hysteresis, as Kun found in 2D? Does the optimal "Goldilocks" density survive when agents have an extra out-of-plane direction in which to escape collisions?
Baselines
The naive reference is direct all-pairs summation on the GPU, evaluating the full Cucker–Smale sum. It costs order $N^2$ per step but is exact. We will run it up to the largest $N$ that fits a fixed time budget, roughly $10^5$ agents. It defines ground truth for momentum drift, for the order parameter (the magnitude of the mean heading, which equals 1 at perfect alignment), and for $\eta_c$.
The strongest existing competitor is classical particle-mesh coupling. This uses cloud-in-cell or triangular-shaped-cloud deposition with matched interpolation and a Fourier-transform solve of the same screened operator. With matched shape functions it is also approximately momentum-conserving, so it is the method our claim must beat. It will receive the same mesh-cell budget, the same agent count, and the same timestep. Its smoothing width will be tuned with the same number of trial runs we give our own method.
The third baseline is spatial hashing with a truncated kernel, cut off at $c\,\ell$ with $c$ tuned for accuracy. This is the default way practitioners scale boids-style simulators.
For none of these does the file contain a reported number on continuous 3D flocking. We found no reported result on Lacuna for transition location, momentum drift, or throughput of 3D Cucker–Smale simulations. The nearest reported scale figures are MAgent's one million agents, achieved in a 2D gridworld, and Flightmare's 200,000 steps per second with 150 quadrotors. Neither is a like-for-like comparison, so we will generate all baseline numbers ourselves under matched settings.
Two ablations isolate the key ingredients. In the first, we break the transpose relation by interpolating with a smoothed nodal reconstruction instead of evaluating the DG field directly. This tests whether conservation, rather than polynomial order, is what fixes the transition point. In the second, we remove the positivity limiter. Beating a baseline means matching the all-pairs $\eta_c$ and hysteresis width within its statistical error, at fewer agents per cell or lower wall-clock time than the competitor needs to reach the same accuracy.
Why not just…?
Why not just use spatial hashing with a cutoff? For a kernel that decays exponentially, this is a real threat. When $\ell$ is small compared with the swarm, each agent has few neighbours, and hashing is close to exact at order-$N$ cost. Our method can only win when $\ell$ is comparable to the swarm size, so that each agent interacts with a sizeable fraction of the flock. The scaling experiment sweeps $\ell$ and reports the crossover honestly. If hashing wins everywhere in the range of $\ell$ that matters for flocking, the computational claim fails and only the bounded-domain results remain.
Why not just use standard particle-mesh coupling with a Fourier solver? In a periodic box, matched cloud-in-cell coupling may perform as well as ours. The periodic-box experiment is designed to show this either way. Fourier solvers do not handle walls or interior obstacles, which are exactly the conditions Carrillo et al. omit. DG at $p \ge 1$ should also need fewer agents per cell for the same accuracy, which matters most in 3D. The decisive test is therefore the bounded domain together with the sweep over agents per cell.
Why not just solve a continuum fluid model of the flock? A model that assigns one velocity to each point in space cannot represent the disordered phase, where agents at the same location move in different directions. That phase is half of the transition we want to measure. A full 6D kinetic solve is prohibitively expensive, as the sparse-grid literature shows. Keeping velocity on particles avoids both problems.
Why not just use low-order finite volumes on the mesh? DG at $p = 0$ is a finite-volume method of this kind, and it is included as an ablation. If $p = 0$ matches $p = 2$ at equal cost, high order adds nothing and we will say so.
Proposed Experiments
The first experiment checks correctness in a periodic 3D box with $N$ from $10^4$ to $10^5$, comparing every method against all-pairs summation. We measure momentum drift over $10^5$ steps and the order-parameter time series, and we check variance decay against the exponential form of Carrillo et al. in a weak-noise regime. We test convergence in $p$ and mesh size by reusing the projection-accuracy methodology of van Rees et al.
The second, decisive experiment sweeps noise upward and then downward at several densities. It measures $\eta_c$ and the hysteresis width for each method as agents per cell fall from about 100 to about 1. The prediction is that non-conservative and low-order couplings shift $\eta_c$ in a direction consistent with added effective noise, and that the conservative $p \ge 2$ scheme stays within the error bars of the all-pairs result.
The third experiment runs the same sweep in a bounded channel containing a spherical obstacle, and also reports whether the flock fragments. Here only DG and the hashing method can run, and the hashing method uses the all-pairs-matched cutoff.
The fourth experiment measures wall-clock time per step against $N$ up to $10^7$ and against $\ell$, on a single V100-class GPU, and locates the crossover with the hashing baseline. Finally, we repeat Kun's density sweep in 3D, with the 2D runs as a control, to test whether the Goldilocks density and the discontinuous transition persist.
References
- Keeping speed and distance for aligned motion
- A Robust, Performance-Portable Discontinuous Galerkin Method for Relativistic Hydrodynamics
- Asymptotic Flocking Dynamics for the Kinetic Cucker-Smale Model
- MAgent: A Many-Agent Reinforcement Learning Platform for Artificial Collective Intelligence
- Flightmare: A Flexible Quadrotor Simulator
- Constrained particle-mesh projections in a hybridized discontinuous Galerkin framework with applications to advection-dominated flows
- Three-dimensional discontinuous Galerkin based high-order gas-kinetic scheme and GPU implementation
- Sparse-grid discontinuous Galerkin methods for the Vlasov–Poisson–Lenard–Bernstein model