FFTs Using AltiVec on Linux and Mac OS X

GregAllen writes "After searching for a good open-source AltiVec implementation of the Fast Fourier Transform (FFT), I have put together the AltiVec FFT page. It has all of the source, some benchmarks, and runs on Mac OS X or LinuxPPC. I even compared it to the venerable (but scalar) FFTW."

Comments

Re:What's a FFT

[ndevice]

an fft is a fast fourier transform. It is commonly used to transform data from the time domain to the frequency domain.

What this means is that is if you have a time-varying signal like audio for example, you can run an fft on it and get a frequency analysis on the sound. i.e. from the sound in a waveform format, after an fft, you can pick out which are the dominant frequencies, and what the relationship between frequencies are.

Although the fft is strictly not necessary because it is, after all, just a transform, it turns out that many media compression techniques use them because humans aren't as discriminating in the frequency domain so if you do lossy compression in the frequency domain, we won't notice/mind as much.

fyi, you do an fft any time you view a .jpg, or listen to an .mp3, or watch a dvd, etc. Lots of uses for them, and that doesn't even get into the engineering/scientific uses...

Re:What's a FFT

[nathanh]

fyi, you do an fft any time you view a .jpg, or listen to an .mp3, or watch a dvd, etc.

You use a FFT anytime you ENCODE a .jpg, or an .mp3, or a DVD. When you view or listen or watch you are using an Inverse FFT.

And to be very specific, I think all your examples use DCT (Discrete Cosine Transform) and not FFT. JPEG definitely does. Very good overview here

Linux is faster than macosx

[dcstimm]

I use Gentoo Linux on my ibook and since I can compile all my code for my g3 cpu, I notice a huge speed increase between linux and macosx. Since My cpu doesnt take advantage of altivec apps that are compiled for altivec run slow on a g3. Apps that are directly compiled for a g3 will run 20-30% faster. Of course apple could make Macosx faster for g3 people if they recompiled the OS with out altivec support, but they cant do that. With My g4 system I dont see a huge speed difference in linux unless I use more aggressive gcc optimizations. Anyway, Linux on a g3 will always run faster than macosx on a g3.

Re:Not really for OSX unless you're porting to lin

[GregAllen]

It's important to point out that the "traditional way" to store complex numbers (and do an FFT) is with interleaved data. If your application uses interleaved data (and most do), then this library is for you. Split data is being used more because of the obvious performance improvements, but you have to change your code (and your mindset) to use it.

I've updated it to say: as much as twice as fast as vBigDSP on split data (but about the same on interleaved data).

I'd like to get an open-source split-data version to add to the site, so Linux users get good split-data FFTs, too.

Further senseless nit-picking

[melquiades]

Although people often use the terms interchangably, strictly speaking the Fourier Transform is the mathematical operation (like "sort") and the FFT is a particular way of computing it (like "quicksort").

The FFT is a particularly FAST algorithm for computing Fourier Transforms, with O(n log n) instead of O(n^2) for the naive algorithm -- thus the name. I believe that there is a comparably fast and very similar algorithm for computing the DCT, which doesn't really have a separate name.

You use a FFT anytime you ENCODE a .jpg, or an .mp3, or a DVD. When you view or listen or watch you are using an Inverse FFT.

True, though an inverse Fourier tranform is simply the Fourier transform run through a complex complement and multiplication by a constant. The FFT and the IFFT are essentially the same algorithm.

And to be very specific, I think all your examples use DCT (Discrete Cosine Transform) and not FFT.

Right ... though again, the DCT and the FT are essentially the same operation -- the DCT is just the real part of the FT (the FT is complex).

Re:Further senseless nit-picking

[plastik55]

Right ... though again, the DCT and the FT are essentially the same operation -- the DCT is just the real part of the FT (the FT is complex).

No -- the DCT spaces its components at half-wavenumbers while the FT has components spaced at integer wavenumbers. So only every other DCT components would be equal to the real part of an FT component. (that isn't strictly true, either, since most DCTs have a half-sample offset compared to FT)

Interestingly enough it wasn't until the '90s that a "fast" or O(n log n) algorithm for calculating the DCT was found--this is well after it had become widely used in compression.

FFTW 3.0 beta has been released

[Dominic_Mazzoni]

Well, FFTW 3.0 beta has been released, and it includes Altivec support. I would be very surprised if this new FFTW wasn't extremely competitive with all the benchmarks presented on this page, if not better.

Anyone want to add it to the benchmark?