Rapid Evaluation of Radial Functions by
Rapid Evaluation of Radial Functions by
Fast Fourier Transforms at Nonequispaced Knots
Gabriele STEIDL1
Faculty of Mathematics and Computer Science
University of Mannheim
Germany
Email: steidl@math.uni-mannheim.de
The fast computation of special structured discrete sums
|
f(yj) : = |
N
å
k = 1
|
ak K(||yj-xk||) (j = 1,¼,M), |
|
or from the linear algebra point of view the fast computation of
products of vectors with special structured dense matrices is a
frequently appearing task in the study of particle models, in the
numerical solution of integral equations (or of partial
differential equations by recasting them as integral equations)
and in the approximation of functions by radial basis functions.
Various algorithms, e.g., the fast multipole method, the panel
clustering method, H-matrix and mosaic matrix methods, were
designed to speed up the summation process.
Here we propose a new summation algorithm based on the
recently developed fast Fourier transform for nonequispaced knots
(NFFT). Our algorithm, in particular our regularization
procedure, is simply structured and can be easily adapted to
different kernels K.
We prove error estimates to obtain clues about the
choice of the involved parameters and present numerical examples
for the prominent bivariate radial kernels
|
|
1
x
|
, |
1
x2
|
, x2 logx, logx, e-sx2, (x2 + c2)±1/2. |
|
Footnotes:
1 Joint work with Daniel POTTS.
File translated from TEX by TTH, version 1.94.
On 23 Apr 2002, 15:57.