VelEng FFT

G4 Velocity Engine implementation of fast Fourier transform (FFT) and associated convolution/correlation routines. Though arbitrary signal lengths (i.e. all powers of 2) are handled, our design emphasis is on very long signals (length N >= 2^16 and on into the millions), for which cache considerations are paramount. The core of the library is a particular variant of full-complex FFT that for signal length N = 2^10 executes at 1.15 giga ops (500 MHz G4). This cache-friendly, core FFT plays a dominant role in the long-signal cases such as two-dimensional FFT and convolution. More important perhaps than the core performance benchmark is the manner in which one can sift through the myriad prevailing (and new) FFT frameworks, to arrive at a suitable such framework for the Velocity Engine. Requirements: G4 Keywords: Velocity Engine, Altivec, FFT, Fast Fourier Transform