Benchmarks

Two scripts produce everything on this page, and every table regenerates verbatim:

julia --project=docs docs/scripts/distributed_solve_benchmarks.jl   # solve cost, memory
julia --project=docs docs/scripts/distributed_solve_comparison.jl   # makespans, ordering, hops, wall clock

All measurements are on real harmonic-extension systems: sheaf Laplacians (stalk dimension 2, identity restriction maps) over each formation, targets pinned, $H$ the free–free Dirichlet block. Slot counts and memory are exact and machine-independent. Timings are minimum-of-runs on one machine.

Exactness

The workspace and distributed solves reproduce the monolithic CliqueTrees.Multifrontal answer to machine precision on every topology and size tested (max relative residual $\sim 2\times10^{-16}$), and the real four-process run below agrees to $9.5\times10^{-17}$. Nothing on this page trades accuracy for anything.

Communication makespan: the full tables

Slots to complete one solve (or reach $\varepsilon = 10^{-6}$, for the iterative methods), under the model of the comparison page. tree (ND) is the distributed tree under a nested-dissection ordering. The fewest-slots cell in each row is highlighted.

grid

chain

ring

star

The degenerate case: one hub sits in every separator, so the tree collapses to a single chunk and ties the coordinator, and nothing beats either.

random geometric

No nested-dissection construction is applied here, so the two tree columns coincide and share the win.

Two readings worth pulling out of the tables:

• On every formation with sublinear separators, tree-ND grows like the plots' flattest curve ($O(\log n)$) while both centralized variants grow linearly and the iterative methods grow with $\kappa(H)$.
• $\kappa(H)$ itself grows with formation size (it is over $10^5$ on the 510-agent chain), so diffusion's disadvantage compounds with scale. Its locality is not the bottleneck. Its conditioning bill is.

The ordering study

The elimination ordering sets the tree's depth, and the depth sets the makespan. Nested dissection here is three lines of Julia (recursively eliminate interval/box middles last), with no external graph partitioner:

Smaller of each metric pair highlighted: nested dissection wins depth and slots, the default order wins fill, which is the trade the study is about.

The trade is explicit: on the 510-agent chain, nested dissection buys a 36× makespan reduction (1014 → 28 slots) for a 1.9× fill increase (2032 → 3948 stored entries). Depth tracks the $\log_2 n$ guide line almost exactly. For a deployment this is nearly always the right trade, since communication slots are wall-clock and battery, and a doubled factor is kilobytes.

The physical routing overlay

Measured hop distributions for tree messages over the physical radio graph (discussion and caveats on the comparison page):

Solve cost on one machine

The preallocated TreeWorkspace solve tracks the monolithic CliqueTrees solve within a few percent (the allocating recursive reference is $\approx 5\times$ slower), and the per-step re-solve is roughly an order of magnitude cheaper than the factorization it reuses. Every "per-step" number in this guide is a re-solve against a cached factor. The factorization is paid once per formation and reported separately.

A real multi-process run

Local worker processes share one machine, so this measures serialization and channel protocol overhead and verifies exactness. It is not a radio simulation (the slot tables are the communication model). The number worth keeping is that this is real inter-process message passing, exact to the last bit.

Per-agent memory

The per-worker slices are balanced around their mean and sum exactly to the centralized factor, so there is zero duplication, by the disjoint-residuals argument of the multifrontal page. On a 24×24 grid across twelve workers, the busiest worker holds 12% of the full factor.