Community
cancel
Showing results for 
Search instead for 
Did you mean: 
Highlighted
Employee
18 Views

What is the best way to improve FFT transform performance?

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.
0 Kudos
3 Replies
Highlighted
Employee
18 Views

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.
0 Kudos
Highlighted
Employee
18 Views


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
0 Kudos
Highlighted
Valued Contributor I
18 Views


Hi Zhu,

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

-- Victor
0 Kudos