-- | -- Module : Math.FFT -- Copyright : (c) 2008 Jed Brown -- License : BSD-style -- -- Maintainer : jed@59A2.org -- Stability : experimental -- Portability : non-portable -- -- This module exposes an interface to FFTW, the Fastest Fourier Transform in -- the West. -- -- These bindings present several levels of interface. All the higher level -- functions ('dft', 'idft', 'dftN', ...) are easily derived from the general -- functions ('dftG', 'dftRCG', ...). Only the general functions let you -- specify planner flags. The higher levels all set 'estimate' so you should -- not have to wait through time consuming planning (see below for more). -- -- The simplest interface is the one-dimensional transforms. If you supply a -- multi-dimensional array, these will only transform the first dimension. -- These functions only take one argument, the array to be transformed. -- -- At the next level, we have multi-dimensional transforms where you specify -- which dimensions to transform in and the array to transform. For instance -- -- > b = dftRCN [0,2] a -- -- is the real to complex transform in dimensions 0 and 2 of the array @a@ which -- must be at least rank 3. The array @b@ will be complex valued with the same -- extent as @a@ in every dimension except @2@. If @a@ had extent @n@ in -- dimension @2@ then the @b@ will have extent @a `div` 2 + 1@ which consists of -- all non-negative frequency components in this dimension (the negative -- frequencies are conjugate to the positive frequencies because of symmetry -- since @a@ is real valued). -- -- The real to real transforms allow different transform kinds in each -- transformed dimension. For example, -- -- > b = dftRRN [(0,DHT), (1,REDFT10), (2,RODFT11)] a -- -- is a Discrete Hartley Transform in dimension 0, a discrete cosine transform -- (DCT-2) in dimension 1, and distrete sine transform (DST-4) in dimension 2 -- where the array @a@ must have rank at least 3. -- -- The general interface is similar to the multi-dimensional interface, takes as -- its first argument, a bitwise '.|.' of planning 'Flag's. (In the complex -- version, the sign of the transform is first.) For example, -- -- > b = dftG DFTBackward (patient .|. destroy_input) [1,2] a -- -- is an inverse DFT in dimensions 1 and 2 of the complex array @a@ which has -- rank at least 3. It will use the patient planner to generate a (near) -- optimal transform. If you compute the same type of transform again, it -- should be very fast since the plan is cached. -- -- Inverse transforms are typically normalized. The un-normalized inverse -- transforms are 'dftGU', 'dftCRGU' and 'dftCROGU'. For example -- -- > b = dftCROGU measure [0,1] a -- -- is an un-normalized inverse DFT in dimensions 0 and 1 of the complex array -- @a@ (representing the non-negative frequencies, where the negative -- frequencies are conjugate) which has rank at least 2. Here, dimension 1 is -- logically odd so if @a@ has extent @n@ in dimension 1, then @b@ will have -- extent @(n - 1) * 2 + 1@ in dimension 1. It is more common that the logical -- dimension is even, in which case we would use 'dftCRGU' in which case @b@ -- would have extent @(n - 1) * 2@ in dimension @1@. -- -- -- The FFTW library separates transforms into two steps. First you compute a -- plan for a given transform, then you execute it. Often the planning stage is -- quite time-consuming, but subsequent transforms of the same size and type -- will be extremely fast. The planning phase actually computes transforms, so -- it overwrites its input array. For many C codes, it is reasonable to re-use -- the same arrays to compute a given transform on different data. This is not -- a very useful paradigm from Haskell. Fortunately, FFTW caches its plans so -- if try to generate a new plan for a transform size which has already been -- planned, the planner will return immediately. Unfortunately, it is not -- possible to consult the cache, so if a plan is cached, we may use more memory -- than is strictly necessary since we must allocate a work array which we -- expect to be overwritten during planning. FFTW can export its cached plans -- to a string. This is known as wisdom. For high performance work, it is a -- good idea to compute plans of the sizes you are interested in, using -- aggressive options (i.e. 'patient'), use 'exportWisdomString' to get a string -- representing these plans, and write this to a file. Then for production -- runs, you can read this in, then add it to the cache with -- 'importWisdomString'. Now you can use the 'estimate' planner so the Haskell -- bindings know that FFTW will not overwrite the input array, and you will -- still get a high quality transform (because it has wisdom). module Math.FFT ( -- * Data types Sign(..), Kind(..), -- * Planner flags -- ** Algorithm restriction flags destroyInput, preserveInput, -- ** Planning rigor flags estimate, measure, patient, exhaustive, -- * DFT of complex data -- ** DFT in first dimension only dft, idft, -- ** Multi-dimensional transforms dftN, idftN, -- ** General transform dftG, -- ** Un-normalized general transform dftGU, -- * DFT of real data -- ** DFT in first dimension only dftRC, dftCR, dftCRO, -- ** Multi-dimensional transforms dftRCN, dftCRN, dftCRON, -- ** General transform dftRCG, dftCRG, dftCROG, -- ** Un-normalized general transform dftCRGU, dftCROGU, -- * Real to real transforms (all un-normalized) -- ** Transforms in first dimension only dftRH, dftHR, dht, dct1, dct2, dct3, dct4, dst1, dst2, dst3, dst4, -- ** Multi-dimensional transforms with the same transform type in each dimension dftRHN, dftHRN, dhtN, dct1N, dct2N, dct3N, dct4N, dst1N, dst2N, dst3N, dst4N, -- ** Multi-dimensional transforms with possibly different transforms in each dimension dftRRN, -- ** General transforms dftRRG, -- * Wisdom importWisdomString, importWisdomSystem, exportWisdomString, ) where import Math.FFT.Base