Data.Number.Flint.Acb.DFT

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\).

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 ()

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 ()

acb_dft_inverse w v n prec

Compute the inverse DFT of v into w.

DFT Precomputation

data AcbDftPre

Constructors

AcbDftPre !(ForeignPtr CAcbDftPre)

Instances

Storable CAcbDftPre

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

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_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 ()

acb_dft_precomp_clear pre

Clears pre.

acb_dft_precomp :: Ptr CAcb -> Ptr CAcb -> Ptr CAcbDftPre -> CLong -> IO ()

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 ()

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 ()

acb_dft_convol_naive w f g len prec

acb_dft_convol_rad2 :: Ptr CAcb -> Ptr CAcb -> Ptr CAcb -> CLong -> CLong -> IO ()

acb_dft_convol_rad2 w f g len prec

acb_dft_convol :: Ptr CAcb -> Ptr CAcb -> Ptr CAcb -> CLong -> CLong -> IO ()

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

data AcbDftCrt

Constructors

AcbDftCrt !(ForeignPtr CAcbDftCrt)

Instances

Storable CAcbDftCrt

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

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 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 ()

acb_dft_crt_init t len prec

acb_dft_crt_clear :: Ptr CAcbDftCrt -> IO ()

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 ()

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.

Radix 2 decomposition

Bluestein transform