Study in Chemnitz. To know what is good.






  • Anmelden
Fast summation

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,\ldots,M)$ based on the recently developed fast Fourier transform at nonequispaced knots. Here $K$ are special kernels, e.g.,
\begin{displaymath} \frac{1}{x^2},\, \frac{1}{\vert x\vert}, \, \log \vert x\vert, \, x^2 \log \vert x\vert,\, \frac{1}{x}, \end{displaymath}

and in its multivariate generalization for RBFs ${\cal 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 ${\cal O} (N \log N +M)$ arithmetic operations.

The algorithms are implemented by Markus Fenn in ./applications/fastsum. Related paper are

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

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

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

oFenn, 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

oPö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