Timeline for Complexity of computing the discrete Fourier transform?
Current License: CC BY-SA 3.0
29 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:32 | history | edited | CommunityBot |
replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/
|
|
| Sep 24, 2011 at 16:49 | comment | added | Jeffε | @Klim: Sure; that's the "number theoretic transform". | |
| Sep 22, 2011 at 9:04 | comment | added | Klim | Do you know that there are exists different versions of FFT not only over C which works over finite fields and other rings? For many applications this versions are more useful. | |
| Sep 15, 2011 at 12:16 | vote | accept | Jeffε | ||
| Sep 14, 2011 at 21:58 | comment | added | Ken Clarkson | Possibly, Gauss-Runge-König-Yates-Stumpf-Danielson-Lánczos-Good-Cooley-Tukey; Cooley and Tukey describe their algorithm as an application of an algorithmic approach due to Good, although "derived and presented in a rather different form". | |
| Sep 13, 2011 at 21:12 | answer | added | Markus Bläser | timeline score: 9 | |
| Sep 13, 2011 at 17:53 | history | edited | Kaveh |
edited tags
|
|
| Sep 13, 2011 at 17:51 | comment | added | Kaveh | This is the kind of question that should have been studied in computable analysis and complexity of real functions, but I couldn't find them in the standard references (Ko's and Weihrauch's books). | |
| Sep 13, 2011 at 16:03 | comment | added | Aaron Sterling | @Jeff: The operation is linear wrt the presentation. Type II effectivity is an attempt to avoid the problems in the real-RAM model, where, eg, one can determine whether two reals are equal in one time step. The function in the paper is only continuous in the sense that the FT function really takes as input a naming function, which, when given a precision parameter, outputs a name of a real to that precision. I'm not saying I know how to map TTE to the integer-RAM model, but I wouldn't be surprised if that has been considered somewhere. I'll take a look. | |
| Sep 13, 2011 at 15:19 | answer | added | Timothy Chow | timeline score: 8 | |
| Sep 13, 2011 at 14:30 | comment | added | Chandra Chekuri | Jeff, Dasgupta etal book has an exercise discussing the modular-arithmetic version. | |
| Sep 13, 2011 at 12:10 | comment | added | Jeffε | v s: No, my actual question is how to minimize the number of operations on the standard integer RAM. (I'm well aware that this is not the standard question, which is asked and answered in standard textbooks.) It's perfectly fine to expand to (say) $2^b$ bit of precision in the intermediate values, if that's what's required, as long as you remember to analyze the resulting arithmetic operations correctly. | |
| Sep 13, 2011 at 12:08 | comment | added | Jeffε | Aaron: The paper you mention describes a non-standard model of computation for integrable functions and establishes a linear-time(!) algorithm for the CONTINUOUS Fourier transform in that model. It's completely unclear how to map that result onto the integer-RAM complexity of the discrete Fourier transform. | |
| Sep 13, 2011 at 12:04 | comment | added | Jeffε | Chandra: I agree that the complex number version is more familiar (despite the glazed eyes that both Suresh and I see). My question is why standard references don't include another half page explaining and motivating the modular-arithmetic version. | |
| Sep 13, 2011 at 10:52 | comment | added | Suresh Venkat | Markus, Aaron: convert to answers ? | |
| Sep 13, 2011 at 10:52 | comment | added | Suresh Venkat | in my class, I find that complex numbers and finite fields draw the same kind of glazed look :) | |
| Sep 12, 2011 at 21:50 | history | tweeted | twitter.com/#!/StackCSTheory/status/113369029695111169 | ||
| Sep 12, 2011 at 20:51 | comment | added | Chandra Chekuri | Jeff, having just taught FFT in graduate algorithms that you regularly teach, let me say that one reason to use complex numbers is that most students are familiar with it. Bringing up finite fields etc takes time. The issue of computing an exact convolution for integer sequences came up and I simply pointed them to the wikipedia article. For signal processing I guess floating point arithmetic is ok and it appears that the numerical properties of FFT have been analyzed though I do not know the details. | |
| Sep 12, 2011 at 19:29 | comment | added | Markus Bläser | Have a look at Method A in the paper of Schönhage and Strassen on integer multiplication. It uses complex Fourier transforms with bounded precision. I think, it is also described in Knuth Vol. 2. | |
| Sep 12, 2011 at 17:48 | comment | added | Aaron Sterling | Computable analysis has considered this, and related questions. This paper produces a complexity bound for computation of the Fourier transform within the framework of Weirauch's Type II effectivity. The bound is that it is linear in the presentation of the (infinite, real-valued) input. Both the input and the output are defined wrt precision parameters in this system, so there may be a way to translate this into the RAM model. | |
| Sep 12, 2011 at 17:39 | comment | added | v s | Just an example: Increasing any additional signal strength is a real 'big' deal in communication systems. If for instance, your algorithm provides $1$ additional bit of accuracy for instance over existing results, then if I understand correctly, you have increased signal quality by roughly a factor of $2$ and hence you have doubled(atleast increased by constant multiple since you have to consider variables like beam patterns etc) cell phone coverage, probably doubled (atleast increased by a constant multiple) revenue for service providers or lowered error correction complexity in half. | |
| Sep 12, 2011 at 17:29 | comment | added | v s | Actually this is a good question each additional bit of precision adds $3dB$ to the signal strength (multiply by $2$). So I think the question will be most useful if the intermediary word sizes can be expanded! | |
| Sep 12, 2011 at 17:27 | comment | added | v s | Thankyou for the clarification. A straightforward approach that is actually used is represent each word to the necessary bits of precision (this is the best that can be done) and compute by using FFT algorithm. A variant that is probably useful in efficient usage of word spaces in processors used in signal processing systems is the following. Supposing if the intermediary word sizes can be expanded to $kb$ bits and the final representation is $b$ bits, what is the complexity? This would probably help in designing or modifying existing instrution sets in fixed/floating point processors. | |
| Sep 12, 2011 at 17:17 | comment | added | Suresh Venkat | I think that's his point: in theory you don't have to worry about $b$, but in any ACTUAL implementation you DO have to worry about it and the error that might be incurred. | |
| Sep 12, 2011 at 17:13 | comment | added | v s | Is the variable $b$ really needed for a proper definition? If I understand correctly, the addition and multiplication operation are on words of infinite precision and isn't it probably sufficient to place different dft coefficients on different words for right definition? And infact, the actual question on complexity is to minimize the number of real or complex multiplications and additions. | |
| Sep 12, 2011 at 16:58 | comment | added | Suresh Venkat | Totally awesome question. | |
| Sep 12, 2011 at 15:37 | comment | added | Mohammad Al-Turkistany | +1 An eye opener. I always blindly accepted the $O(n \log n)$ time complexity for DFT. | |
| Sep 12, 2011 at 14:41 | comment | added | Tyson Williams | I think your claim that the algorithm is incorrectly named detracts from the good question that follows. | |
| Sep 12, 2011 at 14:33 | history | asked | Jeffε | CC BY-SA 3.0 |