# Computing a pruned FFT in O(n\*log(k))

**URL:** <https://discourse.julialang.org/t/computing-a-pruned-fft-in-o-n-log-k/89570>\
**Category:** Numerics\
**Tags:** fftw\
**Created:** [October 31, 2022, 3:31pm UTC](https://discourse.julialang.org/t/computing-a-pruned-fft-in-o-n-log-k/89570 "2022-10-31T15:31:52Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![nvenkov1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nvenkov1/32/43679_2.png) [@nvenkov1](https://discourse.julialang.org/u/nvenkov1)\
**Post date:** [October 31, 2022, 3:31pm UTC](https://discourse.julialang.org/t/computing-a-pruned-fft-in-o-n-log-k/89570/1 "2022-10-31T15:31:52Z")

</div>

Let’s say that I consider a DFT with n coefficients. I am only interested in k\<\<n of these coefficients. In theory, it is possible to compute these k coefficients in O(n\* log(k)) instead of O(n\* log(n)), see [https://www.fftw.org/pruned.html](https://www.fftw.org/pruned.html). This is called the pruned FFT. Does someone know how to compute a pruned FFT in Julia that runs in O(n\*log(k))?

---

<div class="post-metadata">

**Author:** ![lobingera](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/lobingera/32/211_2.png) [@lobingera](https://discourse.julialang.org/u/lobingera)\
**Post date:** [October 31, 2022, 5:42pm UTC](https://discourse.julialang.org/t/computing-a-pruned-fft-in-o-n-log-k/89570/2 "2022-10-31T17:42:57Z")

</div>

> **[Pruned FFTs with FFTW](http://www.fftw.org/pruned.html)**
>
> On computing pruned FFTs, with only a subset of inputs and outpus, using FFTW.

> **[Issues · JuliaMath/FFTW.jl](https://github.com/JuliaMath/FFTW.jl/issues)**
>
> Julia bindings to the FFTW library for fast Fourier transforms - Issues · JuliaMath/FFTW.jl

---

<div class="post-metadata">

**Author:** ![nvenkov1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nvenkov1/32/43679_2.png) [@nvenkov1](https://discourse.julialang.org/u/nvenkov1)\
**Post date:** [October 31, 2022, 6:36pm UTC](https://discourse.julialang.org/t/computing-a-pruned-fft-in-o-n-log-k/89570/3 "2022-10-31T18:36:21Z")

</div>

This is the link I posted myself. If this is a solution, it’s only for the case where one wants the k first coefficients, and not arbitrary components of the transform. But let’s say I try to expand on it, then what is the equivalent of fftw\_plan\_many\_dft in FFTW.jl? I don’t see it among the functions available in the package. I’ll think about it more and post my solution if I get something running.

---

<div class="post-metadata">

**Author:** ![nvenkov1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nvenkov1/32/43679_2.png) [@nvenkov1](https://discourse.julialang.org/u/nvenkov1)\
**Post date:** [November 5, 2022, 11:50am UTC](https://discourse.julialang.org/t/computing-a-pruned-fft-in-o-n-log-k/89570/4 "2022-11-05T11:50:53Z")

</div>

The procedure for the pruned FFT described by FFTW is O(n log(k)) to compute k coefficients out of n. Interestingly, I found a C++ library called sparse fast Fourier transform ([SFFT](https://groups.csail.mit.edu/netmit/sFFT/)) that does the same thing in O(k log(n)).

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [November 5, 2022, 1:00pm UTC](https://discourse.julialang.org/t/computing-a-pruned-fft-in-o-n-log-k/89570/5 "2022-11-05T13:00:18Z")

</div>

> [@nvenkov1](#):
>
> it’s only for the case where one wants the k first coefficients, and not arbitrary components of the transform. But let’s say I try to expand on it, then what is the equivalent

See the references at the end of that page, for example. My understanding is that the constant factors are going to be significantly worse if you want a completely arbitrary set of coefficients (as least for exact algorithms).

(If you just want a different block of k _consecutive_ coefficients, you can easily modify the code on the FFTW page: multiply the inputs by a linear phase, which has O(n) cost, and the window of computed coefficients is shifted via the shift theorem.)

> [@nvenkov1](#):
>
> Interestingly, I found a C++ library called sparse fast Fourier transform ([SFFT](https://groups.csail.mit.edu/netmit/sFFT/)) that does the same thing in O(k log(n)).

No, it’s not doing the same thing — it’s solving a different problem.

A pruned FFT computes k specified DFT outputs from n inputs, regardless of the values of the inputs or the other outputs. (The pruned FFT on the FFTW page, for k consecutive outputs, is exact up to roundoff errors, but there are also other algorithms that are approximate.)

The SFFT algorithm works _only_ if you have inputs such that there are _only_ k nonzero (or at least non-negligible) outputs of the DFT (i.e. the outputs are “sparse”), but you _don’t_ have to know _which_ outputs are nonzero. Moreover, it’s a randomized, approximate algorithm (via sampling the inputs) — and there are additional errors if the other DFT outputs are not exactly zero.

(The original SFFT authors are at MIT too and I’ve chatted with them on occasion. Note that the SFFT method actually uses an ordinary FFT as a subroutine, and in fact their code uses FFTW itself.)

---

<div class="post-metadata">

**Author:** ![nvenkov1](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/nvenkov1/32/43679_2.png) [@nvenkov1](https://discourse.julialang.org/u/nvenkov1)\
**Post date:** [November 6, 2022, 12:05pm UTC](https://discourse.julialang.org/t/computing-a-pruned-fft-in-o-n-log-k/89570/6 "2022-11-06T12:05:46Z")

</div>

Thanks for these clarifications!