Fast fitting of radial basis functions: Methods based onpreconditioned GMRES iteration
by
Cameron Mouat
University of Canterbury
Coauthors: Rick Beatson, Jon Cherrie

Solving large radial basis function (RBF) interpolation problems with non-customised methods is computationally expensive and the matrices that occur are typically badly conditioned. The usual direct methods require O(N²) storage, and O(N³) operations, so that solving large problems with 10, 000 or more centres by such non-customised methods is prohibitively expensive.

In this talk we present preconditioning strategies which, in combination with a fast multiply and GMRES iteration, make the solution of large RBF interpolation problems orders of magnitude less expensive in storage and operations. Typically, the preconditioning results in dramatic clustering of eigenvalues and improves the condition numbers of the interpolation problem by several orders of magnitude. As a result of the eigenvalue clustering the number of GMRES iterations required to solve the preconditioned problem is of the order of 10 to 20. Taken together, the combination of a suitable approximate cardinal function preconditioner, the GMRES iterative method, and existing fast matrix-vector codes for RBFs reduce the computational cost of solving an RBF interpolation problem to O(N) storage, and O(N logN) operations.

Date received: December 17, 1998

Copyright © 1998 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cabp-12.