Tree Data Structures#

Supported tree kinds#

The following tree kinds are supported:

Nonadaptive trees have all leaves on the same (last) level.
Adaptive trees differ from nonadaptive trees in that they may have leaves on more than one level. Adaptive trees have the option of being level-restricted: in a level-restricted tree, neighboring leaves differ by at most one level.

All trees returned by the tree builder are pruned so that empty leaves have been removed. If a level-restricted tree is requested, the tree gets constructed in such a way that the version of the tree before pruning is also level-restricted.

Tree data structure#

class boxtree.box_flags_enum[source]#

Constants for box flags bit field.

HAS_CHILDREN = 12#

HAS_CHILD_SOURCES = 4#

HAS_CHILD_TARGETS = 8#

HAS_OWN_SOURCES = 1#

HAS_OWN_SRCNTGTS = 3#

HAS_OWN_TARGETS = 2#

c_name = 'box_flags_t'#

c_value_prefix = 'BOX_'#

dtype = dtype('uint8')#

class boxtree.TreeOfBoxes(box_centers: ndarray[Any, dtype[ScalarType]], root_extent: ndarray[Any, dtype[ScalarType]], box_parent_ids: ndarray[Any, dtype[ScalarType]], box_child_ids: ndarray[Any, dtype[ScalarType]], box_levels: ndarray[Any, dtype[ScalarType]])[source]#

A quad/octree tree of pure boxes, excluding their contents (e.g. particles). It is a lightweight tree handled with numpy, intended for mesh adaptivity. One may generate a meshmode.mesh.Mesh object consisting of leaf boxes using make_meshmode_mesh_from_leaves().

dimensions#

nlevels#

nboxes#

root_extent#: (Scalar) extent of the root box.

box_centers#: dim-by-nboxes numpy array of the centers of the boxes.

box_parent_ids#: numpy vector of parent box ids.

box_child_ids#: (2**dim)-by-nboxes numpy array of children box ids.

box_levels#: numpy vector of box levels in non-decreasing order.

leaf_flags#: numpy vector of whether a box is leaf.

leaf_boxes#: numpy vector of leaf boxes.

__init__(box_centers: ndarray[Any, dtype[ScalarType]], root_extent: ndarray[Any, dtype[ScalarType]], box_parent_ids: ndarray[Any, dtype[ScalarType]], box_child_ids: ndarray[Any, dtype[ScalarType]], box_levels: ndarray[Any, dtype[ScalarType]]) → None#

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

A quad/octree consisting of particles sorted into a hierarchy of boxes that inherits from TreeOfBoxes. Optionally, particles may be designated ‘sources’ and ‘targets’. They may also be assigned radii which restrict the minimum size of the box into which they may be sorted.

Instances of this class are not constructed directly. They are returned by TreeBuilder.__call__().

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

Inherits from TreeOfBoxes.

Flags

sources_are_targets#

bool

Whether sources and targets are the same

sources_have_extent#

bool

Whether this tree has sources in non-leaf boxes

targets_have_extent#

bool

Whether this tree has targets in non-leaf boxes

Data types

particle_id_dtype#

box_id_dtype#

coord_dtype#

box_level_dtype#

Counts and sizes

root_extent#: the root box size, a scalar

stick_out_factor#

A scalar used for calculating how much particles with extent may overextend their containing box.

Each box in the tree can be thought of as being surrounded by a fictitious box whose \(l^\infty\) radius is 1 + stick_out_factor larger. Particles with extent are allowed to extend inside (a) the fictitious box or (b) a disk surrounding the fictitious box, depending on extent_norm.

extent_norm#

One of None, "l2" or "linf". If None, particles do not have extent. If not None, indicates the norm with which extent-bearing particles are determined to lie ‘inside’ a box, taking into account the box’s stick_out_factor.

This image illustrates the difference in semantics:

In the figure, the box has (\(\ell^\infty\)) radius \(R\), the particle has radius \(r\), and stick_out_factor is denoted \(\alpha\).

nsources#

ntargets#

nlevels#

nboxes#

bounding_box#: a tuple (bbox_min, bbox_max) of numpy vectors giving the (built) extent of the tree. Note that this may be slightly larger than what is required to contain all particles.

level_start_box_nrs#

box_id_t [nlevels+1]

A numpy.ndarray of box ids indicating the ID at which each level starts. Levels are contiguous in box ID space. To determine how many boxes there are in each level, access the start of the next level. This array is built so that this works even for the last level.

level_start_box_nrs_dev#

particle_id_t [nlevels+1]

The same array as level_start_box_nrs as a pyopencl.array.Array.

Per-particle arrays

sources#

coord_t [dimensions][nsources] (an object array of coordinate arrays)

Stored in tree source order. May be the same array as targets.

source_radii#

coord_t [nsources] \(l^\infty\) radii of the sources.

Available if sources_have_extent is True.

targets#

coord_t [dimensions][ntargets] (an object array of coordinate arrays)

Stored in tree target order. May be the same array as sources.

target_radii#

coord_t [ntargets]

\(l^\infty\) radii of the targets. Available if targets_have_extent is True.

Tree/user order indices

See Particle Orderings.

user_source_ids#

particle_id_t [nsources]

Fetching from these indices will reorder the sources from user source order into tree source order.

sorted_target_ids#

particle_id_t [ntargets]

Fetching from these indices will reorder the targets from tree target order into user target order.

Box properties

box_source_starts#

particle_id_t [nboxes]

List of sources in each box. Records start indices in sources for each box. Use together with box_source_counts_nonchild or box_source_counts_cumul. May be the same array as box_target_starts.

box_source_counts_nonchild#

particle_id_t [nboxes]

List of sources in each box. Records number of sources from sources in each box (excluding those belonging to child boxes). Use together with box_source_starts. May be the same array as box_target_counts_nonchild.

box_source_counts_cumul#

particle_id_t [nboxes]

List of sources in each box. Records number of sources from sources in each box and its children. Use together with box_source_starts. May be the same array as box_target_counts_cumul.

box_target_starts#

particle_id_t [nboxes]

List of targets in each box. Records start indices in targets for each box. Use together with box_target_counts_nonchild or box_target_counts_cumul. May be the same array as box_source_starts.

box_target_counts_nonchild#

particle_id_t [nboxes]

List of targets in each box. Records number of targets from targets in each box (excluding those belonging to child boxes). Use together with box_target_starts. May be the same array as box_source_counts_nonchild.

box_target_counts_cumul#

particle_id_t [nboxes]

List of targets in each box. Records number of targets from targets in each box and its children. Use together with box_target_starts. May be the same array as box_source_counts_cumul.

box_parent_ids#

box_id_t [nboxes]

Box 0 (the root) has 0 as its parent.

box_child_ids#

box_id_t [2**dimensions, aligned_nboxes] (C order, ‘structure of arrays’)

“0” is used as a ‘no child’ marker, as the root box can never occur as any box’s child.

box_centers#: coord_t [dimensions, aligned_nboxes] (C order, ‘structure of arrays’)

box_levels#: box_level_dtype box_level_t [nboxes]

box_flags#

box_flags_enum.dtype [nboxes]

A bitwise combination of box_flags_enum constants.

Particle-adaptive box extents

These attributes 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 boxtree.traversal.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]

Methods

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.

Tree with linked point sources#

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

In this boxtree.Tree subclass, the sources of the original tree are linked with extent are expanded into point sources which are linked to the extent-having sources in the original tree. (In an FMM context, they may stand in for the ‘underlying’ source for the purpose of the far-field calculation.) Has all the same attributes as boxtree.Tree. boxtree.Tree.sources_have_extent is always True for instances of this type. In addition, the following attributes are available.

npoint_sources#

point_source_starts#

particle_id_t [nsources]

The array point_sources[:][point_source_starts[isrc]: point_source_starts[isrc]+point_source_counts[isrc]] contains the locations of point sources corresponding to the ‘original’ source with index isrc. (Note that this expression will not entirely work because point_sources is an object array.)

This array is stored in tree point source order, unlike the parameter to boxtree.tree.TreeWithLinkedPointSources.__init__()

point_source_counts#: particle_id_t [nsources] (See point_source_starts.)

point_sources#

coord_t [dimensions][npoint_sources] (an object array of coordinate arrays)

Stored in tree point source order.

user_point_source_ids#

particle_id_t [nsources]

Fetching from these indices will reorder the sources from user point source order into tree point source order.

box_point_source_starts#: particle_id_t [nboxes]

box_point_source_counts_nonchild#: particle_id_t [nboxes]

box_point_source_counts_cumul#: particle_id_t [nboxes]

__init__()[source]#: This constructor is not intended to be called by users directly. Call link_point_sources() instead.

Methods

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.

boxtree.tree.link_point_sources(queue, tree, point_source_starts, point_sources, debug=False)[source]#

Construction: Requires that boxtree.Tree.sources_have_extent is True on tree.

Parameters:

queue – a pyopencl.CommandQueue instance
point_source_starts –
point_source_starts[isrc] and point_source_starts[isrc+1] together indicate a ranges of point particle indices in point_sources which will be linked to the original (extent-having) source number isrc. isrc is in user source order.

All the particles linked to isrc should fall within the \(l^\infty\) ‘circle’ around particle number isrc with the radius drawn from boxtree.Tree.source_radii.
point_sources – an object array of (XYZ) point coordinate arrays.

Filtering the lists of targets#

Data structures#

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

Use ParticleListFilter.filter_target_lists_in_user_order() to create instances of this class.

This class represents subsets of the list of targets in each box (as given by boxtree.Tree.box_target_starts and boxtree.Tree.box_target_counts_cumul). This subset is specified by an array of flags in user target order.

The list consists of target numbers in user target order. See also FilteredTargetListsInTreeOrder.

nfiltered_targets#

target_starts#

particle_id_t [nboxes+1]

Filtered list of targets in each box. Records start indices in boxtree.Tree.targets for each box. Use together with target_lists. The lists for each box are contiguous, so that target_starts[ibox+1] records the end of the target list for ibox.

target_lists#

particle_id_t [nboxes]

Filtered list of targets in each box. Records number of targets from boxtree.Tree.targets in each box (excluding those belonging to child boxes). Use together with target_starts.

Target numbers are stored in user order, as the class name suggests.

Methods

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.

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

Use ParticleListFilter.filter_target_lists_in_tree_order() to create instances of this class.

This class represents subsets of the list of targets in each box (as given by boxtree.Tree.box_target_starts and boxtree.Tree.box_target_counts_cumul).This subset is specified by an array of flags in user target order.

Unlike FilteredTargetListsInUserOrder, this does not create a CSR-like list of targets, but instead creates a new numbering of targets that only counts the filtered targets. This allows all targets in a box to be placed consecutively, which is intended to help traversal performance.

nfiltered_targets#

box_target_starts#

particle_id_t [nboxes]

Filtered list of targets in each box, like boxtree.Tree.box_target_starts. Records start indices in targets for each box. Use together with box_target_counts_nonchild.

box_target_counts_nonchild#

particle_id_t [nboxes]

Filtered list of targets in each box, like boxtree.Tree.box_target_counts_nonchild. Records number of sources from targets in each box (excluding those belonging to child boxes). Use together with box_target_starts.

targets#: coord_t [dimensions][nfiltered_targets] (an object array of coordinate arrays)

unfiltered_from_filtered_target_indices#: Storing to these indices will reorder the targets from filtered tree target order into ‘regular’ tree target order.

Methods

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.

Tools#

class boxtree.tree.ParticleListFilter(context)[source]#

filter_target_lists_in_tree_order(queue, tree, flags)[source]#

Parameters:: flags – an array of length boxtree.Tree.ntargets of numpy.int8 objects, which indicate by being zero that the corresponding target (in user target order) is not part of the filtered list, or by being nonzero that it is.
Returns:: A FilteredTargetListsInTreeOrder

filter_target_lists_in_user_order(queue, tree, flags)[source]#

Parameters:: flags – an array of length boxtree.Tree.ntargets of numpy.int8 objects, which indicate by being zero that the corresponding target (in user target order) is not part of the filtered list, or by being nonzero that it is.
Returns:: A FilteredTargetListsInUserOrder

boxtree.tree.filter_target_lists_in_user_order(queue, tree, flags)[source]#: Deprecated. See ParticleListFilter.filter_target_lists_in_user_order().

boxtree.tree.filter_target_lists_in_tree_order(queue, tree, flags)[source]#: Deprecated. See ParticleListFilter.filter_target_lists_in_tree_order().