Fast evaluation of radial basis functions : methods for generalised multiquadrics in ℝⁿ (2000)
Type of ContentDiscussion / Working Papers
PublisherUniversity of Canterbury
- Engineering: Reports 
A generalised multiquadric radial basis function is a function of the form s(x) = ∑ᴺ𝑖₌₁ 𝑑𝑖 𝜙 (𝗅x-t𝑖𝗅), where 𝜙(r) = (r² + 𝝉²)ᵏ/², x ∈ ℝⁿ, and k ∈ Z is odd. The direct evaluation of an N centre generalised multiquadric radial basis function at m points requires 𝒪(mN) flops, which is prohibitive when m and N are large. Similar considerations apparently rule out fitting an interpolating N centre generalised 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 generalised multiquadric radial basis functions in n-variables. These pieces are combined in a hierarchical fast evaluator requiring only 𝒪((m + N) log N llog 𝜖lⁿ⁺¹) 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, used to compute matrix-vector products, the fast evaluator provides a basis for fast iterative fitting strategies.
ANZSRC Fields of Research49 - Mathematical sciences::4904 - Pure mathematics::490408 - Operator algebras and functional analysis
RightsAll Rights Reserved
Showing items related by title, author, creator and subject.
Cherrie, J. B.; Beatson, R. K.; Ragozin, D. L. (University of Canterbury. Department of Mathematics & Statistics, 2000)As is now well known for some basic functions ϕ, hierarchical and fast multipole like methods can greatly reduce the storage and operation counts for fitting and evaluating radial basis functions. In particular for spline ...
The performance of available methods for computing the polynomial coefficients of the quadratic function approximation is evaluated. By comparing the numerical results to those obtained by symbolic methods, for a variety of functions, the direct solution of the matrix equation and a variety of recursive algorithms are all shown to be numerically unstable. AMS classification Balakrishnan, Easwaran; McInnes, A.W. (University of Canterbury. Mathematics, 1991)The performance of available methods for computing the polynomial coefficients of the quadratic function approximation is evaluated. By comparing the numerical results to those obtained by symbolic methods, for a variety ...
Beatson, Richard Keith; Newsam, G.N. (University of Canterbury. Dept. of Mathematics, 1995)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𝜖⃒) ...