Building interaction lists#

Traversal data structure#

class boxtree.traversal.FMMTraversalInfo(valuedict=None, exclude=None, **kwargs)[source]#

Interaction lists needed for a fast-multipole-like linear-time 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): 669-686. DOI: 10.1137/0909044.

Unless otherwise indicated, all bulk data in this data structure is stored in a pyopencl.array.Array. See also get().

tree#: An instance of boxtree.Tree.

nboxes#: Number of boxes 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 ‘well-separated’ (i.e. M2L-handled) ‘far-field’ 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, then target_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.

Same-level non-well-separated boxes

Boxes considered to be within the ‘non-well-separated area’ according to well_sep_is_n_away that are on the same level as their reference box. See CSR-like 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 [*]

Following attributes are deprecated.

colleagues_starts#: box_id_t [nboxes+1]

colleagues_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 CSR-like interaction list storage. (Note: This list contains global box numbers, not indices into source_boxes.)

neighbor_source_boxes_starts#: box_id_t [ntarget_boxes+1]

neighbor_source_boxes_lists#: box_id_t [*]

Separated Siblings (“List 2”)

Well-separated boxes on the same level. Indexed like target_or_target_parent_boxes. See CSR-like 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, then from_sep_close_smaller_starts will be non-None. 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 length from_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 type box_id_t. (Note: This list contains global box numbers, not indices into source_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 CSR-like 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 or boxtree.Tree.targets_have_extent, then from_sep_close_bigger_starts will be non-None. 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 like target_boxes. See CSR-like 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 to target_boxes.

get(queue, **kwargs)[source]#: Return a copy of self in which all data lives on the host, i.e. all pyopencl.array.Array and ImmutableHostDeviceArray objects are replaced by corresponding numpy.ndarray instances on the host.

merge_close_lists(queue, debug=False)[source]#: Return a new FMMTraversalInfo instance with the contents of from_sep_close_smaller_starts and from_sep_close_bigger_starts merged into neighbor_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)[source]#

__init__(context, well_sep_is_n_away=1, from_sep_smaller_crit=None)[source]#

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 “well-separated” for boxtree.traversal.FMMTraversalInfo.from_sep_siblings_starts (List 2).
from_sep_smaller_crit – The criterion used to determine separation box dimensions and separation for boxtree.traversal.FMMTraversalInfo.from_sep_smaller_by_level (List 3). May be one of "static_linf" (use the box square, possibly enlarged by boxtree.Tree.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 by boxtree.Tree.stick_out_factor).

__call__(queue, tree, wait_for=None, debug=False, _from_sep_smaller_min_nsources_cumul=None, source_boxes_mask=None, source_parent_boxes_mask=None)[source]#

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.
source_boxes_mask – Only boxes passing this mask will be considered for source_boxes. Used by the distributed implementation.
source_parent_boxes_mask – Only boxes passing this mask will be considered for source_parent_boxes. Used by the distributed implementation.

Returns:

A tuple (trav, event), where trav is a new instance of FMMTraversalInfo and event is a pyopencl.Event for dependency management.

Rotation classes data structure#

class boxtree.rotation_classes.RotationClassesInfo(valuedict=None, exclude=None, **kwargs)[source]#

Interaction lists to help with matrix precomputations for rotation-based translations (“point and shoot”).

nfrom_sep_siblings_rotation_classes#: The number of distinct rotation classes.

from_sep_siblings_rotation_classes#

int32 [*]

A list, corresponding to from_sep_siblings_lists of trav, of the rotation class of each box pair.

from_sep_siblings_rotation_class_to_angle#

coord_t [nfrom_sep_siblings_rotation_classes]

Maps rotation classes in from_sep_siblings_rotation_classes to rotation angles. This represents the angle between box translation pairs and the z-axis.

Build rotation classes#

class boxtree.rotation_classes.RotationClassesBuilder(context)[source]#

Build rotation classes for List 2 translations.

__init__(context)[source]#

__call__(queue, trav, tree, wait_for=None)[source]#: Returns a pair info, evt where info is a RotationClassesInfo.

Translation classes data structure#

class boxtree.translation_classes.TranslationClassesInfo(traversal, **kwargs)[source]#

Interaction lists to help with for translations that benefit from precomputing distance related values

nfrom_sep_siblings_translation_classes#: The number of distinct translation classes.

from_sep_siblings_translation_classes#

int32 [*]

A list, corresponding to from_sep_siblings_lists of traversal, of the translation classes of each box pair.

from_sep_siblings_translation_class_to_distance_vector#

coord_vec_t [nfrom_sep_siblings_translation_classes]

Maps translation classes in from_sep_siblings_translation_classes to distance (translation) vectors from source box center to target box center.

from_sep_siblings_translation_classes_level_starts#

int32 [nlevels + 1]

A list with an entry for each level giving the starting translation class id for that level. Translation classes are numbered contiguously by level.

traversal#: A boxtree.traversal.FMMTraversalInfo object corresponding to the traversal that these translation classes refer to.

Build translation classes#

class boxtree.translation_classes.TranslationClassesBuilder(context)[source]#

Build translation classes for List 2 translations.

__init__(context)[source]#

__call__(queue, trav, tree, wait_for=None, is_translation_per_level=True)[source]#: Returns a pair info, evt where info is a TranslationClassesInfo.