JuliaLang/julia — pull request #6193 by stevengj (2014-03-18 02:09:53+00:00)
Title: WIP: new DFT api

This is not quite ready to merge yet, but I wanted to bring it to your attention to see what you think. It is a rewritten DFT API that provides:

* `p = plan_fft(x)` (and similar) now returns a subtype of` `DFT.Plan`. It acts like a linear operator: you can apply it to an existing array with `p * x`, and apply it to a preallocated output array with `A_mul_B!(y, p, x)`.
* It is easy to add new FFT algorithm implementations for specific numeric and array types...

Partly since we have discussed moving FFTW to a module at some point, and partly to support numeric types like `BigFloat`, the patch also includes a start at a pure-Julia FFT implementation, with the following features.

* One-dimensional transforms of arbitrary `AbstractVector`s of arbitrary `Complex` types (including `BigFloat`), with fast algorithms for all sizes (including prime sizes). Multidimensional transforms of arbitrary `StridedArray` subtypes.
* Uses code generation (a baby version of the FFTW code generator) in Julia to generate kernels for use as base cases of the transforms; algorithms in general are FFTW2-like.
* Performance is reasonable. For moderate-power-of-two sizes, it is within a factor of 2-4 of FFTW, with the difference mainly due to the lack of SIMD. For non-power-of-two sizes, the performance is several times worse, but I suspect that there may be some fixable code-generation problem there.

Major to-do items:
- [ ] Documentation
- [ ] Native Julia `rfft` support.

cc: @JeffBezanson, @timholy