The Low-Frequency Multi-Level Fast Multipole Method on Graphics Processors

Abstract

The Fast Multipole Method (FMM) allows for rapid evaluation of the fundamental solution of the Helmholtz equation, known as Green's function. Evaluation times are reduced from O(N^2), using the direct approach, down to O(N log N), with an accuracy specified by the user. The Helmholtz equation, and variations thereof, including the Laplace and wave equations, are used to describe physical phenomena in electromagnetics, acoustics, heat dissipation, and many other applications. This thesis studies the acceleration of the low-frequency FMM, where the product of the wave number and the translation distance of expansion coefficients is relatively low. A general-purpose graphics processing unit (GPGPU), with native support of double-precision arithmetic, was used in the implementation of the LF FMM, with a resulting speedup of 4-22X over a conventional central processing unit (CPU), running in a single-threaded manner, for various simulations involving hundreds of thousands to millions of sources.