In this paper we introduce a new algorithm for fast evaluation of univariate radial basis functions of the form s(x) = Σᶰn₌₁ dn(⃒x - xn⃒) to within accuracy . The algorithm has a setup cost of (N⃒log⃒log⃒log⃒) operations and an incremental cost per evaluation of s(x) of (⃒log⃒) operations. It is based on a hierarchical subdivision of the unit interval, the adaptive construction of a corresponding hierarchy of polynomial approximations, and the fast accumulation of moments. It can be applied in any case where the basic function smooth on (0, 1], and on any grid of centres ｛Xn｝. The algorithm does not require that be analytic at infinity, nor that the user specify new polynomial approximations or modify the data structures for each new , nor that the points Xn form any sort of regular array. Furthermore the algorithm can be extended to problems in higher dimensions.
展开▼
