Pruned Uniform-to-Uniform FFTs

[stumarcus314]

If I only wanted a percentage, say a half or a quarter, of the output frequencies of a uniform-to-uniform FFT, would it be faster to a) use a type-2 NUFFT (such as provided in FINUFFT), specifying only the subset of desired output frequencies, or to b) use an unpruned uniform-to-uniform FFT library (like FFTW) and discard the unwanted output frequencies? I know that if the percentage of desired output frequencies of a uniform-to-uniform FFT is very small, then the Goertzel algorithm is the computationally-efficient way to go: https://en.wikipedia.org/wiki/Goertzel_algorithm

Does FINUFFT offer the ability to compute uniform-to-uniform FFTs, by directly calling the underlying FFT library like FFTW or DUCC0 FFT? This would be useful for method b.

[ahbarnett]

Dear Stu, Unless you want only 5% or less, I think it's not worth doing any fancy transforms. Just do the regular FFT and discard. SGJ has a discussion about this here: https://www.fftw.org/pruned.html If you did want, say, the lowest 1% of outputs, you should use the strided smaller-FFT algorithm on that page. FINUFFT will not help you here, and there's no reason for us to provide an interface to the "bare" FFT since the FFT libraries already have that (apart from DUCC0, which you'd have to wrap yourself). FFTW is available in every modern high-level language. Best, Alex

…

On Wed, May 21, 2025 at 4:04 PM stumarcus314 ***@***.***> wrote: *stumarcus314* created an issue (flatironinstitute/finufft#683) <#683> If I only wanted a percentage, say a half or a quarter, of the output frequencies of a uniform-to-uniform FFT, would it be faster to a) use a type-2 NUFFT (such as provided in FINUFFT), specifying only the subset of desired output frequencies, or to b) use an unpruned uniform-to-uniform FFT library (like FFTW) and discard the unwanted output frequencies? Does FINUFFT offer the ability to compute uniform-to-uniform FFTs, by directly calling the underlying FFT library like FFTW or DUCC0 FFT? This would be useful for method b. — Reply to this email directly, view it on GitHub <#683>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACNZRSQ5ODFWO3CHUYYCOL327TL4XAVCNFSM6AAAAAB5UGS5QWVHI2DSMVQWIX3LMV43ASLTON2WKOZTGA4DCMRYHE4DONA> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

-- *-------------------------------------------------------------------~^`^~._.~' |\ Alex Barnett Center for Computational Mathematics, Flatiron Institute | \ http://users.flatironinstitute.org/~ahb 646-876-5942

[mreineck]

Just wanted to add two short remarks:

• in 1D I completely agree with Alex that it will be very hard to beat the standard FFT by any interesting amount. But as SGJ also mentions, things can look different for multidimensional transforms; in fact, this is already used in the FFT part of finufft itself to save a bit of time (when using the ducc0 FFT.)
• ducc0's FFT does come with a Python wrapper, in case you are interested in using it :)

[stumarcus314]

FFTW++ is an FFT library built on top of FFTW and can improve the performance of convolutions, especially in 2D and 3D. FFTW++ may be useful for FINUFFT.
https://fftwpp.sourceforge.net/
https://sourceforge.net/projects/fftwpp/
https://github.com/dealias/fftwpp