Fast evaluation of polyharmonic splines in three dimensions

This paper concerns the fast evaluation of radial basis functions. It describes the mathematics of hierarchical and fast multipole methods for fast evaluation of splines of the form s (x) = p (x) + (N)Sigma(j=1) dj vertical bar x - x(j)vertical bar(2v-1), x is an element of R-3, where v is a positive integer and p is a low-degree polynomial. Splines s of this form are polyharmonic splines in R-3 and have been found to be very useful for providing solutions to scattered data interpolation problems in R-3. As it is now well known, hierarchical methods reduce the incremental cost of a single extra evaluation from O(N) to O (log N) operations and reduce the cost of a matrix-vector product (evaluation of s at all the centres) from O(N-2) to O(N log N) operations. We give appropriate far- and near-field expansions, together with error estimates, uniqueness theorems and translation formulae. A hierarchical code based on these formulae is detailed and some numerical results are given.