There are some concepts that show up in many places in the pybbfmm docs, so they’re collected together here.
arrdicts and dotdicts¶
dotdicts and arrdicts are somewhere between dictionaries and classes, and are a crutch for research code that I’m immensely fond of. The megastep docs have a lot more detail.
A problem is a dotdict that describes the problem you’re trying to solve. A problem dotdict has keys
A (n_sources, D)-tensor giving the D-dimensional locations of the source charges.
A (n_targets, D)-tensor giving the D-dimensional locations of the target points you want to evaluate the field at.
A (n_sources,)-tensor giving the ‘charge’ at each source point.
A function that takes a tensor of source locations and a tensor of target locations and returns the strength of the sources’ fields at the target points. For example, an inverse-square law uses a kernel
def quad_kernel(a, b): return 1/((a - b)**2).sum(-1)
One important restriction is that multiple targets and sources should not have the exact same location. Otherwise the tree construction might not terminate.
Presolve: trees, indices & schemes¶
presolve() computes a bunch of metadata based on only the positions of the problem’s points and the
kernel used. This presolve metadata can then be used for as many evaluations on different charges as you
If you ever get confused about any presolve metadata, the best way to figure things out is to generate the metadata for a low-capacity, 1D problem:
from pybbfmm import * from pybbfmm.test import * prob = arrdict.arrdict( sources=np.array([[-1], [+.5], [+1]]), charges=np.zeros((3,)), targets=np.array([[0.]]) ).map(lambda t: torch.as_tensor(t).float()) prob['kernel'] = quad_kernel presolve(prob)
There are two steps to the presolve. The first step is to build a tree over the sources and targets, which is done by
orthantree(). It returns three things: the tree, the indices and the depths. These
are described below.
The most important bit of presolve information is the tree. The tree is the binary partition of space that’s used
to figure out which sources it’s okay to approximate when calculating which points. It’s usually constructed by
orthantree() and looks something like this
TODO: imagery of a tree
The internal nodes of the tree are called boxes. The boxes are represented as an index, with the root being index 0.
This means that you’ll usually find the attribute of box
i at index
i of a tensor:
parents gives the
index of the parent of
children gives the children of
3, etc etc.
The tree is represented as an arrdict of tensors. Each tensor is n_boxes long, and gives a different property of the boxes:
Give the boxes’ ID, which is just… its index. Useful to have around, not actually informative.
Gives the boxes’ parents. The
ith element is the index of box
Gives the boxes’ depth in the tree. The
ith element is the depth of box
i, with zero corresponding to the root.
Gives coordinates of the boxes’ centers. The
ith element… you get the idea.
Gives a boolean saying whether that box is a leaf. True means the box is a leaf; that it has no children.
Gives the boxes’ children. The
i``th element is an (2,)/(2, 2)/(2, 2, 2)/etc-tensor of the 2 :sup:`D` children of box ``i.
Gives the boxes’ descent: whether it’s a left-child or a right-child, etc etc. Practically this means the
ith element is a (D,)-vector of (-1, +1)’s, with the value indicating which side of the parent’s center the box is on.
While the tree arrdict itself gives the relationships between the boxes of the tree, it doesn’t have any information
about how the sources and targets relate to the boxes. That’s done by the second return from
indices. This is a dotdict with two elements
A (n_source,)-tensor where the
ith element gives which box the
ith source is in
A (n_target,)-tensor where the
ith element gives which box the
ith target is in
The second step in the presolve is to take all the information from the tree construction stage and use it to generate the interaction lists. The interaction lists describe which boxes, sources and targets interact with which other boxes, sources and targets.
Keeping actual lists of all the pairs of interacting entities is memory-inefficient, so instead what’s generated at this step is enough information to be able to rapidly construct the interacting-entity lists on demand. This information is - for the purposes of this library - called the scheme for the list. There are four lists, so there are four schemes.
The four interaction lists come from 1. The most useful parts of the paper are §3.2, Notation, along with Fig 5.
u: the u-list of a leaf box is the set of neighbouring leaf boxes.
v: the v-list of a box is the children of the parent’s colleagues that are separated from the box.
w: the w-list of a leaf is the set of descendents of colleagues whose parents are adjacent but which aren’t
x: the x-list of a box is set of all boxes for which this box turns up in the other box’s
Believe you me: understanding these is much easier once you’ve read §3.2 and had a hard look at Fig 5.
Evaluate: weights, interactions & contributions¶
Once the presolve is done, actually solving the problem is done by
takes the presolve metadata and uses it to compute the weights, then the interactions, then the contributions.
Summing the contributions gets the solution.
weights()are effectively Chebyshev-approximations of the charge density across each cell. They’re evaluated by starting at the bottom of the tree, at the leaf boxes, and recursively merging approximations until the algorithm reaches the root.
The interactions use the weights calculated previously to evaluate the field contributions between specific pairs of boxes, sources and targets. These pairs come from the u-, v-, w-, x- schemes described above. They’re evaluated as the algorithm moves from the root down the tree
When the algorithm returns to the leaf boxes, through the interaction calculations it’s accumulated a
far_field()approximation of how all the sources that are more than one box away from a specific box generate the field at the center of that specific box. The final step is to sum this far field contribution with the
near_field()contribution that comes from sources at most one box away.