Alternative Tilings for the Fast Multipole Method on the Plane

Yuancheng Luo, Ramani DuraiswamiarXiv 2012 · arXiv

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.

Comparison of Square, Hexagonal, and Triangular tilings with their respective separation parameters $r$ and $R$.

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

Abstract

The fast multipole method (FMM) performs fast approximate kernel summation to a specified tolerance $\epsilon$ by using a hierarchical division of the domain, which groups source and receiver points into regions that satisfy local separation and the well-separated pair decomposition properties. While square tilings and quadtrees are commonly used in 2D, we investigate alternative tilings and associated spatial data structures: regular hexagons (septree) and triangles (triangle-quadtree). We show that both structures satisfy separation properties for the FMM and prove their theoretical error bounds and computational costs. Empirical runtime and error analysis of our implementations are provided.
BibTeX
@misc{luo2012alternative,
  author = {Yuancheng Luo and Ramani Duraiswami},
  title = {{Alternative Tilings for the Fast Multipole Method on the Plane}},
  year = {2012},
  eprint = {1204.3105},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1204.3105},
}
Figure