I have implemented Dutt & Rokhlin's FFT algorithm [1] for non-equispaced data but for some reason I am getting very large errors ($E_2=0.04$ and $E_\infty=0.1$). I was wondering if there are any free available implementation of this method so I can compare my implementation.

[1] Dutt, Alok, and Vladimir Rokhlin. "Fast Fourier transforms for nonequispaced data." SIAM Journal on Scientific computing 14.6 (1993): 1368-1393.

  • $\begingroup$ Did you use my answer? Could you please mark it as the answer? $\endgroup$
    – Royi
    May 24, 2022 at 11:48

3 Answers 3


You may download the NFFT Library - Non Equispaced Fast Fourier Transform.
It has interfaces for MATLAB, Octave and Julia.


After more testing I think I found a problem with the way the algorithm is formulated. According to Eq. (60)

$$ \sum_{k=0}^N\alpha_k \sum_{j=-q/2}^{q/2}P_{jk}\, e^{i(\mu_k+j)x/m}=\sum_{j=-mN/2}^{mN/2-1}\tau_j\, e^{ijx/m} $$.

The idea is to compute the r.h.s. using an inverse FFT. The problem with this is is that some terms of the sum on the l.h.s. are left out: I have verified that when these terms are included by explicitly computing the sum (no FFT involved), the relative approximation error goes down to 1e-3. So the question is: how does one compute the l.h.s. sum using an $m N$ points inverse DFT with kernel $e^{2\pi i k j/(m N)}$ (Eq. (62)) ?


The correct way to implement the sum in the previous answer is

for $l=-m N/2$ to $m N/2-1$

$\quad$ for $k=0$ to $N$

$\quad\quad$ for $j=-q/2$ to $q/2$

$\quad\quad\quad$ if $l==\mod(\mu_k+j+m N/2,m N)-m N/2$,

$\quad\quad\quad\quad$ $\tau_l=\tau_l+\alpha_k P_{jk}$

$\quad\quad\quad$ end

$\quad\quad$ end

$\quad$ end

In this way all the terms $\alpha_k P_{jk}$ are accounted for in the sum.

  • $\begingroup$ Answers don't appear in the same order each time the page is loaded. Could you make it more clear which "previous" answer you're referencing? $\endgroup$
    – The Photon
    Jul 3, 2013 at 21:09
  • $\begingroup$ Furthermore, it looks like the "previous answer" is your own answer...It would be better to just edit your answer to include this additional information. $\endgroup$
    – The Photon
    Jul 3, 2013 at 21:10
  • $\begingroup$ I just tried to move that as comment to my previous answer but the pseudocode is not formatted correctly. $\endgroup$
    – Arrigo
    Jul 3, 2013 at 21:37
  • $\begingroup$ To the lower left of the text of your answer there's the word "edit". If you click that, you can simply edit the text of your older answer and include this extra information. It might help to open both answers for editing in separate windows so you can cut and paste the markup. $\endgroup$
    – The Photon
    Jul 3, 2013 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.