## The Fourier structure

#### Synopsis

signature FOURIER
structure Fourier : FOURIER
The Fourier structure implements both the standard Discrete Fourier Transform and the Cooley-Tukey Fast Fourier Transform, and their inverses, in one and two dimensions. It requires the Complex structure.

#### Interface

val dft : Complex.complex vector -> Complex.complex vector
val idft : Complex.complex vector -> Complex.complex vector
val dft2d : Complex.complex Array2.array -> Complex.complex Array2.array
val idft2d : Complex.complex Array2.array -> Complex.complex Array2.array

val fft : Complex.complex vector -> Complex.complex vector
val ifft : Complex.complex vector -> Complex.complex vector
val fft2d : Complex.complex Array2.array -> Complex.complex Array2.array
val ifft2d : Complex.complex Array2.array -> Complex.complex Array2.array

#### Details

val dft : Complex.complex vector -> Complex.complex vector
Compute the one-dimensional Fourier Transform using the (glacially slow) naive algorithm.

val idft : Complex.complex vector -> Complex.complex vector
Compute the one-dimensional inverse Fourier Transform using the (glacially slow) naive algorithm.

val dft2d : Complex.complex Array2.array -> Complex.complex Array2.array
Compute the two-dimensional Fourier Transform using the (glacially slow) naive algorithm.

val idft2d : Complex.complex Array2.array -> Complex.complex Array2.array
Compute the two-dimensional inverse Fourier Transform using the (glacially slow) naive algorithm.

val fft : Complex.complex vector -> Complex.complex vector
Compute the one-dimensional Fourier Transform using the Cooley-Tukey FFT algorithm. Due to the nature of the algorithm, the number of elements in the input (and output) vector must be integer powers of two.

val ifft : Complex.complex vector -> Complex.complex vector
Compute the one-dimensional inverse Fourier Transform using the Cooley-Tukey FFT algorithm. Due to the nature of the algorithm, the number of elements in the input (and output) vector must be integer powers of two.

val fft2d : Complex.complex Array2.array -> Complex.complex Array2.array
Compute the two-dimensional Fourier Transform using the Cooley-Tukey FFT algorithm. Due to the nature of the algorithm, the number of rows and the number of columns in the input (and output) array must be integer powers of two.

val ifft2d : Complex.complex Array2.array -> Complex.complex Array2.array
Compute the two-dimensional inverse Fourier Transform using the Cooley-Tukey FFT algorithm. Due to the nature of the algorithm, the number of rows and the number of columns in the input (and output) array must be integer powers of two.