Fast evaluation of radial basis functions : moment based methods
Degree GrantorUniversity of Canterbury
Degree NameResearch report
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.
SubjectsField of Research::01 - Mathematical Sciences
- Engineering: Reports