What is the best way to improve FFT transform performance?

[Zhu_W_Intel]

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.

[Zhu_W_Intel]

Quoting - Zhu Wang (Intel)

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.

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.

[Dmitry_B_Intel]

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

[barragan_villanueva_]

Hi Zhu,

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

-- Victor