Recursive Octree Algorithms with Parallel Applications

Tobin Isaac, University of Texas

Octrees--cubic domains that can be recursively divided into octants--are commonly used to represent meshes that require adaptive refinement; when combined with a space-filling curve, octrees form a powerful tool for partitioning such meshes across multiple processors.

In several popular software packages for managing parallel octrees, only the leaves of the octrees are stored, which is known as "flat" storage. Because the intermediate branches are not stored, the implementation in these packages of important algorithms often ignore the tree structure.
We present two such algorithms--sending boundary octants to neighboring processors, and extracting a nodal basis--where using the tree structure gives us improved performance. In terms of serial performance, we get asymptotic improvement in some cases; in terms of parallel performance, we reduce the communication between processors to a minimum. Because communication becomes the limiting factor as we increase the problem size, this communication reduction is critical. Furthermore, our algorithm for extracting a nodal basis, unlike previous algorithms, extends naturally to the extraction of higher-order nodal bases.

Abstract Author(s): Tobin Isaac, Carsten Burstedde, Lucas Wilcox