201× speedup over O(N2) exact at 0.55% force error Description SX-FlatTree is a pointerless, multi-level Barnes–Hut framework for gravitational N-body simulation, designed to eliminate pointer indirection, recursive traversal, and branch-heavy control flow inherent to classical octree implementations. The method encodes spatial hierarchy implicitly using Z-order Morton ordering, organizing particles into nested contiguous arrays (super-bodies, galaxies, clusters) that enable cache-prefetchable, fully iterative traversal. Evaluated at bodies on consumer-grade hardware, SX-FlatTree achieves a 201× speedup over exact computation at 0.55% mean relative force error, reducing evaluated interactions by 124× while preserving 76.6% exact near-field computation. We report the first empirical Pareto frontier of force error versus speedup for a pointerless Barnes–Hut implementation, identifying as the optimal operating point for sub-percent accuracy.
Andrés Sebastián Pirolo (Mon,) studied this question.