18
$\begingroup$

In most (all?) implementations of the Fast Multipole Method (FMM), octrees are used to decompose the relevant domain. Theoretically, octrees provide a simple volumetric bound, which is useful for proving the O(n) runtime of a FMM. Beyond this theoretical rationale, are there benefits to using an Octree over other tree or trie data structures?

Determining the interaction list might be easier with an octree because a cell would know its immediate neighbors. However, the interaction list is unnecessary using a more dynamic tree traversal like Dual Tree Traversal.

An alternative would be a kd-tree. One possible theoretical downside is that construction requires expensive median finding operations. However, there are versions of kd-trees that do not require median finding during construction -- albeit with less efficient space partitioning. Implemention-wise, a kd-tree is very simple.

An even more radical alternative might be an R-tree.

So, my question is: What is about Octrees that make them the best choice for a FMM?

Improve this question
$\endgroup$
5
  • 4
    $\begingroup$ I think it makes determining the interaction lists (which observers are in the far field of which sources) particularly easy. $\endgroup$
    – rchilton1980
    Jul 3, 2014 at 18:11
  • $\begingroup$ Determining interaction lists should be quite easy with any form of hierarchical space decomposition. $\endgroup$
    – Ben Thompson
    Jul 7, 2014 at 12:36
  • 1
    $\begingroup$ I agree with you in that, oct-trees are theoretically simple to analyze. Other fast summation algorithms, such as $\mathcal{H}$-matrices (which are algebraic generalizations of FMM) use different trees, such as geometric bisection or cluster based splitting. $\endgroup$
    – user2457602
    Jul 8, 2014 at 0:28
  • 1
    $\begingroup$ I'm no expert on this, but perhaps the fact that octrees have more 'symmetry' plays a role? The partitions in an octree are arranged regularly and have the same square shape, which could help in making the multipole expansions compared to e.g. a k-d tree. $\endgroup$
    – Jannis Teunissen
    Apr 17, 2016 at 22:39
  • $\begingroup$ Octrees are a natural outcome of domain decomposition in three dimensions. $\endgroup$
    – gpavanb
    Apr 29, 2016 at 5:53

1 Answer 1

Reset to default
2
$\begingroup$

The comments above give some very good reasons for using octrees (i.e., recursively halving the computational cube in each dimension as opposed to a more general orthogonal bisection). Symmetry and simplicity of calculating interaction lists is a big plus.

I would argue that perhaps the most important feature that octrees bring to the table is that the addition theorem underwriting the FMM is systematically satisfied for far-zone interactions independent of the geometry with the extremely simple well-separatedness criterion of one or more "buffer" boxes. In other words, the FMM sum representation of the potential field is guaranteed to converge with increasing order under non-pathological circumstances.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.