Fast evaluation of radial basis functions: Methods for generalised multiquadrics in Rⁿ
by
J B Cherrie
University of Canterbury
Coauthors: R K Beatson, G N Newsam

A generalized multiquadric radial basis function is a function of the form

s(x) = å di f( x -xi),

where

f(x) = ( x2+c2 )k/2,

x ∈ Rⁿ, and k ∈ Z is odd. The direct evaluation of an N centre generalized multiquadric radial basis function at m points requires O(m N) flops which is prohibitive when m and N are large. Similar considerations apparently rule out fitting an interpolating N centre generalized multiquadric to N data points by either direct or iterative solution of the associated system of linear equations in realistic problems.

In this talk we will develop far field expansions, error estimates, recurrence relations for efficient formation of the expansions, and translation formulas, for generalised multiquadric radial basis functions in n-variables. These pieces are combined in a hierarchical fast evaluator requiring only O( (m+N) logN) flops for evaluation of an N centre generalised multiquadric at m points. This flop count compares very favourably with the cost of the direct method. Moreover, as outlined above, the approach provides a basis for fast fitting routines based on iterative solution of the associated linear systems.

Date received: December 16, 1998