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
TreeBuilder. Note that
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.
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 Nonein the call to
one where a distinction between sources and targets is made. (
targets is not Nonein the call to
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 Noneand
source_radii is not None or target_radii is not Nonein the call to
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.target_radii specify the
radii of of \(l^\infty\) ‘circles’ (that is, squares) centered at
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.
There are four particle orderings:
user source order
tree source order (tree/box-sorted)
user target order
tree target order (tree/box-sorted)
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)
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
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
_startsarray has n+1 entries. The very last entry determines the length of the last list.
The lists in
_listsare stored contiguously. The start of the next list is automatically the end of the previous one.