# Fourier

Fourier implements functionality for performing Discrete Fourier Transforms (DFTs). The core functionality of the package is a *highly optimized* set of routines for performing forward and reverse DFTs of 2D data using the matrix triple product method as described in Soummer et al (2007). The routines work for any `NxM`

matrix for `N, M > 1`

include square and nonsquare dimensions of even or odd size. Performance is at worst on par with the FFTW invocation:

```
using FFTW
N=2; M=3;
a = rand(N,M);
b = a |> ifftshift |> fft |> fftshift;
```

for any `N*M <= 1024*1024`

.

## Installation

Fourier is a registered Julia package, it may be installed the usual way:

`julia> Pkg.add("Fourier")`

## Functions

`Fourier.mdft`

— Function.`mdft(ary, samples[, shift, Q])`

Compute and return the 2D DFT via a matrix triple product. Equivalent to fftshift(fft(ifftshift(ary))) if shift==0, samples=size(ary), Q=1.

samples is the number of samples in the output domain. If it is an integer, it is broadcast to both dimensions. Otherwise it may be a tuple to provide each.

shift is used to move the origin. If the output grid with shift=0 spanned -10:1:9 Hz, shift=10 will move the output grid to 0:1:19Hz. The unit is samples, not hertz. The first argument is along x, or the columns of the matrix, not dim 0.

Q controls the oversampling factor. It is equivalent to zero padding the input array by the same factor. E.g. mdft of a 256x256 array with Q=2 is the same as zero padding it to 512x512 and FFTing that.

See also: `imdft`

**References**

"Fast computation of Lyot-style coronagraph propagation" Soummer et al, oe-15-24-15935

`Fourier.imdft`

— Function.`imdft(ary, samples[, shift, Q])`

Compute and return the 2D inverse DFT via a matrix triple product. Equivalent to fftshift(ifft(ifftshift(ary))) if shift==0, samples=size(ary), Q=1.

samples is the number of samples in the output domain. If it is an integer, it is broadcast to both dimensions. Otherwise it may be a tuple to provide each.

shift is used to move the origin. If the output grid with shift=0 spanned -10:1:9 Hz, shift=10 will move the output grid to 0:1:19Hz. The unit is samples, not hertz. The first argument is along x, or the columns of the matrix, not dim 0.

Q controls the oversampling factor. It is equivalent to zero padding the input array by the same factor. E.g. mdft of a 256x256 array with Q=2 is the same as zero padding it to 512x512 and FFTing that.

See also: `mdft`

**References**

"Fast computation of Lyot-style coronagraph propagation" Soummer et al, oe-15-24-15935

## Utilities

`Fourier.fftrange`

— Function.`fftrange(n)`

Computes a range that always matches FFT expectations. I.e., for even N ranges matches the example n=4 => -2:1:1 and for odd N matches the example 5 => -2:1:2.

This can be understood as "the output range shall always contain zero, if there may be only one value for n÷2, it will be the negative one."

The range is always centered; frequency or sampling bins align to it with fftshift. It can be fftshifted to be placed in post-FFT coordinates.