Kailasa, Srinath; (2025) Modern Resesarch Software For Fast Multipole Methods. Doctoral thesis (Ph.D), UCL (University College London).

Preview

Text Kailasa_10208866_thesis_revised.pdf Download (11MB) | Preview

Abstract

This thesis develops high-performance simulation software for the Kernel Independent Fast Multipole Method (kiFMM) in three dimensions — a variant of the widely applied Fast Multipole Method (FMM) algorithm. The FMM finds broad application across physics, engineering, computational science, and data analysis for accelerating dense matrix–vector products where the matrix exhibits low-rank structure in its off-diagonal blocks. It is particularly effective in solving boundary integral formulations of elliptic partial differential equations (PDEs). The FMM and its variants reduce computational complexity from O(Nᵅ logᵝ N), with α ∈ [1, 2) and β ∈ {0, 1}. The optimal scaling of α = 1 and β = 0 is achieved for non-oscillatory problems such as the Poisson equation, which serves as a prototypical application. FMMs are organised hierarchically using a tree-based spatial decomposition and apply a sequence of field translations to propagate long-range interactions — such as those between distant static charges or masses governed by the Poisson equation. The kiFMM employs a kernel-independent approach to field translations and representation, making it well suited to modular implementation while supporting a wide range of elliptic PDEs, including the Poisson and time-independent Helmholtz equations at low frequencies (where kD ∼ 1, with k denoting the wave number and D the diameter of the problem domain). Despite this versatility, scalable and portable implementations of the kiFMM remain limited — particularly for distributed memory architectures and in high-frequency regimes of the Helmholtz problem. This thesis investigates efficient implementations of field translations for the kiFMM in both shared and distributed memory settings. Key contributions include a simplified, high-performance formulation of the Multipole-to-Local (M2L) translation operator using portable level-3 BLAS functions, and a scalable yet lightweight ghost data exchange mechanism for distributed parallelism. Benchmarking demonstrates competitive runtimes across hardware targets. For the Poisson case, weak scaling is achieved on up to 1.024 × 10⁹ source and target points on 16,384 cores of ARCHER2. For the Helmholtz case, the kiFMM algorithmic machinery is shown to extend to high-frequency problems (kD ∈ [50, 100]) with minimal code changes. Though currently limited to single precision and single-node tests, Helmholtz potentials with kD = 100 and 1 × 10⁶ source and target points are computed in 4–8 seconds on standard consumer CPUs. Finally, the software is treated as a research object, with design choices guided by performance, portability, and sustainability in academic high-performance computing.

Download activity - last month

Export as CSVJSONXML

Download activity - last 12 months

Export as XMLJSONCSV

Downloads by country - last 12 months

Export as CSVJSONXML

Archive Staff Only

View Item