From: nmm1@cus.cam.ac.uk (Nick Maclaren)
Newsgroups: sci.math.num-analysis
Subject: Re: New FFT-methods??
Date: 9 Oct 1998 08:53:32 GMT

In article <6vj2vk$cll$1@client3.news.psi.net>,
Dann Corbit <dcorbit@solutionsiq.com> wrote:
>Look at the FFTW page.  They have a feature that learns about efficient ways
>to solve, and saves the learning data to disk.
>
>Carsten Aulbert wrote in message ...
>
>Are there any known papers/links or whatsoever, concerning new ways for
>using FFT with a priory information?

I don't that that will help.  FFTW seems to be based on a collection
of dubious hacks to speed up some rather pedestrian FFT algorithms.
I.e. its scripts try several different forms of code and use the
one that seems best handled by the compiler.


Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.
Email:  nmm1@cam.ac.uk
Tel.:  +44 1223 334761    Fax:  +44 1223 334679
==============================================================================

From: stevenj@alum.mit.edu (Steven G. Johnson)
Newsgroups: sci.math.num-analysis
Subject: Re: New FFT-methods??
Date: Wed, 14 Oct 1998 15:20:46 -0400

William Hughes <whughes@atlsci.com> wrote:
> I use good  techniques, you rely on heuristics,
> he uses dubious hacks.
>
> The FFTW approach seems to me an excellent one.

William,

Thanks for your support.  =)  I've been following this thread with some
interest.

> However, my understanding is that the basic algorithm
> behind FFTW is a straightforward recursive FFT.

More or less.  The recursive part of FFTW uses ordinary mixed-radix Cooley
Tukey, with various implementation tricks (whether they are "dubious" or
not is a subjective matter).

As the base cases of the recursion, FFTW uses hard-coded transforms of
small sizes which were automatically generated.  These transforms use a
variety of FFT algorithms, including Cooley-Tukey, Prime-Factor,
split-radix (a C-T variant), and Rader's algorithm for prime sizes.  [None
of these methods are really "new," however.]  Our generator also performs
many algebraic simplifications, common-subexpression elimination (done in
a somewhat unusual way), etcetera, and in some sense derives "new"
algorithms.  For example, the generator automatically derives real-complex
transforms from the complex-complex ones by applying the symmetries of the
input and output and then simplifying.  (These automatically-derived
real-complex transforms match the lowest published operation counts in the
literature.)  The generator also addresses another problem, namely
scheduling of the computation to minimize variable lifetimes.  It also
structures the code into nested blocks and uses other tricks in an attempt
to help the compiler to optimize fully.

FFTW 2.0 also applies O(N log N) methods to prime factors of arbitrary
size (using a general implementation of Rader's method).

All of the elements of FFTW, with the possible exception of the
automatically-derived real-complex transforms, have appeared previously in
some form or other (although not always in the context of FFTs).  The
novelty, if it can be so called, was in putting them all together.

The closest thing to truly new FFT algorithms that I've seen in the
literature of the past few years have been Burrus et al.'s QFT algorithm
[ICASSP '94] and H. Murakami's generalization of the Bruun algorithm to
any composite even size [ICASSP '96, v. 3, p. 1311].

In any case, I don't think any of this answers the original poster's question:

>Are there any known papers/links or whatsoever, concerning new ways for
>using FFT with a [priori] information?

It sounds like he was asking about new ways to utilize the FFT (e.g. new
signal processing tricks or some such thing), although he is not entirely
clear.

Cordially,
Steven G. Johnson