Fast evaluation of radial basis functions:: Methods for generalized multiquadrics in Rn

A generalized multiquadric radial basis function is a function of the form s(x) = Sigma(i=1)(N) d(i)phi(|x-t(i)|), where phi(r) = (r(2)+tau(2))(k/2), x is an element of R-n, and k is an element of Z is odd. The direct evaluation of an N center generalized multiquadric radial basis function at m points requires O (mN) flops, which is prohibitive when m and N are large. Similar considerations apparently rule out fitting an interpolating N center generalized multiquadric to N data points by either direct or iterative solution of the associated system of linear equations in realistic problems. In this paper we will develop far field expansions, recurrence relations for efficient formation of the expansions, error estimates, and translation formulas for generalized multiquadric radial basis functions in n-variables. These pieces are combined in a hierarchical fast evaluator requiring only O((m+N) log N|log epsilon|(n+1)) flops for evaluation of an N center generalized multiquadric at m points. This flop count is significantly less than that of the direct method. Moreover, used to compute matrix-vector products, the fast evaluator provides a basis for fast iterative fitting strategies.