An FMM Based on Dual Tree Traversal for Many-core Architectures. The present work attempts to integrate the independent efforts in the fast N-body community to create the fastest N-body library for many-core and heterogenous architectures. Focus is placed on low accuracy optimizations, in response to the recent interest to use FMM as a preconditioner for sparse linear solvers. A direct comparison with other state-of-the-art fast N-body codes demonstrates that orders of magnitude increase in performance can be achieved by careful selection of the optimal algorithm and low-level optimization of the code. The current N-body solver uses a fast multipole method with an efficient strategy for finding the list of cell-cell interactions by a dual tree traversal. A task-based threading model is used to maximize thread-level parallelism and intra-node load-balancing. In order to extract the full potential of the SIMD units on the latest CPUs, the inner kernels are optimized using AVX instructions. Our code -- exaFMM -- is an order of magnitude faster than the current state-of-the-art FMM codes, which are themselves an order of magnitude faster than the average FMM code.

References in zbMATH (referenced in 11 articles , 1 standard article )

Showing results 1 to 11 of 11.
Sorted by year (citations)

  1. Shi, Jia; Li, Ruipeng; Xi, Yuanzhe; Saad, Yousef; de Hoop, Maarten V.: A non-perturbative approach to computing seismic normal modes in rotating planets (2022)
  2. Wang, Tingyu; Layton, Simon K.; Barba, Lorena A.: Inexact GMRES iterations and relaxation strategies with fast-multipole boundary element method (2022)
  3. Bull, Jonathan; Engblom, Stefan: Distributed and adaptive fast multipole method in three dimensions (2021)
  4. Timo Betcke; Matthew W. Scroggs: Bempp-cl: A fast Python based just-in-time compiling boundary element library (2021) not zbMATH
  5. Tingyu Wang, Rio Yokota, Lorena A. Barba: ExaFMM: a high-performance fast multipole method library with C++ and Python interfaces (2021) not zbMATH
  6. Berenger Bramas: TBFMM: A C++ generic and parallel fast multipole method library (2020) not zbMATH
  7. Salloum, Samer; Lakkis, Issam: Proper evaluation of spherical harmonics-based expressions for the velocity and vortex stretching vectors in three-dimensional grid-free vortex methods (2020)
  8. Abduljabbar, Mustafa; Al Farhan, Mohammed; Al-Harthi, Noha; Chen, Rui; Yokota, Rio; Bagci, Hakan; Keyes, David: Extreme scale FMM-accelerated boundary integral equation solver for wave scattering (2019)
  9. Huang, He; Luo, Li-Shi; Li, Rui; Chen, Jie; Zhang, He: Improve the efficiency of the Cartesian tensor based fast multipole method for Coulomb interaction using the traces (2018)
  10. Ibeid, Huda; Yokota, Rio; Pestana, Jennifer; Keyes, David: Fast multipole preconditioners for sparse matrices arising from elliptic equations (2018)
  11. Yan, Wen; Shelley, Michael: Flexibly imposing periodicity in kernel independent FMM: a multipole-to-local operator approach (2018)