# FFT Implementations

## Existing packages

The following packages extend the functionality provided by AbstractFFTs:

- FFTW.jl: Bindings for the FFTW library. This also used to be part of Base Julia.
- FastTransforms.jl: Pure-Julia implementation of FFT, with support for arbitrary AbstractFloat types.

## Defining a new implementation

To define a new FFT implementation in your own module, you should

Define a new subtype (e.g.

`MyPlan`

) of`AbstractFFTs.Plan{T}`

for FFTs and related transforms on arrays of`T`

. This must have a`pinv::Plan`

field, initially undefined when a`MyPlan`

is created, that is used for caching the inverse plan.Define a new method

`AbstractFFTs.plan_fft(x, region; kws...)`

that returns a`MyPlan`

for at least some types of`x`

and some set of dimensions`region`

. The`region`

(or a copy thereof) should be accessible via`fftdims(p::MyPlan)`

(which defaults to`p.region`

), and the input size`size(x)`

should be accessible via`size(p::MyPlan)`

.Define a method of

`LinearAlgebra.mul!(y, p::MyPlan, x)`

that computes the transform`p`

of`x`

and stores the result in`y`

.Define a method of

`*(p::MyPlan, x)`

, which can simply call your`mul!`

method. This is not defined generically in this package due to subtleties that arise for in-place and real-input FFTs.If the inverse transform is implemented, you should also define

`plan_inv(p::MyPlan)`

, which should construct the inverse plan to`p`

, and`plan_bfft(x, region; kws...)`

for an unnormalized inverse ("backwards") transform of`x`

. Implementations only need to provide the unnormalized backwards FFT, similar to FFTW, and we do the scaling generically to get the inverse FFT.You can also define similar methods of

`plan_rfft`

and`plan_brfft`

for real-input FFTs.To support adjoints in a new plan, define the trait

`AbstractFFTs.AdjointStyle`

.`AbstractFFTs`

implements the following adjoint styles:`AbstractFFTs.FFTAdjointStyle`

,`AbstractFFTs.RFFTAdjointStyle`

,`AbstractFFTs.IRFFTAdjointStyle`

, and`AbstractFFTs.UnitaryAdjointStyle`

. To define a new adjoint style, define the methods`AbstractFFTs.adjoint_mul`

and`AbstractFFTs.output_size`

.

The normalization convention for your FFT should be that it computes $y_k = \sum_j x_j \exp(-2\pi i j k/n)$ for a transform of length $n$, and the "backwards" (unnormalized inverse) transform computes the same thing but with $\exp(+2\pi i jk/n)$.

## Testing implementations

`AbstractFFTs.jl`

provides an experimental `TestUtils`

module to help with testing downstream implementations, available as a weak extension of `Test`

. The following functions test that all FFT functionality has been correctly implemented:

`AbstractFFTs.TestUtils.test_complex_ffts`

— Function`TestUtils.test_complex_ffts(ArrayType=Array; test_inplace=true, test_adjoint=true)`

Run tests to verify correctness of FFT, BFFT, and IFFT functionality using a particular backend plan implementation. The backend implementation is assumed to be loaded prior to calling this function.

**Arguments**

`ArrayType`

: determines the`AbstractArray`

implementation for which the correctness tests are run. Arrays are constructed via`convert(ArrayType, ...)`

.`test_inplace=true`

: whether to test in-place plans.`test_adjoint=true`

: whether to test plan adjoints.

`AbstractFFTs.TestUtils.test_real_ffts`

— Function`TestUtils.test_real_ffts(ArrayType=Array; test_adjoint=true, copy_input=false)`

Run tests to verify correctness of RFFT, BRFFT, and IRFFT functionality using a particular backend plan implementation. The backend implementation is assumed to be loaded prior to calling this function.

**Arguments**

`ArrayType`

: determines the`AbstractArray`

implementation for which the correctness tests are run. Arrays are constructed via`convert(ArrayType, ...)`

.`test_adjoint=true`

: whether to test plan adjoints.`copy_input=false`

: whether to copy the input before applying the plan in tests, to accomodate for input-mutating behaviour of real FFTW plans.

`TestUtils`

also exposes lower level functions for generically testing particular plans:

`AbstractFFTs.TestUtils.test_plan`

— Function```
TestUtils.test_plan(P::Plan, x::AbstractArray, x_transformed::AbstractArray;
inplace_plan=false, copy_input=false)
```

Test basic properties of a plan `P`

given an input array `x`

and expected output `x_transformed`

.

Because real FFTW plans may mutate their input in some cases, we allow specifying `copy_input=true`

to allow for this behaviour in tests by copying the input before applying the plan.

`AbstractFFTs.TestUtils.test_plan_adjoint`

— Function`TestUtils.test_plan_adjoint(P::Plan, x::AbstractArray; real_plan=false, copy_input=false)`

Test basic properties of the adjoint `P'`

of a particular plan given an input array `x`

, including its accuracy via the dot test.

Real-to-complex and complex-to-real plans require a slightly modified dot test, in which case `real_plan=true`

should be provided. The plan is assumed out-of-place, as adjoints are not yet supported for in-place plans. Because real FFTW plans may mutate their input in some cases, we allow specifying `copy_input=true`

to allow for this behaviour in tests by copying the input before applying the plan.