topic Re: What is the best way to improve FFT transform performance? in Intel® oneAPI Math Kernel Library

What is the best way to improve FFT transform performance?

Zhu_W_Intel — Fri, 16 Oct 2009 21:23:13 GMT

I am using DftiComputeForward. Sometimes, my matrix size happens to be two prime numbers, such as 761*769, The FFT performance is really bad compared to some smaller matrix size, such as 401*401. It is about 2 -3 times slower.

What is the best way to improve the performance here? I have to maintain the accuracy of the result too.

Thanks.

Re: What is the best way to improve FFT transform performance?

Zhu_W_Intel — Fri, 16 Oct 2009 21:34:22 GMT

Quoting - Zhu Wang (Intel)

Sorry, I should be more clear. I am saying when the matrix size is two prime numbers, such as 701*701, the 2D FFT performance is much worse then non-prime number matrix size, even the matrix size is bigger, such as 715*715.

Re: What is the best way to improve FFT transform performance?

Dmitry_B_Intel — Mon, 19 Oct 2009 03:09:16 GMT

Hi Zhu,

FFT is algoritmically based on factorization of the size of the transform. If the size is a composite number, an efficient algorithm is applicable which reduces the original FFT to the FFTs of thesize of the factors. If the original sizeis aprime number,less efficient algoritms are used, in particular the one that computes the FFT via the FFT of at leasttwice larger size which is non-prime. That is why you see the performance on the prime size is worse than that on non-prime. Both types of algorithms do O(n log n) operations, however. So, one way to improve performance of your application isto avoid prime size transforms.

Thanks
Dima

Re: What is the best way to improve FFT transform performance?

barragan_villanueva_ — Tue, 20 Oct 2009 06:44:01 GMT

Hi Zhu,

I'd suggest additioanally to what Dima wrote: use sizes whichconsistof powers of smal radixes: 2,3,5,7,11.

-- Victor