| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.Number.Flint.Acb.DFT
Description
Warning: the interfaces in this module are experimental and may change without notice.
All functions support aliasing.
Let G be a finite abelian group, and \(\chi\) a character of G. For any map \(f:G\to\mathbb C\), the discrete fourier transform \(\hat f:\hat G\to \mathbb C\) is defined by
\[\hat f(\chi) = \sum_{x\in G}\overline{\chi(x)}f(x)\]
Note that by the inversion formula
\[\widehat{\hat{f}}\left(\chi\right) = \# G \times f\left(\chi^{{}-1}\right)\]
it is straightforward to recover \(f\) from its DFT \(\hat f\).
Synopsis
- acb_dft :: Ptr CAcb -> Ptr CAcb -> CLong -> CLong -> IO ()
- acb_dft_inverse :: Ptr CAcb -> Ptr CAcb -> CLong -> CLong -> IO ()
- data AcbDftPre = AcbDftPre !(ForeignPtr CAcbDftPre)
- type CAcbDftPre = CFlint AcbDftPre
- newAcbDftPre :: CLong -> CLong -> IO AcbDftPre
- withAcbDftPre :: AcbDftPre -> (Ptr CAcbDftPre -> IO a) -> IO (AcbDftPre, a)
- withNewAcbDftPre :: CLong -> CLong -> (Ptr CAcbDftPre -> IO a) -> IO (AcbDftPre, a)
- acb_dft_precomp_init :: Ptr CAcbDftPre -> CLong -> CLong -> IO ()
- acb_dft_precomp_clear :: Ptr CAcbDftPre -> IO ()
- acb_dft_precomp :: Ptr CAcb -> Ptr CAcb -> Ptr CAcbDftPre -> CLong -> IO ()
- acb_dft_inverse_precomp :: Ptr CAcb -> Ptr CAcb -> Ptr CAcbDftPre -> CLong -> IO ()
- acb_dft_convol_naive :: Ptr CAcb -> Ptr CAcb -> Ptr CAcb -> CLong -> CLong -> IO ()
- acb_dft_convol_rad2 :: Ptr CAcb -> Ptr CAcb -> Ptr CAcb -> CLong -> CLong -> IO ()
- acb_dft_convol :: Ptr CAcb -> Ptr CAcb -> Ptr CAcb -> CLong -> CLong -> IO ()
- data AcbDftCrt = AcbDftCrt !(ForeignPtr CAcbDftCrt)
- type CAcbDftCrt = CFlint AcbDftCrt
- newAcbDftCrt :: CLong -> CLong -> IO AcbDftCrt
- withAcbDftCrt :: AcbDftCrt -> (Ptr CAcbDftCrt -> IO a) -> IO (AcbDftCrt, a)
- withNewAcbDftCrt :: CLong -> CLong -> (Ptr CAcbDftCrt -> IO a) -> IO (AcbDftCrt, a)
- acb_dft_crt :: Ptr CAcb -> Ptr CAcb -> CLong -> CLong -> IO ()
- acb_dft_crt_init :: Ptr CAcbDftCrt -> CLong -> CLong -> IO ()
- acb_dft_crt_clear :: Ptr CAcbDftCrt -> IO ()
- acb_dft_crt_precomp :: Ptr CAcb -> Ptr CAcb -> Ptr CAcbDftCrt -> CLong -> IO ()
Discrete Fourier transform
Main DFT functions
If \(G=\mathbb Z/n\mathbb Z\), we compute the DFT according to the usual convention
\[w_x = \sum_{y\bmod n} v_y e^{-\frac{2i \pi}nxy}\]
acb_dft :: Ptr CAcb -> Ptr CAcb -> CLong -> CLong -> IO () Source #
acb_dft w v n prec
Set w to the DFT of v of length len, using an automatic choice of algorithm.
acb_dft_inverse :: Ptr CAcb -> Ptr CAcb -> CLong -> CLong -> IO () Source #
acb_dft_inverse w v n prec
Compute the inverse DFT of v into w.
DFT Precomputation
Constructors
| AcbDftPre !(ForeignPtr CAcbDftPre) |
Instances
| Storable CAcbDftPre Source # | |
Defined in Data.Number.Flint.Acb.DFT.FFI Methods sizeOf :: CAcbDftPre -> Int # alignment :: CAcbDftPre -> Int # peekElemOff :: Ptr CAcbDftPre -> Int -> IO CAcbDftPre # pokeElemOff :: Ptr CAcbDftPre -> Int -> CAcbDftPre -> IO () # peekByteOff :: Ptr b -> Int -> IO CAcbDftPre # pokeByteOff :: Ptr b -> Int -> CAcbDftPre -> IO () # peek :: Ptr CAcbDftPre -> IO CAcbDftPre # poke :: Ptr CAcbDftPre -> CAcbDftPre -> IO () # | |
type CAcbDftPre = CFlint AcbDftPre Source #
withAcbDftPre :: AcbDftPre -> (Ptr CAcbDftPre -> IO a) -> IO (AcbDftPre, a) Source #
withNewAcbDftPre :: CLong -> CLong -> (Ptr CAcbDftPre -> IO a) -> IO (AcbDftPre, a) Source #
acb_dft_precomp_init :: Ptr CAcbDftPre -> CLong -> CLong -> IO () Source #
acb_dft_precomp_init pre len prec
Initializes the fast DFT scheme of length len, using an automatic choice of algorithms depending on the factorization of len.
The length len is stored as pre->n.
If several computations are to be done on the same group, the FFT scheme should be reused.
acb_dft_precomp_clear :: Ptr CAcbDftPre -> IO () Source #
acb_dft_precomp_clear pre
Clears pre.
acb_dft_precomp :: Ptr CAcb -> Ptr CAcb -> Ptr CAcbDftPre -> CLong -> IO () Source #
acb_dft_precomp w v pre prec
Computes the DFT of the sequence v into w by applying the precomputed scheme pre. Both v and w must have length pre->n.
acb_dft_inverse_precomp :: Ptr CAcb -> Ptr CAcb -> Ptr CAcbDftPre -> CLong -> IO () Source #
acb_dft_inverse_precomp w v pre prec
Compute the inverse DFT of v into w.
Convolution
acb_dft_convol_naive :: Ptr CAcb -> Ptr CAcb -> Ptr CAcb -> CLong -> CLong -> IO () Source #
acb_dft_convol_naive w f g len prec
acb_dft_convol_rad2 :: Ptr CAcb -> Ptr CAcb -> Ptr CAcb -> CLong -> CLong -> IO () Source #
acb_dft_convol_rad2 w f g len prec
acb_dft_convol :: Ptr CAcb -> Ptr CAcb -> Ptr CAcb -> CLong -> CLong -> IO () Source #
acb_dft_convol w f g len prec
Sets w to the convolution of f and g of length len.
The naive version simply uses the definition.
The rad2 version embeds the sequence into a power of 2 length and uses the formula
\[\widehat{f \star g}(\chi) = \hat f(\chi)\hat g(\chi)\]
to compute it using three radix 2 FFT.
The default version uses radix 2 FFT unless len is a product of small primes where a non padded FFT is faster.
FFT algorithms
CRT decomposition
Constructors
| AcbDftCrt !(ForeignPtr CAcbDftCrt) |
Instances
| Storable CAcbDftCrt Source # | |
Defined in Data.Number.Flint.Acb.DFT.FFI Methods sizeOf :: CAcbDftCrt -> Int # alignment :: CAcbDftCrt -> Int # peekElemOff :: Ptr CAcbDftCrt -> Int -> IO CAcbDftCrt # pokeElemOff :: Ptr CAcbDftCrt -> Int -> CAcbDftCrt -> IO () # peekByteOff :: Ptr b -> Int -> IO CAcbDftCrt # pokeByteOff :: Ptr b -> Int -> CAcbDftCrt -> IO () # peek :: Ptr CAcbDftCrt -> IO CAcbDftCrt # poke :: Ptr CAcbDftCrt -> CAcbDftCrt -> IO () # | |
type CAcbDftCrt = CFlint AcbDftCrt Source #
withAcbDftCrt :: AcbDftCrt -> (Ptr CAcbDftCrt -> IO a) -> IO (AcbDftCrt, a) Source #
withNewAcbDftCrt :: CLong -> CLong -> (Ptr CAcbDftCrt -> IO a) -> IO (AcbDftCrt, a) Source #
acb_dft_crt :: Ptr CAcb -> Ptr CAcb -> CLong -> CLong -> IO () Source #
acb_dft_crt w v n prec
Computes the DFT of v into w, where v and w have size len, using CRT to express \(\mathbb Z/n\mathbb Z\) as a product of cyclic groups.
acb_dft_crt_init :: Ptr CAcbDftCrt -> CLong -> CLong -> IO () Source #
acb_dft_crt_init t len prec
acb_dft_crt_clear :: Ptr CAcbDftCrt -> IO () Source #
acb_dft_crt_clear t
Initialize a CRT decomposition of \(\mathbb Z/n\mathbb Z\) as a direct product of cyclic groups. The length len is stored as t->n.
acb_dft_crt_precomp :: Ptr CAcb -> Ptr CAcb -> Ptr CAcbDftCrt -> CLong -> IO () Source #
acb_dft_crt_precomp w v t prec
Sets w to the DFT of v of size t->n, using the CRT decomposition scheme t.