boxtree can do three main things:

  • it can build quad/octrees (in at least 1D/2D/3D), in one of two modes:

    • First, trees can be built as purely a collection of boxes, see Manipulating Trees of Boxes. These trees are typically built iteratively, through refinement and coarsening.

    • Second, trees can be built from collections of points, so that each box contains only a bounded number of these points. This is the older, less general way to construct trees that has a fairly heavy focus on point-based Fast Multipole Methods (FMMs). See Tree and TreeBuilder. Note that Tree inherits from TreeOfBoxes.

  • it can compute fast-multipole-like interaction lists on this tree structure, see boxtree.traversal. Note that while this traversal generation builds on the result of particle sorting, it is completely distinct in the software sense.

  • it can compute geometric lookup structures based on a Tree, see area_query.

Tree modes#

The particle-based Tree can operate in three ‘modes’:

  • one where no distinction is made between sources and targets. In this mode, all participants in the interaction are called ‘particles’. (targets is None in the call to boxtree.TreeBuilder.__call__())

  • one where a distinction between sources and targets is made. (targets is not None in the call to boxtree.TreeBuilder.__call__())

  • one where a distinction between sources and targets is made, and where sources and/or targets are considered to have an extent, given by an \(l^\infty\) radius. (targets is not None and source_radii is not None or target_radii is not None in the call to boxtree.TreeBuilder.__call__())

    If sources have an extent, it is possible to ‘link’ each source with a number of point sources. For this case, it is important to internalize this bit of terminology: A source may consist of multiple point sources.

Sources and targets with extent#

Tree.source_radii and Tree.target_radii specify the radii of of \(l^\infty\) ‘circles’ (that is, squares) centered at Tree.sources and Tree.targets that contain the entire extent of that source or target.

boxtree.traversal guarantees that, in generating traversals, all interactions to targets within the source extent and from sources within the target extent will invoke special (usually direct, non-multipole) evaluation.

Particle Orderings#

There are four particle orderings:

  • user source order

  • tree source order (tree/box-sorted)

  • user target order

  • tree target order (tree/box-sorted)

Tree.user_source_ids helps translate source arrays into tree order for processing. Tree.sorted_target_ids helps translate potentials back into user target order for output.

If each ‘original’ source above is linked to a number of point sources, the point sources have their own orderings:

  • user point source order

  • tree point source order (tree/box-sorted)

boxtree.tree.TreeWithLinkedPointSources.user_point_source_ids helps translate point source arrays into tree order for processing.

CSR-like interaction list storage#

Many list-like data structures in boxtree consists of two arrays, one whose name ends in _starts, and another whose name ends in _lists. For example, suppose we would like to find the colleagues of box #17 using boxtree.traversal.FMMTraversalInfo.colleagues_starts and boxtree.traversal.FMMTraversalInfo.colleagues_lists.

The following snippet of code achieves this:

ibox = 17
start, end = colleagues_starts[ibox:ibox+2]
ibox_colleagues = colleagues_lists[start:end]

This indexing scheme has the following properties:

  • If the underlying indexing array (say the list of all boxes) has n entries, then the _starts array has n+1 entries. The very last entry determines the length of the last list.

  • The lists in _lists are stored contiguously. The start of the next list is automatically the end of the previous one.