Data.Array.Repa.Algorithms.FFT

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.

Documentation

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

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

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

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

fft2d :: Array DIM2 Complex -> Array DIM2 Complex

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

ifft2d :: Array DIM2 Complex -> Array DIM2 Complex

Compute the inverse DFT of a square matrix.

fft3d :: Array DIM3 Complex -> Array DIM3 Complex

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

ifft3d :: Array DIM3 Complex -> Array DIM3 Complex

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

fftWithRoots

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.