Abstract
The Fast Multipole Method (FMM) is a cornerstone of modern scientific computing, traditionally relying on square-grid hierarchical divisions of space. This paper explores the mathematical and algorithmic feasibility of using alternative tilings—specifically hexagonal (septree) and triangular (triangle-quadtree) structures—in 2D space. We demonstrate that these geometries maintain the essential separation properties required for FMM and provide a rigorous analysis of their performance. While the classic quadtree remains the efficiency leader for uniform data, these new structures offer unique trade-offs in error bounds and potential for non-uniform domains.
Introduction
The Fast Multipole Method (FMM) is essential for accelerating the calculation of long-range forces, such as gravity or electrostatics, in $N$-body problems. By approximating interactions between distant groups of particles, FMM reduces the computational complexity from $O(N^2)$ to $O(N)$. Traditionally, this is achieved through a square hierarchical division of space known as a quadtree.
While square tilings are the default, they are not the only way to tile a plane. Hexagons, for instance, possess higher symmetry and are more "circular" than squares, making them attractive for radial expansions. However, moving beyond squares introduces significant complexity: indexing hierarchical structures, calculating neighbor relationships, and ensuring that the "well-separated" geometric requirements of FMM are met. This research provides the framework to address these challenges.
Methodology and Spatial Structures
The authors implemented and analyzed two novel spatial data structures for FMM, comparing them against the standard square quadtree. The geometric properties of these tilings are illustrated in the figure below.
1. The Septree (Hexagonal)
Unlike squares, a hexagon cannot be perfectly subdivided into smaller hexagons. To overcome this, the authors utilize an "upward-composable" approach where seven hexagons are grouped to form a larger hexagonal aggregate. This structure uses Generalized Balanced Ternary (GBT) arithmetic—a base-7 indexing system where index addition corresponds directly to vector addition in the hexagonal lattice. This allows neighbor finding to be performed via simple index arithmetic rather than complex geometric searches.
2. The Triangle-Quadtree
This structure is "strictly decomposable," where one large triangle is divided into four smaller ones. A unique challenge here is that the orientation of the triangles flips (upright vs. inverted) at different levels of the hierarchy. The authors developed a specialized "ancestor-sibling-reflect" method to efficiently navigate these neighbor relationships.
For both structures, the authors derived the Separation Ratios ($r/R$) and Well-Separated Pair Decomposition (WSPD) properties. These ratios are critical as they dictate the error bounds of the multipole expansions used in the algorithm.
Key Insights and Results
Symmetry vs. Computational Complexity
Hexagons are more symmetric than squares, which theoretically suggests they might handle radial expansions more efficiently. However, this symmetry comes at a cost: the septree requires 42 Multipole-to-Local (M2L) translations per cell, compared to only 27 for a standard quadtree. This increased computational density is a primary factor in the performance differences observed.
Performance Benchmarks
Empirical tests using synthetic uniform distributions validated the theoretical claims:
- Linear Complexity: Both the septree and triangle-quadtree achieve the gold-standard $O(N)$ asymptotic runtime, matching the quadtree's scaling behavior.
- Efficiency Hierarchy: For uniform distributions, the Quadtree remains the fastest implementation. The Septree is slightly slower due to the higher number of M2L translations, and the Triangle-Quadtree is the least efficient.
- Error Bounds: The septree provides a tighter error bound for M2L translations compared to the quadtree. However, for general multipole expansions, the quadtree maintains a lower error because of its superior local separation ratio.
- Crossover Point: All FMM implementations began to outperform direct $O(N^2)$ evaluation at approximately $10^{3.5}$ to $10^{3.75}$ points.
Conclusion and Future Work
This study proves that alternative tilings are mathematically sound and algorithmically viable for FMM. While the quadtree is the most efficient for uniform data, the septree's unique error properties and symmetry suggest it may excel in non-uniform domains where data naturally aligns with hexagonal lattices.
Future research will focus on extending these concepts to 3D using permutohedrons (the 3D counterparts to hexagons) and investigating performance in highly non-uniform point distributions where the underlying physics may not align well with a square grid.
Summary updated