Fast summation based on NFFT
This library of C functions computes approximations of sums of the form \(f(y_j) := \sum\limits_{k=1}^N \alpha_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 \(\mathcal 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 \(\mathcal 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

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

Fast convolution with radial kernels at nonequispaced knots.
Numer. Math. 98, 329-351. (full paper ps, pdf), 2004

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

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

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