# Public Interface

## FFT and FFT planning functions

`AbstractFFTs.fft`

— Function`fft(A [, dims])`

Performs a multidimensional FFT of the array `A`

. The optional `dims`

argument specifies an iterable subset of dimensions (e.g. an integer, range, tuple, or array) to transform along. Most efficient if the size of `A`

along the transformed dimensions is a product of small primes; see `Base.nextprod`

. See also `plan_fft()`

for even greater efficiency.

A one-dimensional FFT computes the one-dimensional discrete Fourier transform (DFT) as defined by

\[\operatorname{DFT}(A)[k] = \sum_{n=1}^{\operatorname{length}(A)} \exp\left(-i\frac{2\pi (n-1)(k-1)}{\operatorname{length}(A)} \right) A[n].\]

A multidimensional FFT simply performs this operation along each transformed dimension of `A`

.

This performs a multidimensional FFT by default. FFT libraries in other languages such as Python and Octave perform a one-dimensional FFT along the first non-singleton dimension of the array. This is worth noting while performing comparisons.

`AbstractFFTs.fft!`

— Function`fft!(A [, dims])`

Same as `fft`

, but operates in-place on `A`

, which must be an array of complex floating-point numbers.

`AbstractFFTs.ifft`

— Function`ifft(A [, dims])`

Multidimensional inverse FFT.

A one-dimensional inverse FFT computes

\[\operatorname{IDFT}(A)[k] = \frac{1}{\operatorname{length}(A)} \sum_{n=1}^{\operatorname{length}(A)} \exp\left(+i\frac{2\pi (n-1)(k-1)} {\operatorname{length}(A)} \right) A[n].\]

A multidimensional inverse FFT simply performs this operation along each transformed dimension of `A`

.

`AbstractFFTs.ifft!`

— Function`ifft!(A [, dims])`

Same as `ifft`

, but operates in-place on `A`

.

`AbstractFFTs.bfft`

— Function`bfft(A [, dims])`

Similar to `ifft`

, but computes an unnormalized inverse (backward) transform, which must be divided by the product of the sizes of the transformed dimensions in order to obtain the inverse. (This is slightly more efficient than `ifft`

because it omits a scaling step, which in some applications can be combined with other computational steps elsewhere.)

\[\operatorname{BDFT}(A)[k] = \operatorname{length}(A) \operatorname{IDFT}(A)[k]\]

`AbstractFFTs.bfft!`

— Function`bfft!(A [, dims])`

Same as `bfft`

, but operates in-place on `A`

.

`AbstractFFTs.plan_fft`

— Function`plan_fft(A [, dims]; flags=FFTW.ESTIMATE, timelimit=Inf)`

Pre-plan an optimized FFT along given dimensions (`dims`

) of arrays matching the shape and type of `A`

. (The first two arguments have the same meaning as for `fft`

.) Returns an object `P`

which represents the linear operator computed by the FFT, and which contains all of the information needed to compute `fft(A, dims)`

quickly.

To apply `P`

to an array `A`

, use `P * A`

; in general, the syntax for applying plans is much like that of matrices. (A plan can only be applied to arrays of the same size as the `A`

for which the plan was created.) You can also apply a plan with a preallocated output array `Â`

by calling `mul!(Â, plan, A)`

. (For `mul!`

, however, the input array `A`

must be a complex floating-point array like the output `Â`

.) You can compute the inverse-transform plan by `inv(P)`

and apply the inverse plan with `P \ Â`

(the inverse plan is cached and reused for subsequent calls to `inv`

or `\`

), and apply the inverse plan to a pre-allocated output array `A`

with `ldiv!(A, P, Â)`

.

The `flags`

argument is a bitwise-or of FFTW planner flags, defaulting to `FFTW.ESTIMATE`

. e.g. passing `FFTW.MEASURE`

or `FFTW.PATIENT`

will instead spend several seconds (or more) benchmarking different possible FFT algorithms and picking the fastest one; see the FFTW manual for more information on planner flags. The optional `timelimit`

argument specifies a rough upper bound on the allowed planning time, in seconds. Passing `FFTW.MEASURE`

or `FFTW.PATIENT`

may cause the input array `A`

to be overwritten with zeros during plan creation.

`plan_fft!`

is the same as `plan_fft`

but creates a plan that operates in-place on its argument (which must be an array of complex floating-point numbers). `plan_ifft`

and so on are similar but produce plans that perform the equivalent of the inverse transforms `ifft`

and so on.

`AbstractFFTs.plan_ifft`

— Function`plan_ifft(A [, dims]; flags=FFTW.ESTIMATE, timelimit=Inf)`

Same as `plan_fft`

, but produces a plan that performs inverse transforms `ifft`

.

`AbstractFFTs.plan_bfft`

— Function`plan_bfft(A [, dims]; flags=FFTW.ESTIMATE, timelimit=Inf)`

Same as `plan_fft`

, but produces a plan that performs an unnormalized backwards transform `bfft`

.

`AbstractFFTs.plan_fft!`

— Function`plan_fft!(A [, dims]; flags=FFTW.ESTIMATE, timelimit=Inf)`

Same as `plan_fft`

, but operates in-place on `A`

.

`AbstractFFTs.plan_ifft!`

— Function`plan_ifft!(A [, dims]; flags=FFTW.ESTIMATE, timelimit=Inf)`

Same as `plan_ifft`

, but operates in-place on `A`

.

`AbstractFFTs.plan_bfft!`

— Function`plan_bfft!(A [, dims]; flags=FFTW.ESTIMATE, timelimit=Inf)`

Same as `plan_bfft`

, but operates in-place on `A`

.

`AbstractFFTs.rfft`

— Function`rfft(A [, dims])`

Multidimensional FFT of a real array `A`

, exploiting the fact that the transform has conjugate symmetry in order to save roughly half the computational time and storage costs compared with `fft`

. If `A`

has size `(n_1, ..., n_d)`

, the result has size `(div(n_1,2)+1, ..., n_d)`

.

The optional `dims`

argument specifies an iterable subset of one or more dimensions of `A`

to transform, similar to `fft`

. Instead of (roughly) halving the first dimension of `A`

in the result, the `dims[1]`

dimension is (roughly) halved in the same way.

`AbstractFFTs.irfft`

— Function`irfft(A, d [, dims])`

Inverse of `rfft`

: for a complex array `A`

, gives the corresponding real array whose FFT yields `A`

in the first half. As for `rfft`

, `dims`

is an optional subset of dimensions to transform, defaulting to `1:ndims(A)`

.

`d`

is the length of the transformed real array along the `dims[1]`

dimension, which must satisfy `div(d,2)+1 == size(A,dims[1])`

. (This parameter cannot be inferred from `size(A)`

since both `2*size(A,dims[1])-2`

as well as `2*size(A,dims[1])-1`

are valid sizes for the transformed real array.)

`AbstractFFTs.brfft`

— Function`brfft(A, d [, dims])`

Similar to `irfft`

but computes an unnormalized inverse transform (similar to `bfft`

), which must be divided by the product of the sizes of the transformed dimensions (of the real output array) in order to obtain the inverse transform.

`AbstractFFTs.plan_rfft`

— Function`plan_rfft(A [, dims]; flags=FFTW.ESTIMATE, timelimit=Inf)`

Pre-plan an optimized real-input FFT, similar to `plan_fft`

except for `rfft`

instead of `fft`

. The first two arguments, and the size of the transformed result, are the same as for `rfft`

.

`AbstractFFTs.plan_brfft`

— Function`plan_brfft(A, d [, dims]; flags=FFTW.ESTIMATE, timelimit=Inf)`

Pre-plan an optimized real-input unnormalized transform, similar to `plan_rfft`

except for `brfft`

instead of `rfft`

. The first two arguments and the size of the transformed result, are the same as for `brfft`

.

`AbstractFFTs.plan_irfft`

— Function`plan_irfft(A, d [, dims]; flags=FFTW.ESTIMATE, timelimit=Inf)`

Pre-plan an optimized inverse real-input FFT, similar to `plan_rfft`

except for `irfft`

and `brfft`

, respectively. The first three arguments have the same meaning as for `irfft`

.

`AbstractFFTs.fftdims`

— Function`fftdims(p::Plan)`

Return an iterable of the dimensions that are transformed by the FFT plan `p`

.

**Implementation**

For legacy reasons, the default definition of `fftdims`

returns `p.region`

. Hence this method should be implemented only for `Plan`

subtypes that do not store the transformed dimensions in a field named `region`

.

`AbstractFFTs.fftshift`

— Function`fftshift(x, [dim])`

Circular-shift along the given dimension of a periodic signal `x`

centered at index `1`

so it becomes centered at index `N÷2+1`

, where `N`

is the size of that dimension.

This can be undone with `ifftshift`

. For even `N`

this is equivalent to swapping the first and second halves, so `fftshift`

and `ifftshift`

are the same.

If `dim`

is not given then the signal is shifted along each dimension.

The output of `fftshift`

is allocated. If one desires to store the output in a preallocated array, use `fftshift!`

instead.

`AbstractFFTs.fftshift!`

— Function`fftshift!(dest, src, [dim])`

Nonallocating version of `fftshift`

. Stores the result of the shift of the `src`

array into the `dest`

array.

`AbstractFFTs.ifftshift`

— Function`ifftshift(x, [dim])`

Circular-shift along the given dimension of a periodic signal `x`

centered at index `N÷2+1`

so it becomes centered at index `1`

, where `N`

is the size of that dimension.

This undoes the effect of `fftshift`

. For even `N`

this is equivalent to swapping the first and second halves, so `fftshift`

and `ifftshift`

are the same.

If `dim`

is not given then the signal is shifted along each dimension.

The output of `ifftshift`

is allocated. If one desires to store the output in a preallocated array, use `ifftshift!`

instead.

`AbstractFFTs.ifftshift!`

— Function`ifftshift!(dest, src, [dim])`

Nonallocating version of `ifftshift`

. Stores the result of the shift of the `src`

array into the `dest`

array.

`AbstractFFTs.fftfreq`

— Function`fftfreq(n, fs=1)`

Return the discrete Fourier transform (DFT) sample frequencies for a DFT of length `n`

. The returned `Frequencies`

object is an `AbstractVector`

containing the frequency bin centers at every sample point. `fs`

is the sampling rate of the input signal, which is the reciprocal of the sample spacing.

Given a window of length `n`

and a sampling rate `fs`

, the frequencies returned are

```
[0:n÷2-1; -n÷2:-1] * fs/n # if n is even
[0:(n-1)÷2; -(n-1)÷2:-1] * fs/n # if n is odd
```

**Examples**

```
julia> fftfreq(4, 1)
4-element Frequencies{Float64}:
0.0
0.25
-0.5
-0.25
julia> fftfreq(5, 2)
5-element Frequencies{Float64}:
0.0
0.4
0.8
-0.8
-0.4
```

`AbstractFFTs.rfftfreq`

— Function`rfftfreq(n, fs=1)`

Return the discrete Fourier transform (DFT) sample frequencies for a real DFT of length `n`

. The returned `Frequencies`

object is an `AbstractVector`

containing the frequency bin centers at every sample point. `fs`

is the sampling rate of the input signal, which is the reciprocal of the sample spacing.

Given a window of length `n`

and a sampling rate `fs`

, the frequencies returned are

```
[0:n÷2;] * fs/n # if n is even
[0:(n-1)÷2;] * fs/n # if n is odd
```

The Nyquist-frequency component is considered to be positive, unlike `fftfreq`

.

**Examples**

```
julia> rfftfreq(4, 1)
3-element Frequencies{Float64}:
0.0
0.25
0.5
julia> rfftfreq(5, 2)
3-element Frequencies{Float64}:
0.0
0.4
0.8
```

`Base.size`

— Function`size(p::Plan, [dim])`

Return the size of the input of a plan `p`

, optionally at a specified dimenion `dim`

.

## Adjoint functionality

The following API is supported by plans that support adjoint functionality. It is also relevant to implementers of FFT plans that wish to support adjoints.

Missing docstring for `Base.adjoint`

. Check Documenter's build log for details.

`AbstractFFTs.AdjointStyle`

— Type`AbstractFFTs.AdjointStyle(::Plan)`

Return the adjoint style of a plan, enabling automatic computation of adjoint plans via `Base.adjoint`

. Instructions for supporting adjoint styles are provided in the implementation instructions.

`AbstractFFTs.adjoint_mul`

— Function`adjoint_mul(p::Plan, x::AbstractArray)`

Multiply an array `x`

by the adjoint of a plan `p`

. This is equivalent to `p' * x`

.

Implementations of a new adjoint style `AS <: AbstractFFTs.AdjointStyle`

should define `adjoint_mul(::Plan, ::AbstractArray, ::AS)`

.

`AbstractFFTs.FFTAdjointStyle`

— Type`FFTAdjointStyle()`

Adjoint style for complex to complex discrete Fourier transforms that normalize the output analogously to `fft`

.

Since the Fourier transform is unitary up to a scaling, the adjoint simply applies the transform's inverse with an appropriate scaling.

`AbstractFFTs.RFFTAdjointStyle`

— Type`RFFTAdjointStyle()`

Adjoint style for real to complex discrete Fourier transforms that halve one of the output's dimensions and normalize the output analogously to `rfft`

.

Since the Fourier transform is unitary up to a scaling, the adjoint applies the transform's inverse, but with appropriate scaling and additional logic to handle the fact that the output is projected to exploit its conjugate symmetry (see `rfft`

).

`AbstractFFTs.IRFFTAdjointStyle`

— Type`IRFFTAdjointStyle(d::Dim)`

Adjoint style for complex to real discrete Fourier transforms that expect an input with a halved dimension and normalize the output analogously to `irfft`

, where `d`

is the original length of the dimension.

Since the Fourier transform is unitary up to a scaling, the adjoint applies the transform's inverse, but with appropriate scaling and additional logic to handle the fact that the input is projected to exploit its conjugate symmetry (see `irfft`

).

`AbstractFFTs.UnitaryAdjointStyle`

— Type`UnitaryAdjointStyle()`

Adjoint style for unitary transforms, whose adjoint equals their inverse.