Copyright | [2012..2017] Manuel M T Chakravarty Gabriele Keller Trevor L. McDonell [2013..2017] Robert Clifton-Everest |
---|---|

License | BSD3 |

Maintainer | Trevor L. McDonell <tmcdonell@cse.unsw.edu.au> |

Stability | experimental |

Portability | non-portable (GHC extensions) |

Safe Haskell | None |

Language | Haskell98 |

Compute the Discrete Fourier Transform (DFT) along the lower order dimension of an array.

This uses a naïve algorithm which takes O(n^2) time. However, you can transform an array with an arbitrary extent, unlike with FFT which requires each dimension to be a power of two.

The `dft`

and `idft`

functions compute the roots of unity as needed. If you
need to transform several arrays with the same extent than it is faster to
compute the roots once using `rootsOfUnity`

or `inverseRootsOfUnity`

respectively, then call `dftG`

directly.

You can also compute single values of the transform using `dftGS`

## Synopsis

- dft :: (Shape sh, Slice sh, Elt (Complex e), RealFloat e, FromIntegral Int e) => Acc (Array (sh :. Int) (Complex e)) -> Acc (Array (sh :. Int) (Complex e))
- idft :: (Shape sh, Slice sh, Elt (Complex e), RealFloat e, FromIntegral Int e) => Acc (Array (sh :. Int) (Complex e)) -> Acc (Array (sh :. Int) (Complex e))
- dftG :: forall sh e. (Shape sh, Slice sh, Elt (Complex e), RealFloat e) => Acc (Array (sh :. Int) (Complex e)) -> Acc (Array (sh :. Int) (Complex e)) -> Acc (Array (sh :. Int) (Complex e))
- dftGS :: forall sh e. (Shape sh, Slice sh, Elt (Complex e), RealFloat e) => Exp (sh :. Int) -> Acc (Array (sh :. Int) (Complex e)) -> Acc (Array (sh :. Int) (Complex e)) -> Acc (Scalar (Complex e))

# Documentation

dft :: (Shape sh, Slice sh, Elt (Complex e), RealFloat e, FromIntegral Int e) => Acc (Array (sh :. Int) (Complex e)) -> Acc (Array (sh :. Int) (Complex e)) Source #

Compute the DFT along the low order dimension of an array

idft :: (Shape sh, Slice sh, Elt (Complex e), RealFloat e, FromIntegral Int e) => Acc (Array (sh :. Int) (Complex e)) -> Acc (Array (sh :. Int) (Complex e)) Source #

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

:: (Shape sh, Slice sh, Elt (Complex e), RealFloat e) | |

=> Acc (Array (sh :. Int) (Complex e)) | roots of unity |

-> Acc (Array (sh :. Int) (Complex e)) | input array |

-> Acc (Array (sh :. Int) (Complex e)) |

Generic function for computation of forward and inverse DFT. This function is also useful if you transform many arrays of the same extent, and don't want to recompute the roots for each one.

The extent of the input and roots must match.