Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Mute
- Printer Friendly Page

holysword

Beginner

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

12-04-2017
01:51 AM

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?

Link Copied

3 Replies

Ying_H_Intel

Employee

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

12-04-2017
05:59 PM

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

12-05-2017
01:40 AM

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:

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

New Contributor I

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

12-12-2017
11:47 AM

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

Topic Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page

For more complete information about compiler optimizations, see our Optimization Notice.