0
Under review

Nonequidistant FFT

didier.clamond 4 years ago updated by Pavel Holoborodko 4 years ago 6

Dear Pavel,


It would be great to support the non-equidistant Fast Fourier Transform.

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


Regards,

Didier

Under review

Dear Didier,


Thank you very much for the suggestion!

What would be the most important feature set?

(NFFT has quite a bit of features)

Thanks Pavel for your quick reply.


For now, my priority would be the 1D complex FFT,

with non- equidistant sampling in time and/or frequency (NNFFT).


In the future, support for DCT and DST of types I, II and IV would

be great, as well as their multi-dimensional extensions.


Note that I have no ideas how difficult it is to implement that in Advanpix

(NFFT relies on FFTW).


Also, since high precision allows huge number of nodes, a parallel 1D FFT

may be of practical interest. Again, I have no ideas how difficult/beneficial it

would be to implement it.


Didier

Thank you for the important details - very interesting!


The main difficulty is not FFTW per se, but licensing terms of NFFT and FFTW.

GNU GPL license doesn't allow usage of these libraries in closed source products.

Alternatively I have to buy extremely expensive commercial licenses for them, $5K+.


This functionality was already requested (by Denis) and I will see what I can do in more details.

Full re-write is needed at the very least to not breach the licensing terms.


Will update you on this (no high hopes for nearest future).

-1

Ouch, I forgot these licence issues!

Then, ignore my request.


Didier

I am trying to contact the developers to know what licensing terms available for closed-source projects.


Meanwhile I found that there is pure MATLAB implementation of NFFT:

http://web.eecs.umich.edu/~fessler/irt/irt/nufft/


It was developed by one of the original authors.


I haven't check its source code but chances are that it can be used with toolbox (?).

I have just received response from MIT as for FFTW licensing possibilities for non-profit organization (like Advanpix):


Full commercial license is $12500.

License price for non-profits is $8333.


I am still waiting response from NFFT team - I hope for more sensible answer.

At the very least - I will replace calls to FFTW with my code.