Truncated DFTI

[holysword]

Hello there,

This might be a silly question, so pardon me if it is.

Let us say that I want to perform M 1D DFTs (let us say, complex-complex) on an array of dimension N, but I only need the first P entries instead of M (e.g. by construction, I know that only the first P entries will be nonzero).

Right now what I do is to compute it full and then discard the last (M-P) entries. It then requires 2 arrays, one temporary, MxN, and the truncated one which I'll effectively use in my code, PxN. Also, if I want to do the backward transform I need to copy the PxN array into an MxN array, padded with zeroes, and then call the transform.

Is there any way to avoid the MxN array altogether and tell MKL that I am just interested in the first P entries for each 1D DFT?

[Ying_H_Intel]

Hi holysword, 

To set DFTI_INPUT_STRIDES, DFTI_OUTPUT_STRIDES   to access the first P or PXN array may help to complete the task.  Please refer to MKL developer guide https://software.intel.com/en-us/mkl-developer-reference-c-dfti-input-strides-dfti-output-strides ; , and MKL DFT sample in install folder. 

If all of them don't work, please submit your request to our official support channel: Online Service Center. 

Best Regards

Ying

[holysword]

I don't think you quite understood my question (or I didn't quite understand your answer). If I understand it correctly, stridden data would be useful if P>M. My case is the opposite, P<M. Therefore, I am padding it with zeroes, lest MKL will overstep and get garbage from the memory.

What I am trying to do is, basically:

X_k = Σ x_j * e^-2πijk/M

for j and k=1..M, where either some x_j are equal to zero or, by construction, I know that some X_k will be zero. I cannot change M, because that changes the exponent, but I was hoping I could "truncate" the sum, by telling MKL that it is not necessary to compute further terms.

[MGRAV]

I challenge a similar problem recently. Where I did huge padding for convolutions.

And it looks impossible ! Sorry

More in detail if have a pattern of x_j that is null, it's possible to do something for example one over 2 ...

if P << M, (at least P < M/2) you can have a look at pruned FFTs http://www.fftw.org/pruned.html

If P <<< M you can just compute the sum manually.

What is your final goal?

Some link about Sparse FFT, that can be interesting if approximations are ok too, https://groups.csail.mit.edu/netmit/sFFT/, http://www.spiral.net/software/sfft.html