Fast evaluation of radial basis functions: Methods for two-dimensional polyharmonic splines

This paper concerns the fast evaluation of radial basis functions. It describes the mathematics of a method for splines of the form s(x) = p(x) + (j=l)Sigma(N) d(j)/x-x(j)/(2m) log/x-x(j)/, x epsilon R-2 where p is a low-degree polynomial. Such functions are very useful for the interpolation of scattered data, but can be computationally expensive to use when N is large. The method described is a generalization of the fast multipole method of Greengard and Rokhlin for the potential case (m = 0), and reduces the incremental cost of a single extra evaluation from O(N) operations to O(I) operations. The paper develops the required series expansions and uniqueness results. It pays particular attention to the rate of convergence of the series approximations involved, obtaining improved estimates which explain why numerical experiments reveal faster convergence than predicted by previous work for the potential (m = 0) and thin-plate spline (m = 1) cases.