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.

Flags for particle-based trees

dtype
IS_SOURCE_BOX
IS_TARGET_BOX
IS_SOURCE_OR_TARGET_BOX
HAS_SOURCE_CHILD_BOXES
HAS_TARGET_CHILD_BOXES
HAS_SOURCE_OR_TARGET_CHILD_BOXES
IS_LEAF_BOX

Warning

IS_LEAF_BOX is only used for TreeOfBoxes for the moment.

class boxtree.TreeOfBoxes(root_extent: ndarray, box_centers: ndarray, box_parent_ids: ndarray, box_child_ids: ndarray, box_levels: ndarray, box_flags: ndarray | None, level_start_box_nrs: ndarray | None, box_id_dtype: dtype, box_level_dtype: dtype, coord_dtype: dtype, sources_have_extent: bool, targets_have_extent: bool, extent_norm: str, stick_out_factor: float, _is_pruned: bool)[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

mod:numpy array of shape (dim, nboxes) 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.

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

box_flags

box_flags_enum.dtype [nboxes]

A bitwise combination of box_flags_enum constants.

level_start_box_nrs

box_id_t [nlevels+1]

An array 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.

box_id_dtype
box_level_dtype
coord_dtype

See Tree documentation.

leaf_boxes

Array of leaf boxes.

sources_have_extent
targets_have_extent
extent_norm
stick_out_factor

See Tree documentation.

__init__(root_extent: ndarray, box_centers: ndarray, box_parent_ids: ndarray, box_child_ids: ndarray, box_levels: ndarray, box_flags: ndarray | None, level_start_box_nrs: ndarray | None, box_id_dtype: dtype, box_level_dtype: dtype, coord_dtype: dtype, sources_have_extent: bool, targets_have_extent: bool, extent_norm: str, stick_out_factor: float, _is_pruned: bool) → None
class boxtree.Tree(valuedict: Mapping[str, Any] | None = None, exclude: Sequence[str] | None = None, **kwargs: Any)[source]

A quad/octree consisting of particles sorted into a hierarchy of boxes.

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

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:

_images/linf-l2.png

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

nlevels
nboxes
nsources
ntargets
level_start_box_nrs

box_id_t [nlevels+1]

An array 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]

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: Mapping[str, Any] | None = None, exclude: Sequence[str] | None = None, **kwargs: Any)[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.

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: Mapping[str, Any] | None = None, exclude: Sequence[str] | None = None, **kwargs: Any)[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: Mapping[str, Any] | None = None, exclude: Sequence[str] | None = None, **kwargs: Any)[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().