0
$\begingroup$

I'm looking to compute an IDFT but my input is very sparse:

Example:

  • IDFT length: 7,408,800 (complex floats)
  • Sparsity: 96.61% to 99.99%

I found this Sparse FFT website but it looks like the library deals with sparse inputs to standard DFT - not IDFT - also it doesn't look like it is not for consumer use.

Are there any techniques I can employ to improve performance for sparse IDFT - before even changing my DFT library? And now, are there any available libraries that give performance improvements for spare IDFT?

| improve this question | |
$\endgroup$
  • $\begingroup$ You can easily modify the input and output of a DFT (it's just time reversals and complex conjugates, no "actual" computation) to make an IDFT. However, would be cool if you could explain how long your DFT is and how sparse it is, i.e. how many of the inputs are non-zero. That would allow for an algorithmic recommendation! $\endgroup$ – Marcus Müller Jul 18 at 12:55
  • $\begingroup$ @MarcusMüller Ranges somewhere from 50% to 95% sparsity $\endgroup$ – Tobi Akinyemi Jul 18 at 12:55
  • $\begingroup$ uh, does that mean 70% to 98% are actual non-zero values? Because: that's not very sparse, and the regular FFT will be the best you can do. $\endgroup$ – Marcus Müller Jul 18 at 12:56
  • $\begingroup$ @MarcusMüller I just calculated, 0.00329% of the data is non-zero (99.99% sparse) at the worst case. In the best case 3.38% is non-zero (96.61% sparsity). $\endgroup$ – Tobi Akinyemi Jul 18 at 13:03
  • $\begingroup$ As you can see, this is seriously sparse $\endgroup$ – Tobi Akinyemi Jul 18 at 13:03
2
$\begingroup$

The FFT is faster than the naive DFT through matrix-vector products because it can reuse many intermediate results.

However, for inputs this sparse, there's really not much that can be re-used, even in the best case.

So, the most efficient way here is probably to work straight forward:

  • Allocate the space ($N=7408800$ values) for your output (initialize with zeros) $o$.
  • Go through your input $i$. Nested loops:
    • For every nonzero input index $n$:
      • For every output index $k$: add $i_ne^{j2\pi \frac{nk}N}$ to $o_k$.

Notes:

  • since with sparse input, your output is non-sparse, it's usually faster to traverse the input only once, but the output many times, instead of the other way around (that is because memory is much faster when addressed linearly)
  • to calculate the complex exponential, you can use SIMD-accelerated calculations, because the values are in consecutive addresses and have proportional phase. LibVOLK has a number of implementations that might be helpful for fast calculation here.
| improve this answer | |
$\endgroup$
  • $\begingroup$ I'm doing a complex to complex IDFT - so I need the full output. I think the half output applies to real to complex DFT's $\endgroup$ – Tobi Akinyemi Jul 18 at 15:19
  • $\begingroup$ What I'm getting from your answer is to essentially implement the classical DFT, because the FFT is not so optimal for sparse data. Is this correct? $\endgroup$ – Tobi Akinyemi Jul 18 at 15:20
  • $\begingroup$ well, not really, no: the classical DFT would be multiplying a lot of zeros. What you're doing here is omitting everything that's just a zero multiplication. The result is the same. $\endgroup$ – Marcus Müller Jul 18 at 15:24
  • 1
    $\begingroup$ @TobiAkinyemi yes, if you want to know how to use SFFT for your specific problem. Isn't it your purpose? If you just want to know the complexity, Marcus, as the author, has already given the answer. The complexity is calculated the same way SFFT authors claimed the complexity O(klog(n)). Cited from the SFFT website This code is provided for research purposes only. At this stage the code is not a standalone portable library and cannot be used blindly. Using the library without understanding the theory will be dangerous. $\endgroup$ – AlexTP Jul 18 at 22:05
  • 2
    $\begingroup$ The imaginary unit. It's pretty usual to denote that with $j$ instead of $i$ in things that deal with signals, because a lot of these disciplines arose from electrical engineering, and $i$ was already used for currents. Anyway, don't you think you should have been asking about understanding of the answer before proposing other things in the comments? And this is really basic... $\endgroup$ – Marcus Müller Jul 19 at 8:22

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.