Module convolution

Modules

• fft
  Contains multiple implementations of computing convolutions using complex FFTs.
• karatsuba
  Contains an optimized implementation of Karatsuba’s for computing convolutions

Structs

• KaratsubaAlgorithm
  Implementation of convolutions that uses Karatsuba’s algorithm with a threshold defined by KaratsubaHint.

Constants

• STANDARD_CONVOLUTION
  Good default algorithm for computing convolutions, using Karatsuba’s algorithm with a threshold defined by KaratsubaHint.

Traits

• ConvolutionAlgorithm
  Trait for objects that can compute a convolution over some ring.
• KaratsubaHint
  Trait to allow rings to customize the parameters with which KaratsubaAlgorithm will compute convolutions over the ring.
• PreparedConvolutionAlgorithm
  Trait for convolution algorithms that can “prepare” one (or both) operands in advance by computing additional data, and then use this data to perform the actual convolution more efficiently.