topic Hi, in Intel® Integrated Performance Primitives

What algorithm was used for function ippiDFTFwd_RToPack_32f_C1R and what is the algorithm complexity?

Zhifei_X_ — Thu, 27 Jun 2013 04:45:23 GMT

What algorithm was used for function ippiDFTFwd_RToPack_32f_C1R?

And what is the algorithm complexity? like the method in FFTW?

I tried to increase the image size for the ippiDFTFwd_RToPack_32f_C1R, the execution time is not monotone increasing (of couse, 2^n is of the minimum execution time). Is there any theory analysis of the algorithm complexity for ippiDFTFwd_RToPack_32f_C1R? Many thanks!

>>...What algorithm was used

SergeyKostrov — Thu, 27 Jun 2013 23:34:39 GMT

>>...What algorithm was used for function ippiDFTFwd_RToPack_32f_C1R? Intel never releases details on internals of some API / algorithms and a generic answer could be as follows: a DFT-like algorithm is used. Please try to search for articles or application notes on Intel web-site related to DFT processing. Note: I checked my collection of Intel articles and I have these two: Split-Radix FFT.17649.pdf SSE in a Fast DCT Algorithm.40981.pdf

Hi, Sergey, could you send me

Zhifei_X_ — Wed, 10 Jul 2013 06:36:53 GMT

Hi, Sergey, could you send me the articles? I tried to search but can not find the pdf files.

Split-Radix FFT.17649.pdf
SSE in a Fast DCT Algorithm.40981.pdf

Many thanks!

Hi,

Igor_A_Intel — Wed, 10 Jul 2013 10:48:26 GMT

Hi,

IPP DFT is based on vector/image length/size decomposition on primes. Prime factors that have special code branches are 2,3,5,7,11,13. For powers of 2 (FFT) supported radixes are 2,4,8,16 (depends on architecture - radix-8 is supported on Intel64, radix-16 - on Xeon-Phi only). For lengths/sizes that can't be decomposed on these primes (or for reminder parts) - convolution based algorithm is used. In general case you may consider algorithm complexity as ~5*n*log2(n) arithmetic operations per 1 call (1D case, n==vector length).

Regards, Igor

>>...could you send me the

SergeyKostrov — Wed, 10 Jul 2013 12:40:24 GMT

>>...could you send me the articles? I tried to search but can not find the pdf files. >> >>Split-Radix FFT.17649.pdf >>SSE in a Fast DCT Algorithm.40981.pdf Yes and I'll do it later today.

>>>>...could you send me the

SergeyKostrov — Thu, 11 Jul 2013 01:29:47 GMT

>>>>...could you send me the articles? I tried to search but can not find the pdf files. >>>> >>>>Split-Radix FFT.17649.pdf >>>>SSE in a Fast DCT Algorithm.40981.pdf >> >>Yes and I'll do it later today. Here they are.

>>>>Split-Radix FFT.17649.pdf

SergeyKostrov — Thu, 11 Jul 2013 13:21:32 GMT

>>>>Split-Radix FFT.17649.pdf Here is a zip-file with sources.