M2L Translation Operators for Kernel-Independent Fast Multipole Methods on Modern Architectures
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.
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}
}
EUVIMED