A kernel-independent adaptive fast multipole algorithm in two and three dimensions

Lexing Ying
New York University

We present a new fast multipole method for particle simulations. The main feature of our algorithm is that it does not require the
implementation of multipole expansions of the underlying kernel, and it is based only on kernel evaluations. Instead of using analytic
expansions to represent the potential generated by sources inside a box of the hierarchical FMM tree, we use a continuous distribution of an equivalent density on a surface enclosing the box. To find this equivalent density we match its potential to the potential of the original sources at a surface, in the far field, by solving
local Dirichlet-type boundary value problems. The far field evaluations are sparsified with singular value decomposition in 2D or fast Fourier transforms in 3D. We have tested the new method on the single and double layer operators for the Laplacian, the modified Laplacian, the Stokes, the modified Stokes, the Navier, and
the modified Navier operators in two and three dimensions. Our numerical results indicate that our method compares very well with the best known implementations of the analytic FMM method for both the Laplacian and modified Laplacian kernels. Its advantage is the (relative) simplicity of the implementation and its immediate
extension to more general kernels.

Presentation (PDF File)

Back to MGA Workshop II: Multiscale Geometry in Scientific Computing