The black-box fast multipole method

A new O(N)$O(N)$ fast multipole formulation is proposed for non-oscillatory kernels. This algorithm is applicable to kernels K(x,y)$K(x\text{,}y)$ which are only known numerically, that is their numerical value can be obtained for any (x,y)$(x\text{,}y)$. This is quite different from many fast multipole methods which depend on analytical expansions of the far-field behavior of K  , for |x-y|$|x-y|$ large. Other “black-box” or “kernel-independent” fast multipole methods have been devised. Our approach has the advantage of requiring a small pre-computation time even for very large systems, and uses the minimal number of coefficients to represent the far-field, for a given L²$L^2$ tolerance error in the approximation. This technique can be very useful for problems where the kernel is known analytically but is quite complicated, or for kernels which are defined purely numerically.