EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

M2L Translation Operators for Kernel-Independent Fast Multipole Methods on Modern Architectures

Srinath Kailasa, Timo Betcke, Sarah Elkazdadi

ACM Transactions on Mathematical Software · 30.09.2026 · 52 (3) · 1-32

DOI: 10.1145/3820372 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Mathematical Software, online erschienen am 18.08.2026. Verfasst von Srinath Kailasa und 2 weiteren Autor:innen. Die Arbeit nennt 35 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Engineering and Physical Sciences Research Council.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Hardware trends favor algorithm designs that maximize data reuse per FLOP. We develop and benchmark high-performance Multipole-to-Local (M2L) translation operators for the kernel-independent Fast Multipole Method (kiFMM), a widely adopted FMM variant that supports a broad class of kernels and has been favored by recent implementations for its simple specification. Naively implemented, M2L is bandwidth-limited and therefore a key bottleneck in the FMM. State-of-the-art FFT-based M2L implementations, though elegant and with a fast setup time, suffer from low operational intensity and require architecture-specific optimizations. We demonstrate that a Basic Linear Algebra Subprograms (BLAS)-based M2L, combined with randomized low-rank compression, achieves competitive performance with greater portability and a simpler implementation leveraging existing BLAS infrastructure, at the cost of higher setup times—especially for high-accuracy settings in double precision. Our Rust-based implementation enables seamless switching between strategies for fair benchmarking. Results on CPUs show that FFT-based M2L is favorable in low-accuracy settings or dynamic particle simulations, while BLAS-based M2L is favored for high-accuracy settings for static particle distributions, where its higher setup costs are amortized in many practical applications of the FMM.

Förderung

  • Engineering and Physical Sciences Research Council

Zitieren

APA

Kailasa, S., Betcke, T., & Elkazdadi, S. (2026). M2L Translation Operators for Kernel-Independent Fast Multipole Methods on Modern Architectures. ACM Transactions on Mathematical Software, 52(3), 1-32. https://doi.org/10.1145/3820372

Vancouver

Kailasa S, Betcke T, Elkazdadi S. M2L Translation Operators for Kernel-Independent Fast Multipole Methods on Modern Architectures. ACM Transactions on Mathematical Software. 2026;52(3):1-32. doi:10.1145/3820372

BibTeX
@article{Kailasa2026,
  author = {Kailasa, Srinath and Betcke, Timo and Elkazdadi, Sarah},
  title = {M2L Translation Operators for Kernel-Independent Fast Multipole Methods on Modern Architectures},
  journal = {ACM Transactions on Mathematical Software},
  year = {2026},
  volume = {52},
  number = {3},
  pages = {1--32},
  doi = {10.1145/3820372}
}
Kostenlos starten →