Trait TwoAdicSubgroupDft 

pub trait TwoAdicSubgroupDft<F: TwoAdicField>: Clone + Default {
    type Evaluations: BitReversibleMatrix<F> + 'static;

    // Required method
    fn dft_batch(&self, mat: RowMajorMatrix<F>) -> Self::Evaluations;

    // Provided methods
    fn dft(&self, vec: Vec<F>) -> Vec<F> { ... }
    fn coset_dft(&self, vec: Vec<F>, shift: F) -> Vec<F> { ... }
    fn coset_dft_batch(
        &self,
        mat: RowMajorMatrix<F>,
        shift: F,
    ) -> Self::Evaluations { ... }
    fn idft(&self, vec: Vec<F>) -> Vec<F> { ... }
    fn idft_batch(&self, mat: RowMajorMatrix<F>) -> RowMajorMatrix<F> { ... }
    fn coset_idft(&self, vec: Vec<F>, shift: F) -> Vec<F> { ... }
    fn coset_idft_batch(
        &self,
        mat: RowMajorMatrix<F>,
        shift: F,
    ) -> RowMajorMatrix<F> { ... }
    fn lde(&self, vec: Vec<F>, added_bits: usize) -> Vec<F> { ... }
    fn lde_batch(
        &self,
        mat: RowMajorMatrix<F>,
        added_bits: usize,
    ) -> Self::Evaluations { ... }
    fn coset_lde(&self, vec: Vec<F>, added_bits: usize, shift: F) -> Vec<F> { ... }
    fn coset_lde_batch(
        &self,
        mat: RowMajorMatrix<F>,
        added_bits: usize,
        shift: F,
    ) -> Self::Evaluations { ... }
    fn dft_algebra<V: BasedVectorSpace<F> + Clone + Send + Sync>(
        &self,
        vec: Vec<V>,
    ) -> Vec<V> { ... }
    fn dft_algebra_batch<V: BasedVectorSpace<F> + Clone + Send + Sync>(
        &self,
        mat: RowMajorMatrix<V>,
    ) -> RowMajorMatrix<V> { ... }
    fn coset_dft_algebra<V: BasedVectorSpace<F> + Clone + Send + Sync>(
        &self,
        vec: Vec<V>,
        shift: F,
    ) -> Vec<V> { ... }
    fn coset_dft_algebra_batch<V: BasedVectorSpace<F> + Clone + Send + Sync>(
        &self,
        mat: RowMajorMatrix<V>,
        shift: F,
    ) -> RowMajorMatrix<V> { ... }
    fn idft_algebra<V: BasedVectorSpace<F> + Clone + Send + Sync>(
        &self,
        vec: Vec<V>,
    ) -> Vec<V> { ... }
    fn idft_algebra_batch<V: BasedVectorSpace<F> + Clone + Send + Sync>(
        &self,
        mat: RowMajorMatrix<V>,
    ) -> RowMajorMatrix<V> { ... }
    fn coset_idft_algebra<V: BasedVectorSpace<F> + Clone + Send + Sync>(
        &self,
        vec: Vec<V>,
        shift: F,
    ) -> Vec<V> { ... }
    fn coset_idft_algebra_batch<V: BasedVectorSpace<F> + Clone + Send + Sync>(
        &self,
        mat: RowMajorMatrix<V>,
        shift: F,
    ) -> RowMajorMatrix<V> { ... }
    fn lde_algebra<V: BasedVectorSpace<F> + Clone + Send + Sync>(
        &self,
        vec: Vec<V>,
        added_bits: usize,
    ) -> Vec<V> { ... }
    fn lde_algebra_batch<V: BasedVectorSpace<F> + Clone + Send + Sync>(
        &self,
        mat: RowMajorMatrix<V>,
        added_bits: usize,
    ) -> RowMajorMatrix<V> { ... }
    fn coset_lde_algebra<V: BasedVectorSpace<F> + Clone + Send + Sync>(
        &self,
        vec: Vec<V>,
        added_bits: usize,
        shift: F,
    ) -> Vec<V> { ... }
    fn coset_lde_algebra_batch<V: BasedVectorSpace<F> + Clone + Send + Sync>(
        &self,
        mat: RowMajorMatrix<V>,
        added_bits: usize,
        shift: F,
    ) -> RowMajorMatrix<V> { ... }
}

This trait gives an interface for computing discrete fourier transforms (DFT’s) and their inverses over cosets of two-adic subgroups of a field F. It also contains combined methods which allow you to take the evaluation vector of a polynomial on a coset gH and extend it to a coset g'K for some possibly larger subgroup K and different shift g'.

It supports polynomials with evaluations/coefficients valued in either F or A where A is a vector space over F with specified basis. This latter case makes use of the fact that the DFT is linear meaning we can decompose an A valued polynomial into a collection of F valued polynomials, apply the DFT to each of them, and then recombine. When A is an extension field, this approach is much faster than using a TwoAdicSubgroupDft<A> implementation directly.

Most implementations of this trait are optimised for the batch case where the input is a matrix and we is a want to perform the same operation on every column. Note that depending on the width and height of the matrix (as well as whether or not you are using the parallel feature) different implementation may be faster. Hence depending on your use case you may want to be using Radix2Dit, Radix2DitParallel, RecursiveDft or Radix2Bowers.

Required Associated Types

type Evaluations: BitReversibleMatrix<F> + 'static

The matrix type used to store the result of a batched DFT operation.

This type represents a matrix of field elements, used to hold the evaluations of multiple polynomials over a two-adic subgroup or its coset. It is always owned and supports efficient access and transformation patterns used in FFT-based algorithms.

Most implementations use RowMajorMatrix<F> or a wrapper like BitReversedMatrixView<RowMajorMatrix<F>> to allow in-place bit-reversed access.

Required Methods

fn dft_batch(&self, mat: RowMajorMatrix<F>) -> Self::Evaluations

Compute the discrete Fourier transform (DFT) of each column in mat. This is the only method an implementer needs to define, all other methods can be derived from this one.

Mathematical Description

Let H denote the unique multiplicative subgroup of order mat.height(). Treating each column of mat as the coefficients of a polynomial, compute the evaluations of those polynomials on the subgroup H.

Provided Methods

fn dft(&self, vec: Vec<F>) -> Vec<F>

Compute the discrete Fourier transform (DFT) of vec.

Mathematical Description

Let H denote the unique multiplicative subgroup of order vec.len(). Treating vec as coefficients of a polynomial, compute the evaluations of that polynomial on the subgroup H.

fn coset_dft(&self, vec: Vec<F>, shift: F) -> Vec<F>

Compute the “coset DFT” of vec.

Mathematical Description

Let H denote the unique multiplicative subgroup of order vec.len(). Treating vec as coefficients of a polynomial, compute the evaluations of that polynomial on the coset shift * H.

fn coset_dft_batch(&self, mat: RowMajorMatrix<F>, shift: F) -> Self::Evaluations

Compute the “coset DFT” of each column in mat.

Mathematical Description

Let H denote the unique multiplicative subgroup of order mat.height(). Treating each column of mat as the coefficients of a polynomial, compute the evaluations of those polynomials on the coset shift * H.

fn idft(&self, vec: Vec<F>) -> Vec<F>

Compute the inverse DFT of vec.

Mathematical Description

Let H denote the unique multiplicative subgroup of order vec.len(). Treating vec as the evaluations of a polynomial on H, compute the coefficients of that polynomial.

fn idft_batch(&self, mat: RowMajorMatrix<F>) -> RowMajorMatrix<F>

Compute the inverse DFT of each column in mat.

Mathematical Description

Let H denote the unique multiplicative subgroup of order mat.height(). Treating each column of mat as the evaluations of a polynomial on H, compute the coefficients of those polynomials.

fn coset_idft(&self, vec: Vec<F>, shift: F) -> Vec<F>

Compute the “coset iDFT” of vec. This is the inverse operation of “coset DFT”.

Mathematical Description

Let H denote the unique multiplicative subgroup of order vec.len(). Treating vec as the evaluations of a polynomial on shift * H, compute the coefficients of this polynomial.

fn coset_idft_batch( &self, mat: RowMajorMatrix<F>, shift: F, ) -> RowMajorMatrix<F>

Compute the “coset iDFT” of each column in mat. This is the inverse operation of “coset DFT”.

Mathematical Description

Let H denote the unique multiplicative subgroup of order mat.height(). Treating each column of mat as the evaluations of a polynomial on shift * H, compute the coefficients of those polynomials.

fn lde(&self, vec: Vec<F>, added_bits: usize) -> Vec<F>

Compute the low-degree extension of vec onto a larger subgroup.

Mathematical Description

Let H, K denote the unique multiplicative subgroups of order vec.len() and vec.len() << added_bits, respectively. Treating vec as the evaluations of a polynomial on the subgroup H, compute the evaluations of that polynomial on the subgroup K.

There is another way to interpret this transformation which gives a larger use case. We can also view it as treating columns of mat as evaluations over a coset gH and then computing the evaluations of those polynomials on the coset gK.

fn lde_batch( &self, mat: RowMajorMatrix<F>, added_bits: usize, ) -> Self::Evaluations

Compute the low-degree extension of each column in mat onto a larger subgroup.

Mathematical Description

Let H, K denote the unique multiplicative subgroups of order mat.height() and mat.height() << added_bits, respectively. Treating each column of mat as the evaluations of a polynomial on the subgroup H, compute the evaluations of those polynomials on the subgroup K.

There is another way to interpret this transformation which gives a larger use case. We can also view it as treating columns of mat as evaluations over a coset gH and then computing the evaluations of those polynomials on the coset gK.

fn coset_lde(&self, vec: Vec<F>, added_bits: usize, shift: F) -> Vec<F>

Compute the low-degree extension of of vec onto a coset of a larger subgroup.

Mathematical Description

Let H, K denote the unique multiplicative subgroups of order vec.len() and vec.len() << added_bits, respectively. Treating vec as the evaluations of a polynomial on the subgroup H, compute the evaluations of that polynomial on the coset shift * K.

There is another way to interpret this transformation which gives a larger use case. We can also view it as treating vec as the evaluations of a polynomial over a coset gH and then computing the evaluations of that polynomial on the coset g'K where g' = g * shift.

fn coset_lde_batch( &self, mat: RowMajorMatrix<F>, added_bits: usize, shift: F, ) -> Self::Evaluations

Compute the low-degree extension of each column in mat onto a coset of a larger subgroup.

Mathematical Description

Let H, K denote the unique multiplicative subgroups of order mat.height() and mat.height() << added_bits, respectively. Treating each column of mat as the evaluations of a polynomial on the subgroup H, compute the evaluations of those polynomials on the coset shift * K.

There is another way to interpret this transformation which gives a larger use case. We can also view it as treating columns of mat as evaluations over a coset gH and then computing the evaluations of those polynomials on the coset g'K where g' = g * shift.

fn dft_algebra<V: BasedVectorSpace<F> + Clone + Send + Sync>( &self, vec: Vec<V>, ) -> Vec<V>

Compute the discrete Fourier transform (DFT) of vec.

Mathematical Description

Let H denote the unique multiplicative subgroup of order vec.len(). Treating vec as coefficients of a polynomial, compute the evaluations of that polynomial on the subgroup H.

fn dft_algebra_batch<V: BasedVectorSpace<F> + Clone + Send + Sync>( &self, mat: RowMajorMatrix<V>, ) -> RowMajorMatrix<V>

Compute the discrete Fourier transform (DFT) of each column in mat.

Mathematical Description

Let H denote the unique multiplicative subgroup of order mat.height(). Treating each column of mat as the coefficients of a polynomial, compute the evaluations of those polynomials on the subgroup H.

fn coset_dft_algebra<V: BasedVectorSpace<F> + Clone + Send + Sync>( &self, vec: Vec<V>, shift: F, ) -> Vec<V>

Compute the “coset DFT” of vec.

Mathematical Description

Let H denote the unique multiplicative subgroup of order vec.len(). Treating vec as coefficients of a polynomial, compute the evaluations of that polynomial on the coset shift * H.

fn coset_dft_algebra_batch<V: BasedVectorSpace<F> + Clone + Send + Sync>( &self, mat: RowMajorMatrix<V>, shift: F, ) -> RowMajorMatrix<V>

Compute the “coset DFT” of each column in mat.

Mathematical Description

Let H denote the unique multiplicative subgroup of order mat.height(). Treating each column of mat as the coefficients of a polynomial, compute the evaluations of those polynomials on the coset shift * H.

fn idft_algebra<V: BasedVectorSpace<F> + Clone + Send + Sync>( &self, vec: Vec<V>, ) -> Vec<V>

Compute the inverse DFT of vec.

Mathematical Description

Let H denote the unique multiplicative subgroup of order vec.len(). Treating vec as the evaluations of a polynomial on H, compute the coefficients of that polynomial.

fn idft_algebra_batch<V: BasedVectorSpace<F> + Clone + Send + Sync>( &self, mat: RowMajorMatrix<V>, ) -> RowMajorMatrix<V>

Compute the inverse DFT of each column in mat.

Mathematical Description

Let H denote the unique multiplicative subgroup of order mat.height(). Treating each column of mat as the evaluations of a polynomial on H, compute the coefficients of those polynomials.

fn coset_idft_algebra<V: BasedVectorSpace<F> + Clone + Send + Sync>( &self, vec: Vec<V>, shift: F, ) -> Vec<V>

Compute the “coset iDFT” of vec. This is the inverse operation of “coset DFT”.

Mathematical Description

Let H denote the unique multiplicative subgroup of order vec.len(). Treating vec as the evaluations of a polynomial on shift * H, compute the coefficients of this polynomial.

fn coset_idft_algebra_batch<V: BasedVectorSpace<F> + Clone + Send + Sync>( &self, mat: RowMajorMatrix<V>, shift: F, ) -> RowMajorMatrix<V>

Compute the “coset iDFT” of each column in mat. This is the inverse operation of “coset DFT”.

Mathematical Description

Let H denote the unique multiplicative subgroup of order mat.height(). Treating each column of mat as the evaluations of a polynomial on shift * H, compute the coefficients of those polynomials.

fn lde_algebra<V: BasedVectorSpace<F> + Clone + Send + Sync>( &self, vec: Vec<V>, added_bits: usize, ) -> Vec<V>

Compute the low-degree extension of vec onto a larger subgroup.

Mathematical Description

Let H, K denote the unique multiplicative subgroups of order vec.len() and vec.len() << added_bits, respectively. Treating vec as the evaluations of a polynomial on the subgroup H, compute the evaluations of that polynomial on the subgroup K.

There is another way to interpret this transformation which gives a larger use case. We can also view it as treating columns of mat as evaluations over a coset gH and then computing the evaluations of those polynomials on the coset gK.

fn lde_algebra_batch<V: BasedVectorSpace<F> + Clone + Send + Sync>( &self, mat: RowMajorMatrix<V>, added_bits: usize, ) -> RowMajorMatrix<V>

Compute the low-degree extension of each column in mat onto a larger subgroup.

Mathematical Description

Let H, K denote the unique multiplicative subgroups of order mat.height() and mat.height() << added_bits, respectively. Treating each column of mat as the evaluations of a polynomial on the subgroup H, compute the evaluations of those polynomials on the subgroup K.

There is another way to interpret this transformation which gives a larger use case. We can also view it as treating columns of mat as evaluations over a coset gH and then computing the evaluations of those polynomials on the coset gK.

fn coset_lde_algebra<V: BasedVectorSpace<F> + Clone + Send + Sync>( &self, vec: Vec<V>, added_bits: usize, shift: F, ) -> Vec<V>

Compute the low-degree extension of of vec onto a coset of a larger subgroup.

Mathematical Description

Let H, K denote the unique multiplicative subgroups of order vec.len() and vec.len() << added_bits, respectively. Treating vec as the evaluations of a polynomial on the subgroup H, compute the evaluations of that polynomial on the coset shift * K.

There is another way to interpret this transformation which gives a larger use case. We can also view it as treating vec as the evaluations of a polynomial over a coset gH and then computing the evaluations of that polynomial on the coset g'K where g' = g * shift.

fn coset_lde_algebra_batch<V: BasedVectorSpace<F> + Clone + Send + Sync>( &self, mat: RowMajorMatrix<V>, added_bits: usize, shift: F, ) -> RowMajorMatrix<V>

Compute the low-degree extension of each column in mat onto a coset of a larger subgroup.

Mathematical Description

Let H, K denote the unique multiplicative subgroups of order mat.height() and mat.height() << added_bits, respectively. Treating each column of mat as the evaluations of a polynomial on the subgroup H, compute the evaluations of those polynomials on the coset shift * K.

There is another way to interpret this transformation which gives a larger use case. We can also view it as treating columns of mat as evaluations over a coset gH and then computing the evaluations of those polynomials on the coset g'K where g' = g * shift.

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl<F> TwoAdicSubgroupDft<F> for Radix2DFTSmallBatch<F>

where F: TwoAdicField,

type Evaluations = DenseMatrix<F>

impl<F: TwoAdicField + Ord> TwoAdicSubgroupDft<F> for Radix2DitParallel<F>

type Evaluations = RowIndexMappedView<BitReversalPerm, DenseMatrix<F>>

impl<F: TwoAdicField> TwoAdicSubgroupDft<F> for NaiveDft

type Evaluations = DenseMatrix<F>

impl<F: TwoAdicField> TwoAdicSubgroupDft<F> for Radix2Bowers

type Evaluations = DenseMatrix<F>

impl<F: TwoAdicField> TwoAdicSubgroupDft<F> for Radix2Dit<F>

type Evaluations = DenseMatrix<F>