Tree building

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

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

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().

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 ficitious box or (b) a disk surrounding the fictious 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\).

nsources
ntargets
nlevels
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.

Methods

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.

Tree with linked point sources

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

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 Tree. 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 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]

Methods

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.

Construction: Requires that 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 shoud fall within the \(l^\infty\) ‘circle’ around particle number isrc with the radius drawn from source_radii.

  • point_sources – an object array of (XYZ) point coordinate arrays.

Filtering the lists of targets

Data structures

class boxtree.tree.FilteredTargetListsInUserOrder

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)

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.

class boxtree.tree.FilteredTargetListsInTreeOrder

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)

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.

Tools

class boxtree.tree.ParticleListFilter(context)
filter_target_lists_in_tree_order(queue, tree, flags)
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)
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)

Deprecated. See ParticleListFilter.filter_target_lists_in_user_order().

boxtree.tree.filter_target_lists_in_tree_order(queue, tree, flags)

Deprecated. See ParticleListFilter.filter_target_lists_in_tree_order().

Build Entrypoint

class boxtree.TreeBuilder(context)
Parameters:context – A pyopencl.Context.
__call__(queue, particles, kind='adaptive', max_particles_in_box=None, allocator=None, debug=False, targets=None, source_radii=None, target_radii=None, stick_out_factor=None, refine_weights=None, max_leaf_refine_weight=None, wait_for=None, extent_norm=None, bbox=None, **kwargs)
Parameters:
  • queue – a pyopencl.CommandQueue instance
  • particles – an object array of (XYZ) point coordinate arrays.
  • kind

    One of the following strings:

    • ’adaptive’
    • ’adaptive-level-restricted’
    • ’non-adaptive’

    ’adaptive’ requests an adaptive tree without level restriction. See Supported tree kinds for further explanation.

  • targets – an object array of (XYZ) point coordinate arrays or None. If None, particles act as targets, too. Must have the same (inner) dtype as particles.
  • source_radii

    If not None, a pyopencl.array.Array of the same dtype as particles.

    If this is given, targets must also be given, i.e. sources and targets must be separate. See Sources and targets with extent.

  • target_radii – Like source_radii, but for targets.
  • stick_out_factor – See Tree.stick_out_factor and Sources and targets with extent.
  • refine_weights – If not None, a pyopencl.array.Array of the type numpy.int32. A box will be split if it has a cumulative refine_weight greater than max_leaf_refine_weight. If this is given, max_leaf_refine_weight must also be given and max_particles_in_box must be None.
  • max_leaf_refine_weight – If not None, specifies the maximum weight of a leaf box.
  • max_particles_in_box – If not None, specifies the maximum number of particles in a leaf box. If this is given, both refine_weights and max_leaf_refine_weight must be None.
  • wait_for – may either be None or a list of pyopencl.Event instances for whose completion this command waits before starting execution.
  • extent_norm"l2" or "linf". Indicates the norm with respect to which particle stick-out is measured. See Tree.extent_norm.
  • bbox

    Bounding box of either type: 1. A dim-by-2 array, with each row to be [min, max] coordinates

    in its corresponding axis direction.
    1. (Internal use only) of the same type as returned by boxtree.bounding_box.make_bounding_box_dtype.

    When given, this bounding box is used for tree building. Otherwise, the bounding box is determined from particles in such a way that it is square and is slightly larger at the top (so that scaled coordinates are always < 1). When supplied, the bounding box must be square and have all the particles in its closure.

  • kwargs – Used internally for debugging.
Returns:

a tuple (tree, event), where tree is an instance of Tree, and event is a pyopencl.Event for dependency management.