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 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 ‘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
, 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.
Particle-adaptive 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, non-adaptive box extent, use
boxtree.Tree.box_centers
along withboxtree.Tree.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]
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 intosource_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
, thenfrom_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 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 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
orboxtree.Tree.targets_have_extent
, thenfrom_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 liketarget_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
totarget_boxes
.- get(queue, **kwargs)[source]¶
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)[source]¶
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)[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 byboxtree.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 byboxtree.Tree.stick_out_factor
).
- __call__(queue, tree, wait_for=None, debug=False, _from_sep_smaller_min_nsources_cumul=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.
- Returns
A tuple (trav, event), where trav is a new instance of
FMMTraversalInfo
and event is apyopencl.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¶
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.
- __call__(queue, trav, tree, wait_for=None, is_translation_per_level=True)[source]¶
Returns a pair info, evt where info is a
TranslationClassesInfo
.