A multigrid-type method for thin plate spline interpolation on a circle

We consider the problem of thin plate spline interpolation to n equally spaced points on a circle, where the number of data points is sufficiently large for work of O(n 3 ) to be unacceptable. We develop an iterative multigrid-type method, each iteration comprising ngrid stages, and n being an integer multiple of 2 ngrid-1 . We let the first grid, V 1 , be the full set of data points, V say, and each subsequent (coarser) grid, V k , k = 2, 3,..., ngrid, contain exactly half of the data points of the preceding (finer) grid, these data points being equally spaced. At each stage of the iteration, we correct our current approximation to the thin plate spline interpolant by an estimate of the interpolant to the current residuals on V k , where the correction is constructed from Lagrange functions of interpolation on small local subsets of p data points in V k . When the coarsest grid is reached, however, then the interpolation problem is solved exactly on its q = n/2 ngrid-1i points. The iterative process continues until the maximum residual does not exceed a specified tolerance. Each iteration has the effect of premultiplying the vector of residuals by an n x n matrix R, and thus convergence will depend upon the spectral radius, p(R), of this matrix. We investigate the dependence of the spectral radius on the values of n, p, and q. In all the cases we have considered, we find p(R) << 1, and thus rapid convergence is assured.