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

Received on 23 February 1995. Revised on 7 May 1996. This paper concerns the fast evaluation of radial basis functions.It describes the mathematics of a methos for splines of theform where p is a low-degree polynomial. Such functions are veryuseful for the interpolation of scattered data, but can be computationallyexpensive to use when N is large. The method described is ageneralization of the fast multipole method of Greengard andRokhlin for the potential case (m=0), and reduces the incrementalcost of a single extra evaluation from O(N) operations to O(1)operations. The paper develops the required series expansionsand uniqueness results. It pays particular attention to therate of convergence of the series approximations involved, obtainingimproved estimates which explain why numerical experiments revealfaster convergence than predicted by previous work for the potential(m=0) and thin-plate spline (m=1) cases.     

Univariate Interpolation on a Regular Finite Grid by a Multiquadric Plus a Linear Polynomial

Univariate multiquadric interpolation to a twice continuouslydifferentiable function on a regular infinite grid enjoys secondorder convergence and some excellent localization properties,but numerical calculations suggest that, if the grid is finite,then usually the convergence rate deteriorates to first ordernear the grid boundaries, ibis conjecture is proved. It is alsoshown that one can recover superlinear convergence by addinga linear polynomial term to the multiquadric approximation.Making such additions is a standard technique, but we find thatthe usual way of choosing the polynomial fails to provide superlinearconvergence m general. Therefore some new procedures are giventhat pick a suitable polynomial automatically. Thus it is notunusual to reduce the maximum error of the interpolation bya factor of 10³. Further, it is straightforward to include oneof the new procedures in multiquadric interpolation to functionsof several variables when the data points are in general position.