Struct RecursiveDft 

pub struct RecursiveDft<F> { /* private fields */ }

Recursive DFT, decimation-in-frequency in the forward direction, decimation-in-time in the backward (inverse) direction.

Implementations

impl<MP: FieldParameters + TwoAdicData> RecursiveDft<MontyField31<MP>>

pub fn new(n: usize) -> Self

Trait Implementations

impl<F: Clone> Clone for RecursiveDft<F>

fn clone(&self) -> RecursiveDft<F>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<F: Debug> Debug for RecursiveDft<F>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<F: Default> Default for RecursiveDft<F>

fn default() -> RecursiveDft<F>

Returns the “default value” for a type.

impl<MP: MontyParameters + FieldParameters + TwoAdicData> TwoAdicSubgroupDft<MontyField31<MP>> for RecursiveDft<MontyField31<MP>>

DFT implementation that uses DIT for the inverse “backward” direction and DIF for the “forward” direction.

The API mandates that the LDE is applied column-wise on the row-major input. This is awkward for memory coherence, so the algorithm here transposes the input and operates on the rows in the typical way, then transposes back again for the output. Even for modestly large inputs, the cost of the two transposes outweighed by the improved performance from operating row-wise.

The choice of DIT for inverse and DIF for “forward” transform mean that a (coset) LDE

• IDFT / zero extend / DFT

expands to

• bit-reverse input
• invDFT DIT
  • result is in “correct” order
• coset shift and zero extend result
• DFT DIF on result
  • output is bit-reversed, as required for FRI.

Hence the only bit-reversal that needs to take place is on the input.

type Evaluations = RowIndexMappedView<BitReversalPerm, DenseMatrix<MontyField31<MP>>>

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

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

where MP: MontyParameters + FieldParameters + TwoAdicData,

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.

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

where MP: MontyParameters + FieldParameters + TwoAdicData,

Compute the inverse DFT of each column in mat.

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

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

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

Compute the discrete Fourier transform (DFT) of vec.

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

Compute the “coset DFT” of vec.

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

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

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

Compute the inverse DFT of vec.

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”.

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

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

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

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

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

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

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.

fn dft_algebra<V>(&self, vec: Vec<V>) -> Vec<V>

where V: BasedVectorSpace<F> + Clone + Send + Sync,

Compute the discrete Fourier transform (DFT) of vec.

fn dft_algebra_batch<V>(&self, mat: DenseMatrix<V>) -> DenseMatrix<V>

where V: BasedVectorSpace<F> + Clone + Send + Sync,

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

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

where V: BasedVectorSpace<F> + Clone + Send + Sync,

Compute the “coset DFT” of vec.

fn coset_dft_algebra_batch<V>( &self, mat: DenseMatrix<V>, shift: F, ) -> DenseMatrix<V>

where V: BasedVectorSpace<F> + Clone + Send + Sync,

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

fn idft_algebra<V>(&self, vec: Vec<V>) -> Vec<V>

where V: BasedVectorSpace<F> + Clone + Send + Sync,

Compute the inverse DFT of vec.

fn idft_algebra_batch<V>(&self, mat: DenseMatrix<V>) -> DenseMatrix<V>

where V: BasedVectorSpace<F> + Clone + Send + Sync,

Compute the inverse DFT of each column in mat.

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

where V: BasedVectorSpace<F> + Clone + Send + Sync,

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

fn coset_idft_algebra_batch<V>( &self, mat: DenseMatrix<V>, shift: F, ) -> DenseMatrix<V>

where V: BasedVectorSpace<F> + Clone + Send + Sync,

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

fn lde_algebra<V>(&self, vec: Vec<V>, added_bits: usize) -> Vec<V>

where V: BasedVectorSpace<F> + Clone + Send + Sync,

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

fn lde_algebra_batch<V>( &self, mat: DenseMatrix<V>, added_bits: usize, ) -> DenseMatrix<V>

where V: BasedVectorSpace<F> + Clone + Send + Sync,

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

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

where V: BasedVectorSpace<F> + Clone + Send + Sync,

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

fn coset_lde_algebra_batch<V>( &self, mat: DenseMatrix<V>, added_bits: usize, shift: F, ) -> DenseMatrix<V>

where V: BasedVectorSpace<F> + Clone + Send + Sync,

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