Fast Evaluation of Multiquadric RBF Sums by a Cartesian Treecode

A treecode is presented for evaluating sums defined in terms of the multiquadric radial basis function (RBF), φ( x) = (| x|²+c²)1/2, where x ∈ R³ and c ≥ 0. Given a set of N nodes, evaluating an RBF sum directly requires CPU time that scales like O(N²). For a given level of accuracy, the treecode reduces the CPU time to O(Nlog N) using a far-field expansion of φ( x). We consider two options for the far-field expansion: (1) a Laurent series previously used in applications of the Fast Multipole Method to multiquadric RBFs, and (2) a certain Taylor series previously used in treecode particle simulations, but not yet in the context of multiquadric RBFs. It is known that the Laurent series converges when the RBF parameter c lies in an interval 0 ≤ c ≤ c̄, where c̄ is proportional to the minimum node spacing, but here we show that the Taylor series converges uniformly for c ≥ 0. We implement the treecode in Cartesian coordinates and use a recurrence relation to compute the Taylor coefficients. Numerical results exhibit the treecode error, CPU time, and memory usage in two test cases, random nodes in a cube and on the surface of a sphere. The treecode approach presented here is applicable to generalized multiquadrics in any dimension.