Spline Interpolation on Unbounded Domains

Spline interpolation is a splendid tool for multiscale approximation on unbounded domains. In particular, it is well suited for use by the multilevel summation method (MSM) for calculating a sum of pairwise interactions for a large set of particles in linear time. Outlined here is an algorithm for spline interpolation on unbounded domains that is efficient and elegant though not so simple. Further gains in efficiency are possible via quasi-interpolation, which compromises collocation but with minimal loss of accuracy. The MSM, which may also be of value for continuum models, embodies most of the best features of both hierarchical clustering methods (tree methods, fast multipole methods, hierarchical matrix methods) and FFT-based 2-level methods (particleparticle particlemesh methods, particlemesh Ewald methods).