added basic fft to my dataframes

[Mirko Vukovic]

In preparation for experiments that start tomorrow, I added today real-array fft and power spectrum capabilities to my dataframe code.  It uses GSLL's fft functions (search for file fft.lisp).  The classes, generic functions, and methods are still a bit rough, and will be refined.

You can read more about it: https://github.com/mirkov/data-table/blob/master/user/example1/README.org

That same directory contains examples-w-fft.lisp that shows the code usage.  I annotated the code.

The png files show sunspot data and two power spectra.

The example shows how I create one data-table with raw data, and then another one with slightly massaged data.  I do the fft on the latter one.

The example also shows that the current syntax is `functional' vs `declarative'. I explicitly  build the second data table, instead of declaring its dependency on the first table.  I think that the latter approach is preferable from a user's point of view.  But I will refrain from trying to design and implement this declarative approach.  I need more real-world experience before trying to do this.

I may add windowing capability to the fft code later on.

Mirko

[Paul Khuong]

On 2013-01-13, at 9:53 PM, Mirko Vukovic <mirko....@gmail.com> wrote:

> In preparation for experiments that start tomorrow, I added today
> real-array fft and power spectrum capabilities to my dataframe code. It
> uses GSLL's fft functions (search for file fft.lisp).

[...]

> I may add windowing capability to the fft code later on.

It works, and that's what matters, but...

Bordeaux-FFT has windowing code and fairly decent performance for complex, power-of-two, FFT on SBCL/x86-64 (using complex arithmetic enables SBCL to emit SIMD FP code).

Napa-FFT3 (https://github.com/pkhuong/Napa-FFT3) has basically the same windowing code, and real-only FFT, but still only does power of two FFTs (smaller FFTs basically need padding, unless a brave soul wants to implement more radices). In early experiments ~one year ago, Napa-FFT3 was on on par with FFTW 3.3, except for small L2 cache-sized transforms, for which FFTW's nice codelets make a huge impact. Plus, Napa-FFT3 is based on a bit-reversed mixed-radix FFT, so multidimensional FFTs are easier to implement (an in-place transpose is just a bunch of bit reverses permutations).

Paul Khuong