Traversal building¶
Traversal data structure¶

class
boxtree.traversal.
FMMTraversalInfo
¶ Interaction lists needed for a fastmultipolelike lineartime gather of particle interactions.
Terminology (largely) follows this article:
Carrier, J., Greengard, L. and Rokhlin, V. “A Fast Adaptive Multipole Algorithm for Particle Simulations.” SIAM Journal on Scientific and Statistical Computing 9, no. 4 (July 1988): 669686. DOI: 10.1137/0909044.
Unless otherwise indicated, all bulk data in this data structure is stored in a
pyopencl.array.Array
. See alsoget()
.
tree
¶ An instance of
boxtree.Tree
.

nboxes
¶ Number of boxe in the tree.

nlevels
¶ Number of levels in the tree.

well_sep_is_n_away
¶ The distance (measured in target box diameters in the \(l^\infty\) norm) from the edge of the target box at which the ‘wellseparated’ (i.e. M2Lhandled) ‘farfield’ starts.
Basic box lists for iteration

source_boxes
¶ box_id_t [*]
List of boxes having sources.

target_boxes
¶ box_id_t [*]
List of boxes having targets. If
boxtree.Tree.sources_are_targets
, thentarget_boxes is source_boxes
.

ntarget_boxes
¶ Number of
target_boxes
.

source_parent_boxes
¶ box_id_t [*]
List of boxes that are (directly or indirectly) a parent of one of the
source_boxes
. These boxes may have sources of their own.

level_start_source_box_nrs
¶ box_id_t [nlevels+1]
Indices into
source_boxes
indicating where each level starts and ends.

level_start_source_parent_box_nrs
¶ box_id_t [nlevels+1]
Indices into
source_parent_boxes
indicating where each level starts and ends.

target_or_target_parent_boxes
¶ box_id_t [*]
List of boxes that are one of the
target_boxes
or their (direct or indirect) parents.

ntarget_or_target_parent_boxes
¶ Number of
target_or_target_parent_boxes
.

level_start_target_box_nrs
¶ box_id_t [nlevels+1]
Indices into
target_boxes
indicating where each level starts and ends.

level_start_target_or_target_parent_box_nrs
¶ box_id_t [nlevels+1]
Indices into
target_or_target_parent_boxes
indicating where each level starts and ends.
Particleadaptive box extents
The attributes in this section are only available if the respective particle type (source/target) has extents. These capture the maximum extent of particles (including the particle’s extents) inside of the box. If the box is empty, both min and max will reflect the box center. The purpose of this information is to reduce the cost of some interactions through knowledge that some boxes are partially empty. (See the from_sep_smaller_crit argument to the constructor of
FMMTraversalBuilder
for an example.)Note
To obtain the overall, nonadaptive box extent, use
Tree.box_centers
along withTree.box_levels
.If they are not available, the corresponding attributes will be None.

box_source_bounding_box_min
¶ coordt_t [dimensions, aligned_nboxes]

box_source_bounding_box_max
¶ coordt_t [dimensions, aligned_nboxes]

box_target_bounding_box_min
¶ coordt_t [dimensions, aligned_nboxes]

box_target_bounding_box_max
¶ coordt_t [dimensions, aligned_nboxes]
Samelevel nonwellseparated boxes
Boxes considered to be within the ‘nonwellseparated area’ according to
well_sep_is_n_away
that are on the same level as their reference box. See CSRlike interaction list storage.This is a generalization of the “colleagues” concept from the Carrier paper to the case in which
well_sep_is_n_away
is not 1.
same_level_non_well_sep_boxes_starts
¶ box_id_t [nboxes+1]

same_level_non_well_sep_boxes_lists
¶ box_id_t [*]
Neighbor Sources (“List 1”)
List of source boxes immediately adjacent to each target box. Indexed like
target_boxes
. Includes the target box itself. See CSRlike interaction list storage. (Note: This list contains global box numbers, not indices intosource_boxes
.)
neighbor_source_boxes_starts
¶ box_id_t [ntarget_boxes+1]

neighbor_source_boxes_lists
¶ box_id_t [*]
Separated Siblings (“List 2”)
Wellseparated boxes on the same level. Indexed like
target_or_target_parent_boxes
. See CSRlike interaction list storage.
from_sep_siblings_starts
¶ box_id_t [ntarget_or_target_parent_boxes+1]

from_sep_siblings_lists
¶ box_id_t [*]
Separated Smaller Boxes (“List 3”)
Smaller source boxes separated from the target box by their own size.
If
boxtree.Tree.targets_have_extent
, thenfrom_sep_close_smaller_starts
will be nonNone. It records interactions between boxes that would ordinarily be handled through “List 3”, but must be evaluated specially/directly because of Sources and targets with extent.
target_boxes_sep_smaller_by_source_level
¶ A list of arrays of global box numbers, one array per level, indicating which boxes are used with the interaction list entries of
from_sep_smaller_by_level
.target_boxes_sep_smaller_by_source_level[i]
has lengthfrom_sep_smaller_by_level[i].num_nonempty_lists
.

from_sep_smaller_by_level
¶ A list of
boxtree.Tree.nlevels
(corresponding to the levels on which each listed source box resides) objects, each of which has attributes count, starts, lists, num_nonempty_lists, and nonempty_indices, which form a CSR list of List 3 source boxes.starts has shape/type
box_id_t [num_nonempty_lists+1]
. lists is of typebox_id_t
. (Note: This list contains global box numbers, not indices intosource_boxes
.)Note starts are indexed along with target_boxes_sep_smaller_by_source_level. For example, for level i, lists[starts[j]:starts[j+1]] represents “List 3” source boxes of target_boxes_sep_smaller_by_source_level[i][j] on level i.

from_sep_close_smaller_starts
¶ Indexed like
target_boxes
. See CSRlike interaction list storage.box_id_t [ntarget_boxes+1]
(or None)

from_sep_close_smaller_lists
¶ box_id_t [*]
(or None)
Separated Bigger Boxes (“List 4”)
Bigger source boxes separated from the target box by the (smaller) target box’s size. (Note: This list contains global box numbers, not indices into
source_boxes
.)If
boxtree.Tree.sources_have_extent
orboxtree.Tree.targets_have_extent
, thenfrom_sep_close_bigger_starts
will be nonNone. It records interactions between boxes that would ordinarily be handled through “List 4”, but must be evaluated specially/directly because of Sources and targets with extent.from_sep_bigger_starts is indexed like
target_or_target_parent_boxes
. Similar to the other “close” lists, from_sep_close_bigger_starts is indexed liketarget_boxes
. See CSRlike interaction list storage.
from_sep_bigger_starts
¶ box_id_t [ntarget_or_target_parent_boxes+1]

from_sep_bigger_lists
¶ box_id_t [*]

from_sep_close_bigger_starts
¶ box_id_t [ntarget_boxes+1]
(or None)

from_sep_close_bigger_lists
¶ box_id_t [*]
(or None)
Changed in version 2018.2: Changed index style of from_sep_close_bigger_starts from
target_or_target_parent_boxes
totarget_boxes
.
get
(queue, **kwargs)¶ Return a copy of self in which all data lives on the host, i.e. all
pyopencl.array.Array
objects are replaced by correspondingnumpy.ndarray
instances on the host.

merge_close_lists
(queue, debug=False)¶ Return a new
FMMTraversalInfo
instance with the contents offrom_sep_close_smaller_starts
andfrom_sep_close_bigger_starts
merged intoneighbor_source_boxes_starts
and these two attributes set to None.

Build Entrypoint¶

class
boxtree.traversal.
FMMTraversalBuilder
(context, well_sep_is_n_away=1, from_sep_smaller_crit=None)¶  Parameters
well_sep_is_n_away – Either An integer 1 or greater. (Only 1 and 2 are tested.) The spacing between boxes that is considered “wellseparated” for
from_sep_siblings
(List 2).from_sep_smaller_crit – The criterion used to determine separation box dimensions and separation for
from_sep_smaller_by_level
(List 3). May be one of"static_linf"
(use the box square, possibly enlarged byTree.stick_out_factor
),"precise_linf"` (use the precise extent of targets in the box, including their radii), or ``"static_l2"
(use the circumcircle of the box, possibly enlarged byTree.stick_out_factor
).

__call__
(queue, tree, wait_for=None, debug=False, _from_sep_smaller_min_nsources_cumul=None)¶  Parameters
queue – A
pyopencl.CommandQueue
instance.tree – A
boxtree.Tree
instance.wait_for – may either be None or a list of
pyopencl.Event
instances for whose completion this command waits before starting exeuction.
 Returns
A tuple (trav, event), where trav is a new instance of
FMMTraversalInfo
and event is apyopencl.Event
for dependency management.