Fast algorithms and preconditioning techniques for fitting radial basis functions.
Degree GrantorUniversity of Canterbury
Degree NameDoctor of Philosophy
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.