Trait feanor_math::algorithms::fft::FFTAlgorithm

pub trait FFTAlgorithm<R: ?Sized + RingBase> {
    // Required methods
    fn len(&self) -> usize;
    fn root_of_unity(&self, ring: &R) -> &R::Element;
    fn unordered_fft_permutation(&self, i: usize) -> usize;
    fn unordered_fft_permutation_inv(&self, i: usize) -> usize;
    fn unordered_fft<V>(&self, values: V, ring: &R)
       where V: SwappableVectorViewMut<R::Element>;
    fn unordered_inv_fft<V>(&self, values: V, ring: &R)
       where V: SwappableVectorViewMut<R::Element>;

    // Provided methods
    fn fft<V>(&self, values: V, ring: &R)
       where V: SwappableVectorViewMut<R::Element> { ... }
    fn inv_fft<V>(&self, values: V, ring: &R)
       where V: SwappableVectorViewMut<R::Element> { ... }
}

Trait for objects that can perform a fast fourier transform over some ring.

Usually fast implementations of FFTs have to store a lot of precomputed data (e.g. powers of roots of unity), hence they should be represented as objects implementing this trait.

Note on equality

If you choose to implement PartialEq for an FFTTable, and F == G, then F and G should satisfy the following properties:

• F and G support the same rings
• F.len() == G.len()
• F.root_of_unity(ring) == G.root_of_unity(ring) for each supported ring ring
• F.unordered_fft_permutation(i) == G.unordered_fft_permutation(i) for all i In other words, F and G must have exactly the same output for unordered_fft (and thus fft, inv_fft, …) on same inputs.

Required Methods

fn len(&self) -> usize

This FFTTable can compute the FFT of arrays of this length.

fn root_of_unity(&self, ring: &R) -> &R::Element

The root of unity used for the FFT. While all primitive n-th roots of unity can be used equally for computing a Fourier transform, the concrete one used determines the order of the output values.

See also FFTAlgorithm::unordered_fft_permutation().

fn unordered_fft_permutation(&self, i: usize) -> usize

On input i, returns j such that unordered_fft(values)[i] contains the evaluation at zeta^j of values. Here zeta is the value returned by FFTAlgorithm::root_of_unity()

fn unordered_fft_permutation_inv(&self, i: usize) -> usize

The inverse of FFTAlgorithm::unordered_fft_permutation(), i.e. for all i, have self.unordered_fft_permutation_inv(self.unordered_fft_permutation(i)) == i.

fn unordered_fft<V>(&self, values: V, ring: &R)

where V: SwappableVectorViewMut<R::Element>,

Computes the Fourier transform of the given values, but the output values are arbitrarily permuted (in a way compatible with FFTAlgorithm::unordered_inv_fft()).

Note that the FFT of a sequence a_0, ..., a_(N - 1) is defined as Fa_k = sum_i a_i z^(-ik) where z is an N-th root of unity.

fn unordered_inv_fft<V>(&self, values: V, ring: &R)

where V: SwappableVectorViewMut<R::Element>,

Inverse to FFTAlgorithm::unordered_fft(), with basically the same contract.

Provided Methods

fn fft<V>(&self, values: V, ring: &R)

where V: SwappableVectorViewMut<R::Element>,

Computes the Fourier transform of the given values over the specified ring. The output is in standard order, i.e. the i-th output element is the evaluation of the input at self.root_of_unity()^-i (note the -, which is standard convention for Fourier transforms).

Panics

This function panics if values.len() != self.len().

fn inv_fft<V>(&self, values: V, ring: &R)

where V: SwappableVectorViewMut<R::Element>,

Computes the Fourier transform of the given values over the specified ring. The output is in standard order, i.e. the i-th output element is the evaluation of the input at self.root_of_unity()^i, divided by self.len().

Panics

This function panics if values.len() != self.len().

Object Safety

This trait is not object safe.

Implementors

impl<R_main, R_twiddle, H> FFTAlgorithm<R_main> for CooleyTuckeyFFT<R_main, R_twiddle, H>

where R_main: ?Sized + RingBase, R_twiddle: ?Sized + RingBase + DivisibilityRing, H: Homomorphism<R_twiddle, R_main>,

impl<R_main, R_twiddle, H, A> FFTAlgorithm<R_main> for BluesteinFFT<R_main, R_twiddle, H, A>

where R_main: ?Sized + RingBase, R_twiddle: ?Sized + RingBase + DivisibilityRing, H: Homomorphism<R_twiddle, R_main>, A: Allocator + Clone,

impl<R_main, R_twiddle, H, T1, T2> FFTAlgorithm<R_main> for CoprimeCooleyTuckeyFFT<R_main, R_twiddle, H, T1, T2>

where R_main: ?Sized + RingBase, R_twiddle: ?Sized + RingBase, H: Homomorphism<R_twiddle, R_main>, T1: FFTAlgorithm<R_main>, T2: FFTAlgorithm<R_main>,

impl<T, R: ?Sized + RingBase> FFTAlgorithm<R> for T

where T: Deref, T::Target: FFTAlgorithm<R>,