Skip to content
Projects

Fast multipole method

The fast multipole method computes the fields of line charges in O(N).

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]").

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

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.FMM field error against theta, for a few fixed orders.Loading figure…

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.the number of M2L and P2P node pairs the dual-tree traversal produces, against N; the interaction list grows linearly, not quadratically.Loading figure…

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.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.Loading figure…

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.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.Loading figure…

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]').