Lambda the Ultimate

The following paper is a good reference regarding the FFT complexity:

@article{Heideman:1986,
    author = "M.T.Heideman and C.S.Burrus",
    title = "On the number of multiplications
             necessary to compute a length-$2^n$ {DFT}",
    journal = {{IEEE} Trans. ASSP},
    volume = "ASSP-34",
    number = "1",
    month = {February}, 
    pages = "91--95",
    year = "1986"
    }

The paper proves that the minimum number of floating-point (not
rational!) multiplications needed to compute 2^n complex-valued DFT is
2^{n+2} - 2n^2 - 2n -4. For real-valued inputs, only half that many
are needed.

For split-radix DFT, the number of FP multiplication is (n-3)*2^n + 4.

The algorithm with the minimum number of multiplications is not
practical beyond n = 4 (because the number of additions
sky-rockets). But for n = 4 and below, the split-radix is the minimum
multiplication DFT algorithm. For n=5, the algorithm in the Heideman and
Burrus paper has 64 FP multiplications and 504 additions (whereas
split-radix has 68 FP multiplications and 388 additions). For n>5,
only lower boundaries were proven but no algorithm was actually
written (so the number of additions is not known, but it is certainly
very large).

Thanks for the answers; couldn't find your article yet but stumbled on this one: S.G. Johnson, M. Frigo, A modified split-radix FFT with reduced arithmetic complexity. Hmpf, their tables only list general flop's.

Hmm, when counting bit operations there is a "philosophical" argument that you can get rid of all the multiplications by recursive Karatsuba but I must admit that this is probably impractical and stretching the truth, well, a bit... ;-)

I just posted an updated version of the paper that gives formulas for the separate counts of real additions and multiplies (no table, though). (See Eqs. 4-5 and 13.)

(Since the savings are purely in the number of real multiplications, as described in the paper, these are pretty easy to figure out yourself if you know the counts for standard split-radix assuming general complex multiplies are done in 4/2 mults/adds.)

Thanks for your comments and compliments on your paper. I reread some stuff on FFT and NTTs and, ah well, decided that it would take too much of my time to grasp it really (I personally only looked at the NTT to find minimal terms for factorization, but went for Karatsuba for now, so irrational FFT I don't really get); same goes for about 50% of your paper, I grasp your line of reasoning but don't have time to go into the technicalities of it :(

Anyway, I had three, somewhat rambling, thoughts you (others) might find of interest. The last one is a question which rambles the least and which I am interested in.

First, by wikipedia, Winograd, who else, proved that the DFT can be computed with O(n) multiplications at the expense of too many additions. Wikipedia does not link to an argument. (prime length?)

Second, [decided to kill this not-even half-baked thought]

Third thought, which is the interesting thought for LtU readers -I guess- is: there is some "mechanical" feeling to the combinatorial/algorithmic argument. You state a function which unfolds to a given term graph and then you start searching for sharing on the graph, or rewrite rules which maximize sharing, after which you look for another recurrence relation which implies another function the graph could be folded to (and then you hope that you can apply the master theorem). This seems aimenable to automation so my question is: is there any software (more general than for FFT use) which helps automating these mundane combinatorial tasks?

[Hmm, actually, I guess I am going to try this. Hey, if I am no Winograd maybe my computer can become one ;-) ]

there is some "mechanical" feeling to the combinatorial/algorithmic argument. You state a function which unfolds to a given term graph and then you start searching for sharing on the graph, or rewrite rules which maximize sharing, after which you look for another recurrence relation which implies another function the graph could be folded to (and then you hope that you can apply the master theorem). This seems amenable to automation so my question is: is there any software (more general than for FFT use) which helps automating these mundane combinatorial tasks?

That has been done in the SPIRAL project, which ``entirely autonomously, generates platform-tuned implementations of signal processing transform such as the discrete Fourier transform, discrete cosine transform, and many others.''

SPIRAL can also search for signal processing algorithms with the minimal operation count (btw, on modern super-scalar CPU the code with the minimal (FP) operations count is not necessarily the fastest one).