Community
cancel
Showing results for 
Search instead for 
Did you mean: 
holysword
Beginner
84 Views

Truncated DFTI

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?

0 Kudos
3 Replies
Ying_H_Intel
Employee
84 Views

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
Beginner
84 Views

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:

Xk = Σ xj * e-2πijk/M

for j and k=1..M, where either some xj are equal to zero or, by construction, I know that some Xwill 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
New Contributor I
84 Views

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

Reply