Fast solution of the radial basis function interpolation equations: Domaindecomposition methods

In this paper we consider domain decomposition methods for solving the radi al basis function interpolation equations. There are three interwoven threa ds to the paper. The rst thread provides good ways of setting up and solvin g small- to medium-sized radial basis function interpolation problems. Thes e may occur as subproblems in a domain decomposition solution of a larger i nterpolation problem. The usual formulation of such a problem can su er fro m an unfortunate scale dependence not intrinsic in the problem itself. This scale dependence occurs, for instance, when fitting polyharmonic splines i n even dimensions. We present and analyze an alternative formulation, avail able for all strictly conditionally positive definite basic functions, whic h does not su er from this drawback, at least for the very important exampl e previously mentioned. This formulation changes the problem into one invol ving a strictly positive definite symmetric system, which can be easily and efficiently solved by Cholesky factorization. The second section considers a natural domain decomposition method for the interpolation equations and views it as an instance of von Neumann's alternating projection algorithm. Here the underlying Hilbert space is the reproducing kernel Hilbert space i nduced by the strictly conditionally positive definite basic function. We s how that the domain decomposition method presented converges linearly under very weak nondegeneracy conditions on the possibly overlapping subdomains. The last section presents some algorithmic details and numerical results o f a domain decomposition interpolatory code for polyharmonic splines in 2 a nd 3 dimensions. This code has solved problems with 5 million centers and c ant splines with 10,000 centers in approximately 7 seconds on very modest h ardware.