Struct Radix2DFTSmallBatch 

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

An FFT algorithm which divides a butterfly network’s layers into two halves.

Unlike other FFT algorithms, this algorithm is optimized for small batch sizes. It also stores its twiddle factors and only re-computes if it is asked to do a larger FFT.

Instead of parallelizing across rows, this algorithm parallelizes across groups of rows with the same twiddle factors. This allows it to make use of field packings far more than the standard methods even for low width matrices. Once the chunk size is small enough, it computes a large set of layers fully on a single thread, which avoids the overhead of passing data between threads.

Implementations

impl<F: TwoAdicField> Radix2DFTSmallBatch<F>

pub fn new(n: usize) -> Self

Create a new Radix2DFTSmallBatch instance with precomputed twiddles for the given size.

The input n should be a power of two, representing the maximal FFT size you expect to handle.

Trait Implementations

impl<F: Clone> Clone for Radix2DFTSmallBatch<F>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<F: Debug> Debug for Radix2DFTSmallBatch<F>

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

Formats the value using the given formatter.

impl<F: Default> Default for Radix2DFTSmallBatch<F>

fn default() -> Radix2DFTSmallBatch<F>

Returns the “default value” for a type.

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

where F: TwoAdicField,

type Evaluations = DenseMatrix<F>

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

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.

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

Compute the inverse DFT of each column in mat.

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.

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: RowMajorMatrix<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: RowMajorMatrix<F>, shift: F, ) -> RowMajorMatrix<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: RowMajorMatrix<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: BasedVectorSpace<F> + Clone + Send + Sync>( &self, vec: Vec<V>, ) -> Vec<V>

Compute the discrete Fourier transform (DFT) of vec.

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.

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

Compute the “coset DFT” of vec.

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.

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

Compute the inverse DFT of vec.

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.

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

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

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.

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.

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.

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.