This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
|
I would like this page to mention which algorithm is used by FFTW. This could include a link to "Category:FFT_algorithms" (I don't know how to make this link properly)
I'd never heard of Dan Bernstein until I looked at this page. It seems to me that the mention of his "controversy" is redundant on this page. The link is to a web page of Bernstein's (i.e. not an article in a journal, or an independent web page) and having studied his library (and being well aware of FFTW), I am inclined to delete all mention of Bernstein and his library. Here are my reasons: unless someone can link in some third party sources on the controversy (i.e. not Bernstein's own material) I think the inclusion of the controversy violates NPOV. The Bernstein library hasn't been updated since 1999 and it is limited to powers of 2 lengths. Also, from reading its code, it seems to depend on providing a different function for each size of array. Great to use if your data array is a fixed size (and a power of 2) but no good if you sometimes want to pass a 256 element array and sometimes a 512 element array. FFTW in contrast, handles arbitrary sizes with a single call. Anyone else have a view? Sangwine 22:01, 12 December 2006 (UTC)
As one of the FFTW authors, I have avoided this page (due to WP:COI) and don't really want to reopen an old flamewar, but I feel I should comment here. The facts which are undisputed, as far as I can tell, are:
DJB also had some other criticisms, e.g. he doesn't like the way we plot our graphs (he prefers tables of raw timing numbers whereas we find a speed rescaled by N log N more readable), but on these matters we continue to disagree. The claim that we have "refused to acknowledge" djbfft is false (we have linked to the djbfft website since 1997).
(Nowadays, both djbfft and pfftw are trounced on Intel processors by anything that uses SSE/ SSE2 instructions, such as recent FFTW versions or the Intel Math Kernel Libraries.)
To what extent Wikipedia should comment on this I leave up to others. However, I'm not sure that it's fair to simply link to DJB's page on the issue, which is (indisputably) one-sided and (arguably) out-of-date.
—Steven G. Johnson 20:29, 20 December 2006 (UTC)
OK, that comment (by Steven Johnson) is helpful. I don't see exactly how to resolve this, so I have flagged the controversy part of the article with what seems to me to be the appropriate tag (self-published source). If anyone can cite some independent material or add a third or fourth opinion, then maybe this issue can be resolved. Sangwine 16:09, 22 December 2006 (UTC)
I'm removing the controversy section, mostly because of the ugly template. If anyone wants to include this material, then feel free to supply reliable third-party sources for it. Is this controversy notable? Then surely some third party has taken it up. Otherwise, I'm removing outdated self-published material as is the policy of the english wikipedia. Thanks, Vesal ( talk) 11:52, 22 August 2008 (UTC)
I have rewritten the technical description of FFTW:
1) Collected the description of the (wide range of) transforms that FFTW supports to the beginning of the technical description.
2) Add more information/use wiki-refs: Complex number, Big-O notation, prime factors, power of two, heuristics, etc.
3) The expression 'particularly strong feature' has been removed, since the truth of this evaluation depends on the needs of the FFTW user and since users may find other features in FFTW to be 'particularly strong' (e.g. the support for non-power of two arrays or the use of SIMD operations). However, since many users may benefit from this interesting measuring-feature, a significant part of the description is dedicated to this topic.
4) The FFTW term guru is defined at the beginning of the last part of the technical description.
5) Highlight FFTW terminology: wisdom, guru.
At least some FFT algorithms permute the transformed elements (by bit-reversing their index), thus unpermuting them incurs an overhead.
When I started working with FFTs (on a CM-200 15 years ago), this overhead was large enough that the FFT library supported Out-of-order transforms, i.e. transforms where the transformed elements where returned to the caller in the permuted order.
In many cases such an Out-of-order transform requires no extra coding by the caller, e.g. when two arrays are transformed, then multiplied elementwise, and then transformed back.
Since FFTW seems to support all other possible (and impossible :-) variants of the FFT, it is natural to wonder why Out-of-order transforms are not supported.
I googled fftw.org to no avail, so can anybody here answer this question ? (I notice an FFTW author has been active on this page)
Thanks, Lklundin 23:09, 30 March 2007 (UTC).
The main article includes the sentence 'FFTW is known as the fastest free software implementation of the Fast Fourier transform (FFT) algorithm'.
Although the FFTW web-site lists extensive benchmarks to support this claim, the sentence may still need some improvement, since the passive voice ('is known') is listed under Wikipedia:AWT.
An anonymous at 67.160.224.159 has twice made unexplained, (poor grammar) changes to the sentence, but I find these changes too negative, especially in the light of the provided benchmarks. I have therefore reverted these two changes, hoping for something better.
Lklundin ( talk) 17:51, 6 February 2008 (UTC)
It doesn't seem appropriate for the article to link to my userpage; doesn't that violate Wikipedia:Self-references to avoid? —Steven G. Johnson ( talk) 00:12, 6 November 2008 (UTC)
Matteo Frigo was at the MIT Laboratory for Computer Science (LCS) when FFTW was first developed, but I was in the MIT Physics Department. (I'm currently in MIT's Department of Mathematics, and Matteo has had several different positions, so there is not presently any direct association between FFTW and LCS/ CSAIL.)
—Steven G. Johnson ( talk) 05:28, 5 December 2008 (UTC)
I'm not sure if Wikipedia is the place for this, but I wanted to know if it would be appropriate to also add an external link showing the basic C implementation of the FFTW libraries. I have been using my implementation of FFTW for a while now at Griffith University, Australia for Signal processing and I constantly have students asking me how to implement the most basic FFT and IFFT in C. And I thought since Wikipedia is usually their first point of call when researching, could it also point them in the right direction for implementation. Something like: C Programming: The reconstruction of the Fast Fourier transform of a real signal using FFTW libraries for the most basic implementation, or something similar.
—Roger Chappel ( talk) 19:48, 17 June 2011 (UTC)
Hi all, I noticed that, currently, reference 5 (which is the source for how "[FFTW] is also licensed commercially (for a cost of up to $12,500) by MIT") as-linked ( http://technology.mit.edu/technologies/15054_fastest-fourier-transform-in-the-west-fftw-version-3-3-x-fftw-v-3-3-x) redirects to a general landing page. Should we update the source for that information to the MIT TLO's current page on FFTW? The latest link is: https://tlo.mit.edu/technologies/fftw-fastest-fourier-transform-west.
Alternatively, we could add a link to an archived version of the old web page. (I'm new to Wikipedia, so I'm not sure if one option is preferred over another.) Here is the Internet Archive link: https://web.archive.org/web/20170128024924/http://technology.mit.edu/technologies/15054_fastest-fourier-transform-in-the-west-fftw-version-3-3-x-fftw-v-3-3-x. This is the latest archived copy of the webpage that doesn't redirect the same way it does now.
Any guidance? Thanks in advance!
— QB2k ( talk) 11:54, 3 February 2023 (UTC)
This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||
|
I would like this page to mention which algorithm is used by FFTW. This could include a link to "Category:FFT_algorithms" (I don't know how to make this link properly)
I'd never heard of Dan Bernstein until I looked at this page. It seems to me that the mention of his "controversy" is redundant on this page. The link is to a web page of Bernstein's (i.e. not an article in a journal, or an independent web page) and having studied his library (and being well aware of FFTW), I am inclined to delete all mention of Bernstein and his library. Here are my reasons: unless someone can link in some third party sources on the controversy (i.e. not Bernstein's own material) I think the inclusion of the controversy violates NPOV. The Bernstein library hasn't been updated since 1999 and it is limited to powers of 2 lengths. Also, from reading its code, it seems to depend on providing a different function for each size of array. Great to use if your data array is a fixed size (and a power of 2) but no good if you sometimes want to pass a 256 element array and sometimes a 512 element array. FFTW in contrast, handles arbitrary sizes with a single call. Anyone else have a view? Sangwine 22:01, 12 December 2006 (UTC)
As one of the FFTW authors, I have avoided this page (due to WP:COI) and don't really want to reopen an old flamewar, but I feel I should comment here. The facts which are undisputed, as far as I can tell, are:
DJB also had some other criticisms, e.g. he doesn't like the way we plot our graphs (he prefers tables of raw timing numbers whereas we find a speed rescaled by N log N more readable), but on these matters we continue to disagree. The claim that we have "refused to acknowledge" djbfft is false (we have linked to the djbfft website since 1997).
(Nowadays, both djbfft and pfftw are trounced on Intel processors by anything that uses SSE/ SSE2 instructions, such as recent FFTW versions or the Intel Math Kernel Libraries.)
To what extent Wikipedia should comment on this I leave up to others. However, I'm not sure that it's fair to simply link to DJB's page on the issue, which is (indisputably) one-sided and (arguably) out-of-date.
—Steven G. Johnson 20:29, 20 December 2006 (UTC)
OK, that comment (by Steven Johnson) is helpful. I don't see exactly how to resolve this, so I have flagged the controversy part of the article with what seems to me to be the appropriate tag (self-published source). If anyone can cite some independent material or add a third or fourth opinion, then maybe this issue can be resolved. Sangwine 16:09, 22 December 2006 (UTC)
I'm removing the controversy section, mostly because of the ugly template. If anyone wants to include this material, then feel free to supply reliable third-party sources for it. Is this controversy notable? Then surely some third party has taken it up. Otherwise, I'm removing outdated self-published material as is the policy of the english wikipedia. Thanks, Vesal ( talk) 11:52, 22 August 2008 (UTC)
I have rewritten the technical description of FFTW:
1) Collected the description of the (wide range of) transforms that FFTW supports to the beginning of the technical description.
2) Add more information/use wiki-refs: Complex number, Big-O notation, prime factors, power of two, heuristics, etc.
3) The expression 'particularly strong feature' has been removed, since the truth of this evaluation depends on the needs of the FFTW user and since users may find other features in FFTW to be 'particularly strong' (e.g. the support for non-power of two arrays or the use of SIMD operations). However, since many users may benefit from this interesting measuring-feature, a significant part of the description is dedicated to this topic.
4) The FFTW term guru is defined at the beginning of the last part of the technical description.
5) Highlight FFTW terminology: wisdom, guru.
At least some FFT algorithms permute the transformed elements (by bit-reversing their index), thus unpermuting them incurs an overhead.
When I started working with FFTs (on a CM-200 15 years ago), this overhead was large enough that the FFT library supported Out-of-order transforms, i.e. transforms where the transformed elements where returned to the caller in the permuted order.
In many cases such an Out-of-order transform requires no extra coding by the caller, e.g. when two arrays are transformed, then multiplied elementwise, and then transformed back.
Since FFTW seems to support all other possible (and impossible :-) variants of the FFT, it is natural to wonder why Out-of-order transforms are not supported.
I googled fftw.org to no avail, so can anybody here answer this question ? (I notice an FFTW author has been active on this page)
Thanks, Lklundin 23:09, 30 March 2007 (UTC).
The main article includes the sentence 'FFTW is known as the fastest free software implementation of the Fast Fourier transform (FFT) algorithm'.
Although the FFTW web-site lists extensive benchmarks to support this claim, the sentence may still need some improvement, since the passive voice ('is known') is listed under Wikipedia:AWT.
An anonymous at 67.160.224.159 has twice made unexplained, (poor grammar) changes to the sentence, but I find these changes too negative, especially in the light of the provided benchmarks. I have therefore reverted these two changes, hoping for something better.
Lklundin ( talk) 17:51, 6 February 2008 (UTC)
It doesn't seem appropriate for the article to link to my userpage; doesn't that violate Wikipedia:Self-references to avoid? —Steven G. Johnson ( talk) 00:12, 6 November 2008 (UTC)
Matteo Frigo was at the MIT Laboratory for Computer Science (LCS) when FFTW was first developed, but I was in the MIT Physics Department. (I'm currently in MIT's Department of Mathematics, and Matteo has had several different positions, so there is not presently any direct association between FFTW and LCS/ CSAIL.)
—Steven G. Johnson ( talk) 05:28, 5 December 2008 (UTC)
I'm not sure if Wikipedia is the place for this, but I wanted to know if it would be appropriate to also add an external link showing the basic C implementation of the FFTW libraries. I have been using my implementation of FFTW for a while now at Griffith University, Australia for Signal processing and I constantly have students asking me how to implement the most basic FFT and IFFT in C. And I thought since Wikipedia is usually their first point of call when researching, could it also point them in the right direction for implementation. Something like: C Programming: The reconstruction of the Fast Fourier transform of a real signal using FFTW libraries for the most basic implementation, or something similar.
—Roger Chappel ( talk) 19:48, 17 June 2011 (UTC)
Hi all, I noticed that, currently, reference 5 (which is the source for how "[FFTW] is also licensed commercially (for a cost of up to $12,500) by MIT") as-linked ( http://technology.mit.edu/technologies/15054_fastest-fourier-transform-in-the-west-fftw-version-3-3-x-fftw-v-3-3-x) redirects to a general landing page. Should we update the source for that information to the MIT TLO's current page on FFTW? The latest link is: https://tlo.mit.edu/technologies/fftw-fastest-fourier-transform-west.
Alternatively, we could add a link to an archived version of the old web page. (I'm new to Wikipedia, so I'm not sure if one option is preferred over another.) Here is the Internet Archive link: https://web.archive.org/web/20170128024924/http://technology.mit.edu/technologies/15054_fastest-fourier-transform-in-the-west-fftw-version-3-3-x-fftw-v-3-3-x. This is the latest archived copy of the webpage that doesn't redirect the same way it does now.
Any guidance? Thanks in advance!
— QB2k ( talk) 11:54, 3 February 2023 (UTC)