Tabulation of thin plate splines on a very fine two-dimensional grid.(English)Zbl 0813.65014

Braess, D. (ed.) et al., Numerical methods in approximation theory. Vol. 9: Proceedings of the conference held in Oberwolfach, Germany, November 24-30, 1991. Basel: BirkhĂ¤user. ISNM, Int. Ser. Numer. Math. 105, 221-244 (1992).
Summary: A thin plate spline approximation has the form $s(x) = \sum^ n_{j=1} \lambda_ j \| x - x_ j \|^ 2_ 2 \log \| x - x_ j \|_ 2 + p(x), \quad x \in \mathbb{R}^ 2,$ where $$\{\lambda_ j \in \mathbb{R} : j = 1,2, \dots, n\}$$ and $$\{x_ j \in \mathbb{R}^ 2 : j =1,2, \dots, n\}$$ are parameters and where $$p$$ is a linear polynomial. There exist several applications that require $$s$$ to be tabulated at all the lattice points of a very fine square grid. For example, $$10^ 8$$ grid points and $$n = 500$$ can occur, and then the direct evaluation of $$s$$ at every grid point would be impracticable.
Fortunately each thin plate spline term is smooth away from its centre $$x_ j$$, so it is possible to apply a scheme that subtabulates by finite differences provided that special attention is given to those terms whose centres are close to the current $$x$$. Thus the total work is bounded by a small constant multiple of the number of grid points plus a constant multiple of $$n \varepsilon^{-1/3} |\log h |$$, where $$\varepsilon$$ is a given tolerance on the calculated values of $$s(x)$$ and where $$h$$ is the mesh size of the fine grid. We will find that the exponent $$-1/3$$ is due to the order of the differences that are employed.
An algorithm for this calculation is described and discussed and some numerical results are presented. The errors of the subtabulation procedures are studied in an appendix.
For the entire collection see [Zbl 0807.00018].

MSC:

 65D07 Numerical computation using splines 41A15 Spline approximation 41A63 Multidimensional problems