Efficient evaluation of a Fourier-like sum

Greetings esteemed savants:

Suppose we have some set of known real numbers x_j for
1 <= j <= N, and we wish to evaluate the sum

S(k) = sum_{j=1}^N e^{i k x_j}

for some set of values of k. If the x_j are equispaced,
then it is well-known that this sum can be efficiently
evaluated using fast Fourier transform techniques such
that the total time needed to evaluate S(k) for all of
the desired k values scales as N_k log N, where N_k is
the number of k values to be considered.

I have a problem (which stems from the computer
simulation of scattering patterns due to x-ray scattering
from a set of atoms, if anyone is interested) in which I
have no choice in the values of the x_j. They are fixed
and, in general, not evenly spaced. I do have some
freedom in choosing k values. (There are particular k
values at which I am interested in evaluating S(k), but I
can simply evaluate S(k) on a grid and interpolate to get
the k values I want.)

Obviously by brute force I can evaluate the above sum
using O(N N_k) operations, but this is too slow for large
N.

Any hints? Does anyone know of a efficient algorithm for
evaluating this sum? Feel free to massage the set of k
values to make things "nice", if necessary.

Extra points for hints as to a scheme that can be
generalized to the case where k and x_j become 3D
vectors, and the product k x_j in the above sum is
replaced by a dot product.

Thanks very much for any and all help, hints and advice!
.

Relevant Pages

  • Re: Help check my proof please?
    ... and increasing function. ... required RHS. ... you totally abandoned my hints. ... Sum them up symbolically, not numerically. ...
    (sci.math)
  • Re: Liberty Basic?
    ... and display summation of them on screen. ... Any hints for this? ... To reply by email change 'news' to my forename. ...
    (comp.lang.basic.misc)
  • Re: (Discrete Math - Induction) Formula Differentiation
    ... ANY hints on how the derivative of the sum of terms of a G.P will get ... problem is from the Mathematical Induction chapter of my Discrete ...
    (sci.math)
  • Re: Help check my proof please?
    ... I understand that this is the sequence until infinity, ... But you have switched back to the first group of hints, where the sum ... the sum is built from the bottom up. ...
    (sci.math)
  • Re: goldbachs conjecture
    ... Expanding the double sum for K: ... Evaluating M, we obtain K ... Ndenote the Narayana number C_C/n, ...
    (sci.math)