Traversal building

Traversal data structure

class boxtree.traversal.FMMTraversalInfo

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 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, 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.

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 with boxtree.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 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)

Return a copy of self in which all data lives on the host, i.e. all pyopencl.array.Array objects are replaced by corresponding numpy.ndarray instances on the host.

merge_close_lists(queue, debug=False)

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)
Parameters
__call__(queue, tree, wait_for=None, debug=False, _from_sep_smaller_min_nsources_cumul=None)
Parameters
Returns

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