FAST EVALUATION OF RADIAL BASIS FUNCTIONS .1.

This paper describes some new techniques for the rapid evaluation and fitting of radial basis functions. The techniques are based on the hierarchical and multipole expansions recently introduced by several authors for the calculation of many-body potentials. Consider in particular the N term thin-plate spline, s(x) = SIGMA(j=1)N d(j)phi(x - x(j)), where phi(u) = absolute-value-of u2 log absolute-value-of u, in 2-dimensions. The direct evaluation of s at a single extra point requires an extra O(N) operations. This paper shows that, with judicious use of series expansions, the incremental cost of evaluating s(x) to within precision epsilon, can be cut to 0(1 + \log epsilon\) operations. In particular, if A is the interpolation matrix, a(i,j) = phi(x(i) - x(j)), the technique allows computation of the matrix-vector product Ad in O(N), rather than the previously required O(N2) operations, and using only O(N) storage. Fast, storage-efficient, computation of this matrix-vector product makes pre-conditioned conjugate-gradient methods very attractive as solvers of the interpolation equations, Ad = y, when N is large.