repa-algorithms-1.1.0.0: Algorithms using the Repa array library.

Data.Array.Repa.Algorithms.FFT

Description

Fast computation of Discrete Fourier Transforms using the Cooley-Tuckey algorithm.

Time complexity is O(n log n) in the size of the input.

Input dimensions must be powers of two, else `error`.

The `fft` and `ifft` functions (and friends) also compute the roots of unity needed. If you need to transform several arrays with the same extent then it is faster to compute the roots once using `calcRootsOfUnity` or `calcInverseRootsOfUnity`, then call `fftWithRoots` directly.

The inverse transforms provided also perform post-scaling so that `ifft` is the true inverse of `fft`. If you don't want that then call `fftWithRoots` directly.

The functions `fft2d` and `fft3d` require their inputs to be squares (and cubes) respectively. This allows them to reuse the same roots-of-unity when transforming along each axis. If you need to transform rectanglular arrays then call `fftWithRoots` directly.

Synopsis

# Documentation

fft :: Shape sh => Array (sh :. Int) Complex -> Array (sh :. Int) ComplexSource

Compute the DFT along the low order dimension of an array.

ifft :: Shape sh => Array (sh :. Int) Complex -> Array (sh :. Int) ComplexSource

Compute the inverse DFT along the low order dimension of an array.

Compute the DFT of a square matrix. If the matrix is not square then `error`.

Compute the inverse DFT of a square matrix.

Compute the DFT of a 3d cube. If the array is not a cube then `error`.

Compute the inverse DFT of a 3d cube. If the array is not a cube then `error`.

Arguments

 :: forall sh . Shape sh => Array (sh :. Int) Complex Roots of unity. -> Array (sh :. Int) Complex Input values. -> Array (sh :. Int) Complex

Generic function for computation of forward or inverse Discrete Fourier Transforms. Computation is along the low order dimension of the array.