2
$\begingroup$

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 freely 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.

| improve this question | |
$\endgroup$
  • $\begingroup$ Did you use my answer? Could you please mark it as the answer? $\endgroup$ – Royi Oct 27 '19 at 11:12
3
$\begingroup$

You can download it here NFFT Library (Nonequispaced Fast Fourier transform):

http://www-user.tu-chemnitz.de/~potts/nfft/

Enjoy.

| improve this answer | |
$\endgroup$
1
$\begingroup$

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)) ?

| improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\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 '13 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 '13 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 '13 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 '13 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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