Fast Convolution: does it matter whether I normalize to block length (N) in the FFT versus in the iFFT?

James Van Buskirk wrote:
> <stevenj@alum.mit.edu> wrote in message
> news:1125943989.790065.231790@o13g2000cwo.googlegroups.com...
>
> > Of course.  This is why, for computational purposes, I've always felt
> > that the best normalization for FFTs is no normalization at all---any
> > overall scale factor can, in most practical applications, be absorbed
> > elsewhere at little or no cost (e.g. in the convolution kernel).
>
> But continuing along these lines is dangerous because it can lead
> to computing convolutions in fewer operations than would be the case
> if the FFT and its inverse (or transpose) were used, as in
>
> http://home.comcast.net/~kmbtib/conv2c.f90
>
> and this would violate the orthodoxy contraints of the current
> forum...

I don't know what you mean by comp.dsp being "orthodox", but
as a general rule, an improvement of a general algorithm takes
advantage of some particular property of some subset of the
measurements, and the improvement comes at the expense of
general usefulness of the algorithm.

The radix-2 FFT is probably the fastest FFT what run-time is
concerned. There are prime-factor FFTs around that are more
general, but probably not quite as fast as the radix-2 version.
Does that mean that the radix-2 FFT is a better tool than the
general FFT? It depends on the cost of restricting the data
to be of length 2^N for some integer N. Some times that
restriction is more expensive, in some way other than run-time,
than using a general length FFT. Are people who prefer the
general FFT "orthodox" because they use a tool with more
flexibility?

You tell me.

Rune

Rune Allnor wrote:
> The radix-2 FFT is probably the fastest FFT [where] run-time is
> concerned.

Um, this is not even close to true, in my experience.   Unless by
"radix-2" you just mean "any FFT for 2^n", which is not the standard
terminology.

> There are prime-factor FFTs around that are more
> general, but probably not quite as fast as the radix-2 version.

I think you mean mixed-radix FFTs (which don't require prime factors,
by the way).  The Prime-Factor Algorithm is *less* general, because it
requires its factors to be relatively prime (e.g. it doesn't work for
2^n.)

Keeping your data within factors of 2/3/5 is generally faster, given a
good mixed-radix code, than restricting yourself to 2^n, if the latter
would require you to significantly increase the length of your array
beyond what you need (e.g. you may need to almost double the length).
The situation is even more dramatic in 2d and 3d, where adjacent
power-of-two sizes differ by factors of 4 and 8, respectively.

(Note that the comparison is muddied by the fact that there is a cycle:
most people are ingrained to use 2^n, so 2^n FFTs get most of the
optimization effort, so most people use 2^n, so...)

Steven

stevenj@alum.mit.edu wrote:
> Rune Allnor wrote:
> > The radix-2 FFT is probably the fastest FFT [where] run-time is
> > concerned.
>
> Um, this is not even close to true, in my experience.   Unless by
> "radix-2" you just mean "any FFT for 2^n", which is not the standard
> terminology.
>
> > There are prime-factor FFTs around that are more
> > general, but probably not quite as fast as the radix-2 version.
>
> I think you mean mixed-radix FFTs (which don't require prime factors,
> by the way).  The Prime-Factor Algorithm is *less* general, because it
> requires its factors to be relatively prime (e.g. it doesn't work for
> 2^n.)
>
> Keeping your data within factors of 2/3/5 is generally faster, given a
> good mixed-radix code, than restricting yourself to 2^n, if the latter
> would require you to significantly increase the length of your array
> beyond what you need (e.g. you may need to almost double the length).
> The situation is even more dramatic in 2d and 3d, where adjacent
> power-of-two sizes differ by factors of 4 and 8, respectively.
>
> (Note that the comparison is muddied by the fact that there is a cycle:
> most people are ingrained to use 2^n, so 2^n FFTs get most of the
> optimization effort, so most people use 2^n, so...)
>
> Steven

OK, I got the details wrong.

Still, most users of an FFT package would not be concerned about
the possibility of the FFT going a few millisecond faster if the
FFT lengths comprised certain factors. Only the really demanding
users would care, and I don't there are very many such users. 

Rune

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message
news:1126089385.367928.304160@g14g2000cwa.googlegroups.com...

> I don't know what you mean by comp.dsp being "orthodox"

Well, start off with the fact that in a thread about fast
convolution, your post refers almost exclusively to radix-
2 FFTs.

-- 
write(*,*) transfer((/17.392111325966148d0,6.5794487871554595D-85, &
6.0134700243160014d-154/),(/'x'/)); end

James Van Buskirk wrote:
> "Rune Allnor" <allnor@tele.ntnu.no> wrote in message
> news:1126089385.367928.304160@g14g2000cwa.googlegroups.com...
>
> > I don't know what you mean by comp.dsp being "orthodox"
>
> Well, start off with the fact that in a thread about fast
> convolution, your post refers almost exclusively to radix-
> 2 FFTs.

Hmmm.... OK, I could agree it might be due to orthodoxy.
But then, Occam's Razor is a very good principle in
explanations and teaching: Don't use a more complex example
than necessary, to communicate the essence of whatever
question is under debate.

Most of the time the radix-2 FFT is discussed because that's
what people have heard of, and that's what people read about
in the textbooks. Most of the time, the elaborate variations
obfuscate the issue rather than clarify.

And some times those elaborate details are what is crucial
to understand, to get on. 

Rune