Fast summation based on NFFT

This library of C functions computes approximations of sums of the form $f (y_{j}) := \sum_{k = 1}^{N} α_{k} K (y_{j} - x_{k})$ $(j = 1, \dots, M)$ based on the recently developed fast Fourier transform at nonequispaced knots (NFFT). Here $K$ are special kernels, e.g., $\frac{1}{x^{2}}, \frac{1}{| x |}, \log | x |, x^{2} \log | x |, \frac{1}{x},$ and in its multivariate generalization for RBFs $K$ . Our algorithm can be modified for other kernels frequently used in the approximation by RBFs, e.g., the Gaussian or the (inverse) multiquadric $(x^{2} + c^{2})^{\pm 1 / 2}$ .

New kernels are easily incorporated by defining an appropriate C-function (see kernels.c for some examples).

fastsum_test.c is an example for the usage of the library. The MATLAB script file fastsum_test.m calls the MATLAB function fastsum.m, which is a simple example for the usage in MATLAB. In summary it requires $O (N \log N + M)$ arithmetic operations.

The algorithms are implemented by Markus Fenn in ./applications/fastsum. The OpenMP parallelization was implemented by Toni Volkmer. The Matlab interface was implemented by Michael Quellmalz in ./matlab/fastsum. The Julia interface was implemented by Michael Schmischke in ./julia/fastsum. Related paper are

Potts, D. and Steidl, G.
Fast summation at nonequispaced knots by NFFTs.
SIAM J. on Sci. Comput. 24, 2013-2037. (full paper ps, pdf), 2004

Potts, D., Steidl, G. and Nieslony, A.
Fast convolution with radial kernels at nonequispaced knots.
Numer. Math. 98, 329-351. (full paper ps, pdf), 2004

Fenn, M. and Steidl, G.
Fast NFFT based summation of radial functions.
Sampling Theory in Signal and Image Processing 3/1, 1-28 (2004)

Fenn, M. and Potts, D.
Fast summation based on fast trigonometric transforms at nonequispaced nodes.
Numer. Linear Algebra Appl. 12, 161-169. (full paper ps, pdf), 2005

Pï¿½plau, G., Potts, D. and van Rienen, U.
Calculation of 3D Space-Charge Fields of Bunches of Charged Particles by Fast Summation.
in: Proceedings of SCEE 2004 (5th International Workshop on Scientific Computing in Electrical Engineering), Springer-Verlag (full paper ps, pdf ), 2005