4
$\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$
13
  • $\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, 2020 at 12:55
  • $\begingroup$ @MarcusMüller Ranges somewhere from 50% to 95% sparsity $\endgroup$
    – Tobi Akinyemi
    Jul 18, 2020 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, 2020 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, 2020 at 13:03
  • 1
    $\begingroup$ Sparse FFT is for sparse output of the transform. You have sparse input so it is not applicable. $\endgroup$
    – Olli Niemitalo
    Jul 21, 2020 at 14:08

1 Answer 1

Reset to default
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$
28
  • 1
    $\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, 2020 at 15:19
  • 1
    $\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, 2020 at 15:20
  • 1
    $\begingroup$ Do you know the time complexity of your solution $\endgroup$
    – Tobi Akinyemi
    Jul 18, 2020 at 19:09
  • 1
    $\begingroup$ I believe SFFT is klog(n). Here you iterate through n, implying its at best O(n) $\endgroup$
    – Tobi Akinyemi
    Jul 18, 2020 at 19:09
  • 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, 2020 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.