Hello, I have a small query regarding the discrete Fourier transforms. If I understand correctly, then what we do is convert a polynomial to its point value representation, with n points for a polynomial that goes up to the power of n-1. But why must we evaluate it at the nth roots of unity? Wouldn't any other n points uniquely identify this polynomial AND be much simpler?
+2
A:
Wouldn't any other n points uniquely identify this polynomial AND be much simpler?
No to both. 1) There's no guarantee that n arbitrary points would work and 2) it wouldn't be simpler. Turn the question around: why do you object to the roots of unity?
MarkusQ
2009-04-13 17:11:43
This is down right and flat out NO (I wish I could scream). assume that f,g are distinct degree n-1 polynomials, and are the same on n points, then their difference F is 0 on n points. Huray ! you just found a degree n-1 polynomial with n roots.
David Lehavi
2009-04-14 13:58:09
Answering your remarks on my post: No other points would work, but not for the reason he is alluding to. I find your answer misleading because you say more or less "it may work but why bother" (it won't). I don't know what other question you talk about, and I hate decaf.
David Lehavi
2009-04-14 19:06:20
@David Lehavi -- You could make it work for other (carefully chosen) sets of points (think either of pre-and-post change of representation or using an alternate set of ortho-normal basis functions) but _in_general_ it would not work.
MarkusQ
2009-04-14 23:48:36
@MarkusQ -- To get what FFT could offer you need a finite subgroup of the complex numbers. The only such subgroups are the sets of roots of unity of a give order.
David Lehavi
2009-04-15 14:26:23
@David Lehavi -- Scale and rotate by some arbitrary factor and angle about the origin and you'll get a set that 1) can be used (albeit less conveniently) and 2) aren't roots of unity. It's messy and stupid, but the whole point of FT is that it survives such transformations.
MarkusQ
2009-04-15 15:06:52
@David Lehavi -- Note also that the question is about DFT, not FFT.
MarkusQ
2009-04-15 15:08:26
@MarkusQ -- Call the set of roots of unity of degree n U_n. The set you suggest is aU_n, which is a U_n torsor, so you will get a transform. You will however need to refactor for the size of a (or loose the transform = inverse property), and loose wave->monomial if the argument is not 0.
David Lehavi
2009-04-15 17:30:18
+1
A:
The chief applicative reasons are
- Waves become monomials.
- Product on the time space is convolution on the phase space and vice versa (so you can multiply two polynomials of degree n in O(n log n) ).
- Derivative on the time space is product by x on the phase space and vice versa.
You'd have none of these with random points - intuitively speaking, because they do not form a group. There are many more theoretical reasons (and also a few more applicative ones)
David Lehavi
2009-04-14 14:06:27
@Dave Lehavi -- What's up with this? You post an answer which, while more technically worded, is in substantial agreement with mine, mod me down, and then go and mod me down on another unrelated question? Have you considered switching to decaf?
MarkusQ
2009-04-14 14:23:48
A:
No, not really. It's got nothing to do with polynomials. It's about decomposing a vector (the initial sequence of numbers) into a different basis. It's just that this basis has a series of very useful properties:
(1) It's orthogonal -- the vectors don't mix, and determining the transformation back to the original basis is exceedingly simple.
(2) The Fourier basis vectors are eigenvectors of the shift (or circular shift, for the discrete case) operation -- a Fourier basis function, after shifting the vector indices, is still the same function (times a number). That's what makes convolutions and the solution of a large class of differential equations very simple in Fourier space.
(3) And finally, the entries are roots of unity -- this gives raise to the FFT, one of the most elegant algorithms ever discovered, reducing the N^2 operations required for a change of basis to N log N.