Skip to content
tree-d-3d
Projects

The fast multipole method: O(N) fields of line charges.

Runs the experiments behind FlatQuadtree.fmm, the library’s O(N) fast multipole method for kernel="log", and saves one figure per claim:

Source: examples/fmm_scaling.py. Run it yourself with python examples/fmm_scaling.py [--output examples/output] [--quick] (needs pip install "tree-d-3d[examples]").

Figures

Section titled “Figures”

FMM field error against the expansion order, for a few theta; multipole expansions converge almost exponentially in the order.

FMM field error against theta, for a few fixed orders.

the number of M2L and P2P node pairs the dual-tree traversal produces, against N; the interaction list grows linearly, not quadratically.

wall-clock time against N for the direct sum, the Barnes-Hut tree walk and the FMM, on a log-log plot; the FMM overtakes the tree walk at large N.

the quadtree with one leaf box highlighted, its P2P (near-field, exact) partner leaves in one color and its M2L (far-field, multipole-translated) partner boxes in another.

--quick uses fewer particles and a narrower N range (well under a minute instead of a few minutes). Needs Plotly (pip install 'tree-d-3d[examples]').