FMMS

Direct summation is exact and O(N²). At a million bodies, one force evaluation is a trillion interactions. Barnes–Hut drops that to O(N log N), but it gives up accuracy at the high end. The Fast Multipole Method groups distant bodies into multipole expansions and reaches O(N).

Getting the O(N) scaling is only half the battle. The real headache is keeping energy and momentum conserved while tracking down where the constant-factor overhead actually goes.

FMMS is a Dehnen-style dual-tree-walk solver. The tree, walk, and integrator are Rust; the math is written against a direct N² reference so every approximation has a check.

• Solid-harmonic expansions with an error-controlled multipole-acceptance criterion. The MAC factor of 8 is load-bearing for the rms error check.
• Rotation-accelerated M2L at O(p³) above p ≈ 20, with the naive O(p⁴) path below the measured crossover.
• Deterministic Plummer models, force comparison against direct summation, and energy and momentum checks.
• SoA body layout and a cache-blocked P2P kernel. The P2P kernel is already saturating the FP64 hardware ceiling.

I keep the library, benchmark binary, and live GPU visual harness separate in the workspace, so a visualization bug cannot hide in the solver.

48× vs direct

Single core, N=10⁶, p=8, ε=10⁻⁵, August 2026. The profile below uses eight threads.

Right now a full N=10⁶ step takes about 20 seconds. Almost all of that is spent in the tree walk and the two serial passes rather than the multipole math itself, which means the bottleneck is memory layout and parallelization rather than the algorithm.

Scaling fits N^0.91–1.0 from N=10³ to N=10⁶. The serial sweep runs 0.73s at N=10⁴ and 51.7s at N=10⁶. Momentum conservation holds to netF/|F| ≈ 10⁻¹⁵.

A 160-body Plummer sphere, virialized and run live in the browser. This is a direct-summation demo, not the Rust solver: at this size FMM's tree bookkeeping would cost more than it saves.

Reproduce the N=10⁶ phase profile:

cargo run --release -p fmm-bench -- 1000000 8 1e-5 1000000 8

Run the force, energy, and momentum checks:

cargo test --release

Next up: parallelizing those two serial passes and fixing the memory layout on the tree walk, so I can rerun the N=10⁶ benchmark without being bottlenecked by DRAM. After that: wider SIMD kernels and the GPU visual harness.