>I don't see any reason to assume it's an unprovable axiom-of-choice
>type of thing, although the proof seems to be fairly difficult and has
>resisted repeated attempts so far. There are already proofs that
>Omega(N log N) operations are required under certain restrictions on
>the type of algorithms [e.g. there is a nice proof by Morgenstern in
>1978 that Omega(N log N) additions are required if you restrict
>yourself to algorithms with bounded multiplicative constants ...
>unfortunately, there are many interesting algorithms that do not have
>the property of bounded constants, including the ones with the
>currently lowest known flop counts (see fftw.org/newsplit.pdf)].
Interesting. I wasn't particularly thinking it was unprovable, just
curious whether or not it can be proven unprovable. Rumor has it my
advanced calculus professor (oh so long ago) ended up with a known
unprovable problem for his dissertation (though he did not know this at the
time), which always makes me think about these things. He was, btw, a bit
odd, and the rumor claimed it was a result of his dissertation stress.
Mark
Reply by Steven G. Johnson●May 9, 20082008-05-09
On May 9, 12:23 am, "Steven G. Johnson" <stev...@alum.mit.edu> wrote:
> the type of algorithms [e.g. there is a nice proof by Morgenstern in
> 1978 that Omega(N log N) additions are required if you restrict
On May 7, 12:05 pm, "markt" <tak...@pericle.com> wrote:
> >And even optimality in terms of flop counts is not proven; no one
> >knows tight lower bounds. There isn't even any proof that you can't
> >do better than O(N log N) for an FFT (although no counterexamples are
> >known).
>
> Though I suppose the fact that O(N log N) is called an estimation implies
> this statement, I did not know this explicitly. Particularly the second
> statement. Learn something new every day. Do you suppose it is an
> unprovable problem?
I wouldn't say that the O(N log N) asymptotic analysis implies this
statement. Having an estimate or an asymptotic bound doesn't mean
that you don't know more precise things as well. Exact arithmetic
counts are certainly known for the existing algorithms; it's just not
known whether better counts are possible.
I don't see any reason to assume it's an unprovable axiom-of-choice
type of thing, although the proof seems to be fairly difficult and has
resisted repeated attempts so far. There are already proofs that
Omega(N log N) operations are required under certain restrictions on
the type of algorithms [e.g. there is a nice proof by Morgenstern in
1978 that Omega(N log N) additions are required if you restrict
yourself to algorithms with bounded multiplicative constants ...
unfortunately, there are many interesting algorithms that do not have
the property of bounded constants, including the ones with the
currently lowest known flop counts (see fftw.org/newsplit.pdf)].
Steven
Reply by markt●May 7, 20082008-05-07
>If you look at the definition of asymptotic (O) notation, you'll see
>that there's no need to say whether "infinity" is prime or composite.
I think he was intentionally being funny. ;)
>In practice, the O(N log N) prime-size algorithms already have clear
>advantage for N > 100. In principle, you usually have enough freedom
>to choose your transform to be a composite size, but many people
>apparently find it useful to not have to worry about resizing their
>data, without being afraid that if they are unlucky the FFT will be
>thousands of times slower (as opposed to just a factor of 10).
I played around with FFTW quite a bit a few years ago (you and I traded
emails about my efforts, and my company actually bought a license at the
time) and I can say that this is at the very least, empirically true.
>And even optimality in terms of flop counts is not proven; no one
>knows tight lower bounds. There isn't even any proof that you can't
>do better than O(N log N) for an FFT (although no counterexamples are
>known).
Though I suppose the fact that O(N log N) is called an estimation implies
this statement, I did not know this explicitly. Particularly the second
statement. Learn something new every day. Do you suppose it is an
unprovable problem?
>Yes, especially for large N I'm not aware of any implementation of the
>minimal-known-flop FFT algorithm(s) that is competitive in practice
>with highly optimized implementations. You just have too many other
>things to worry about that are more important than arithmetic these
>days. On the other hand, to be fair, I doubt that the highly
>optimized implementations sacrifice more than 10-15% in the flop count
>compared to the lowest known flop counts.
Too bad. It's not difficult for other math functions, such as a complex
multiply or magnitude function (which is what FFTW's SIMD code does), which
are then ordered in memory for fast access and a consistently full
pipeline. Once you have to stride or do a corner turn, the effort just
ain't worth it, not for the 10% at least.
Mark
Reply by Jerry Avins●May 7, 20082008-05-07
glen herrmannsfeldt wrote:
> Steven G. Johnson wrote:
> (snip)
>
>> Short answer: FFTW uses the prime-factor algorithm for small sizes (<=
>> 16) within its codelets at the leaves of its recursion. Larger
>> composite sizes are broken down into smaller sizes using mixed-radix
>> Cooley-Tukey. It is O(N log N) for all N.
>
> An interesting statement. O() notation gives the order as
> N goes to infinity, and it may or may not be of any use
> for small N. Now, is infinity prime or composite?
Composite, of course. Primes get scarcer as numbers increase. By the
time infinity is reached, they are vanishingly scarce. Aint logic wunnerful?
Jerry
--
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������
Reply by Philip Martel●May 6, 20082008-05-06
"glen herrmannsfeldt" <gah@ugcs.caltech.edu> wrote in message
news:8JCdncXYrN0Anr3VnZ2dnUVZ_oimnZ2d@comcast.com...
> Steven G. Johnson wrote:
> (snip)
>
>> Short answer: FFTW uses the prime-factor algorithm for small sizes (<=
>> 16) within its codelets at the leaves of its recursion. Larger
>> composite sizes are broken down into smaller sizes using mixed-radix
>> Cooley-Tukey. It is O(N log N) for all N.
>
> An interesting statement. O() notation gives the order as
> N goes to infinity, and it may or may not be of any use
> for small N. Now, is infinity prime or composite?
Yes.
>
> -- glen
>
Reply by Steven G. Johnson●May 6, 20082008-05-06
On May 5, 12:02 pm, "markt" <tak...@pericle.com> wrote:
> Yeah, as you note, even "optimal" in terms of the least amount of FLOPS is
> not necessarily "optimal" in terms of speed.
And even optimality in terms of flop counts is not proven; no one
knows tight lower bounds. There isn't even any proof that you can't
do better than O(N log N) for an FFT (although no counterexamples are
known).
> without reference to some criteria. Set your minimum FLOP count algorithm
> up in such a way that your next instruction is always waiting for
> completion of the current instruction (a pipeline stall) and you'll find it
> may not work very well compared to another algorithm with more required
> FLOPS, but a better overall flow.
Yes, especially for large N I'm not aware of any implementation of the
minimal-known-flop FFT algorithm(s) that is competitive in practice
with highly optimized implementations. You just have too many other
things to worry about that are more important than arithmetic these
days. On the other hand, to be fair, I doubt that the highly
optimized implementations sacrifice more than 10-15% in the flop count
compared to the lowest known flop counts.
On the other hand, for small hardcoded transforms of sizes < 100 or
so, we have usually found that we do best with the algorithms that
come close to the minimum known flop counts. (This relies on the
ability to find a good schedule for the code, of course, but we have a
generic algorithm for this that seems to work well.)
(Sometimes people talk about a "crossover point" at which the O(N log
N) algorithms beat the naive O(N^2) algorithm, but in my experience
this is mostly about overheads of implementations. For small N you
really want to hard-code everything to avoid the overhead, and in that
case, we've usually found that a hard-coded O(N log N) algorithm wins
over the O(N^2) algorithm for all composite N starting with N=4.)
Steven
Reply by Steven G. Johnson●May 6, 20082008-05-06
On May 6, 3:12 am, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> > Cooley-Tukey. It is O(N log N) for all N.
>
> An interesting statement. O() notation gives the order as
> N goes to infinity, and it may or may not be of any use
> for small N. Now, is infinity prime or composite?
If you look at the definition of asymptotic (O) notation, you'll see
that there's no need to say whether "infinity" is prime or composite.
In practice, the O(N log N) prime-size algorithms already have clear
advantage for N > 100. In principle, you usually have enough freedom
to choose your transform to be a composite size, but many people
apparently find it useful to not have to worry about resizing their
data, without being afraid that if they are unlucky the FFT will be
thousands of times slower (as opposed to just a factor of 10).
Steven
Reply by markt●May 6, 20082008-05-06
>An interesting statement. O() notation gives the order as
>N goes to infinity, and it may or may not be of any use
>for small N. Now, is infinity prime or composite?
I was reading this thinking "yeah, it's probably not very good for small
N" then I got to the last bit and had to laugh. :)
Mark
Reply by Jerry Avins●May 6, 20082008-05-06
glen herrmannsfeldt wrote:
> ... Now, is infinity prime or composite?
:-) !
Jerry
--
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������