Fast algorithms and preconditioning techniques for fitting radial basis functions. (2001)
Type of ContentTheses / Dissertations
Degree NameDoctor of Philosophy
PublisherUniversity of Canterbury. Mathematics and Statistics
Radial basis functions are excellent interpolators for scattered data in Rd. Previously the use of RBFs had been restricted to small or medium sized data sets due to the high computational cost of solving the interpolation equations when using global basic functions. The construction of fast multipole methods, which reduce the cost of finding a matrix-vector product to O(N log N) or O(N) operations, has created the opportunity to dramatically reduce the cost of solving RBF equations. This thesis presents preconditioners which in conjunction with matrix iterative methods reduce the cost of solving these systems from O(N3) operations to O(N log N) operations. The usual formulation of the radial basis function interpolation equations are generally badly conditioned for large N. Thus the accuracy of the solution is less certain. However, it is not the problem that is badly conditioned but instead the basis built from the Φ functions. Preconditioners in this thesis improve the conditioning of the system by converting to a better basis.
RightsCopyright Cameron Thomas Mouat
Showing items related by title, author, creator and subject.
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𝜖⃒) ...
Radial Basis Functions Applied to Integral Interpolation, Piecewise Surface Reconstruction and Animation Control Langton, Michael Keith (University of Canterbury. Mathematics and Statistics, 2009)This thesis describes theory and algorithms for use with Radial Basis Functions (RBFs), emphasising techniques motivated by three particular application areas. In Part I, we apply RBFs to the problem of interpolating ...
Cherrie, J. B. (University of Canterbury. Mathematics and Statistics, 2000)Radial Basis Functions (RBFs) have proven to be successful interpolants to scattered data. However, the perceived high computational costs for fitting and evaluating the RBFs associated with large data sets have hindered ...