Turn on suggestions

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

Showing results for

- Intel Community
- Software Development SDKs and Libraries
- Intel® oneAPI Math Kernel Library & Intel® Math Kernel Library
- What is the best way to improve FFT transform performance?

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

Highlighted
##

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

Employee

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

10-16-2009
02:23 PM

18 Views

What is the best way to improve FFT transform performance?

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

Thanks.

3 Replies

Highlighted
##

*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.

Zhu_W_Intel

Employee

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

10-16-2009
02:34 PM

18 Views

Quoting - Zhu Wang (Intel)

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.

Highlighted
##

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

Dmitry_B_Intel

Employee

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

10-18-2009
08:09 PM

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

Highlighted
##

Hi Zhu,

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

-- Victor

barragan_villanueva_

Valued Contributor I

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

10-19-2009
11:44 PM

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

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