ExaFMM: a high-performance fast multipole method library with C++ and Python interfaces

Tingyu Wang, Rio Yokota, Lorena A. BarbaJ. Open Source Softw 2021 · DOI · DBLP

Abstract

The Fast Multipole Method (FMM) is a critical algorithm for reducing the complexity of N-body problems from $O(N^2)$ to $O(N)$. However, the implementation of FMM often involves a trade-off between extreme performance and code maintainability. This paper presents ExaFMM-t, a lean, header-only C++ library with Python interfaces that prioritizes clean design and accessibility without sacrificing significant computational speed. We demonstrate its performance on million-particle benchmarks and a large-scale biomolecular simulation of the Zika virus.

Introduction

Calculating interactions between $N$ points—the classic N-body problem—is a fundamental challenge in fields ranging from astrophysics to molecular biology. While a naive approach scales as $O(N^2)$, the Fast Multipole Method (FMM) reduces this complexity to $O(N)$ through hierarchical approximations of long-range interactions. Despite its efficiency, FMM is notoriously difficult to implement, often leading to a choice between slow, generic code or hyper-optimized, unmaintainable "black boxes."

ExaFMM-t addresses this "performance vs. maintainability" trap. By providing a "standard" go-to library that is both easy to use and computationally competitive, the authors aim to provide for N-body problems what FFTW did for the Fast Fourier Transform.

Methodology

ExaFMM-t is a modern implementation focusing on the kernel-independent variant of FMM (KIFMM). The library is designed to be a "white-box" tool that researchers can understand and extend, rather than a legacy system.

Technical Implementation

  • Header-only C++ Design: The core library consists of approximately 6,000 lines of code, making it significantly more compact than comparable packages. It relies on standard C++ STL containers and mature math libraries like BLAS, LAPACK, and FFTW3.
  • Parallelism and Vectorization: The library utilizes OpenMP for multi-threading and leverages SIMD vectorization (SSE, AVX, AVX-512) to optimize near-range particle-to-particle (P2P) operators.
  • Python Integration: Using pybind11, ExaFMM-t offers high-level Python APIs. To handle Python's dynamic nature and avoid naming collisions, the authors created separate Python modules for each kernel (e.g., Laplace, Helmholtz).
  • Kernel Support: It natively supports Laplace, low-frequency Helmholtz, and modified Helmholtz (Yukawa) kernels, with an architecture that allows users to add new non-oscillatory kernels easily.

Performance and Applications

The library follows a "ballpark" performance philosophy: prioritizing clean code and standard interfaces while remaining competitive with state-of-the-art specialized codes.

Benchmarking

In a synthetic benchmark involving 1 million randomly distributed particles for a Laplace problem on a 14-core Intel i9 workstation, ExaFMM-t achieved high-precision results rapidly:

  • 7 digits of accuracy in 0.95 seconds.
  • 10 digits of accuracy in 1.48 seconds.

Real-World Application: Zika Virus Simulation

To demonstrate its utility in complex, biologically relevant scenarios, ExaFMM-t was integrated with the Bempp-cl boundary element method package. This combination was used to simulate the biomolecular electrostatics of a Zika virus model, involving 1.6 million atoms and 10 million boundary elements (resulting in 30 million evaluation points). The entire simulation completed in just 1.5 hours on a single CPU node, demonstrating the library's capability to handle massive datasets on modest hardware.

Conclusion

ExaFMM-t provides a robust, maintainable, and high-performance solution for researchers working with N-body problems. By reducing the codebase to 6,000 lines and providing first-class Python support, the library lowers the barrier to entry for high-performance computing in scientific research. Future work will continue to expand kernel support and refine the integration with boundary element method frameworks for broader applications in computational physics and biology.

Summary updated

BibTeX
@article{wang2021exafmm,
  author = {Tingyu Wang and Rio Yokota and Lorena A. Barba},
  title = {{ExaFMM: a high-performance fast multipole method library with C++ and Python interfaces}},
  journal = {J. Open Source Softw.},
  year = {2021},
  doi = {10.21105/joss.03145},
}
Figure