Trait ConvolutionAlgorithm

pub trait ConvolutionAlgorithm<R: ?Sized + RingBase> {
    type PreparedConvolutionOperand = ();

    // Required methods
    fn compute_convolution<S: RingStore<Type = R> + Copy, V1: VectorView<R::Element>, V2: VectorView<R::Element>>(
        &self,
        lhs: V1,
        rhs: V2,
        dst: &mut [R::Element],
        ring: S,
    );
    fn supports_ring<S: RingStore<Type = R> + Copy>(&self, ring: S) -> bool;

    // Provided methods
    fn prepare_convolution_operand<S, V>(
        &self,
        _val: V,
        _length_hint: Option<usize>,
        _ring: S,
    ) -> Self::PreparedConvolutionOperand
       where S: RingStore<Type = R> + Copy,
             V: VectorView<R::Element> { ... }
    fn compute_convolution_prepared<S, V1, V2>(
        &self,
        lhs: V1,
        _lhs_prep: Option<&Self::PreparedConvolutionOperand>,
        rhs: V2,
        _rhs_prep: Option<&Self::PreparedConvolutionOperand>,
        dst: &mut [R::Element],
        ring: S,
    )
       where S: RingStore<Type = R> + Copy,
             V1: VectorView<R::Element>,
             V2: VectorView<R::Element> { ... }
    fn compute_convolution_sum<'a, S, I, V1, V2>(
        &self,
        values: I,
        dst: &mut [R::Element],
        ring: S,
    )
       where S: RingStore<Type = R> + Copy,
             I: ExactSizeIterator<Item = (V1, Option<&'a Self::PreparedConvolutionOperand>, V2, Option<&'a Self::PreparedConvolutionOperand>)>,
             V1: VectorView<R::Element>,
             V2: VectorView<R::Element>,
             Self: 'a,
             R: 'a { ... }
}

Trait for objects that can compute a convolution over some ring.

Example

struct NaiveConvolution;
// we support all rings!
impl<R: ?Sized + RingBase> ConvolutionAlgorithm<R> for NaiveConvolution {
    fn compute_convolution<S: RingStore<Type = R>, V1: VectorView<R::Element>, V2: VectorView<R::Element>>(&self, lhs: V1, rhs: V2, dst: &mut [R::Element], ring: S) {
        for i in 0..(lhs.len() + rhs.len() - 1) {
            for j in max(0, i as isize - rhs.len() as isize + 1)..min(lhs.len() as isize, i as isize + 1) {
                ring.add_assign(&mut dst[i], ring.mul_ref(lhs.at(j as usize), rhs.at(i - j as usize)));
            }
        }
    }
    fn supports_ring<S: RingStore<Type = R>>(&self, _: S) -> bool
        where S: Copy
    { true }
}
let lhs = [1, 2, 3, 4, 5];
let rhs = [2, 3, 4, 5, 6];
let mut expected = [0; 10];
let mut actual = [0; 10];
STANDARD_CONVOLUTION.compute_convolution(lhs, rhs, &mut expected, StaticRing::<i64>::RING);
NaiveConvolution.compute_convolution(lhs, rhs, &mut actual, StaticRing::<i64>::RING);
assert_eq!(expected, actual);

Provided Associated Types

type PreparedConvolutionOperand = ()

Additional data associated to a list of ring elements, which can be used to compute a convolution where this list is one of the operands faster.

For more details, see ConvolutionAlgorithm::prepare_convolution_operand(). Note that a PreparedConvolutionOperand can only be used for convolutions with the same list of values it was created for.

Required Methods

fn compute_convolution<S: RingStore<Type = R> + Copy, V1: VectorView<R::Element>, V2: VectorView<R::Element>>( &self, lhs: V1, rhs: V2, dst: &mut [R::Element], ring: S, )

Elementwise adds the convolution of lhs and rhs to dst.

In other words, computes dst[i] += sum_j lhs[j] * rhs[i - j] for all i, where j runs through all positive integers for which lhs[j] and rhs[i - j] are defined, i.e. not out-of-bounds.

In particular, it is necessary that dst.len() >= lhs.len() + rhs.len() - 1. However, to allow for more efficient implementations, it is instead required that dst.len() >= lhs.len() + rhs.len().

Panic

Panics if dst is shorter than lhs.len() + rhs.len() - 1. May panic if dst is shorter than lhs.len() + rhs.len().

fn supports_ring<S: RingStore<Type = R> + Copy>(&self, ring: S) -> bool

Returns whether this convolution algorithm supports computations of the given ring.

Note that most algorithms will support all rings of type R. However in some cases, e.g. for finite fields, required data might only be precomputed for some moduli, and thus only these will be supported.

Provided Methods

fn prepare_convolution_operand<S, V>( &self, _val: V, _length_hint: Option<usize>, _ring: S, ) -> Self::PreparedConvolutionOperand

where S: RingStore<Type = R> + Copy, V: VectorView<R::Element>,

Takes an input list of values and computes an opaque ConvolutionAlgorithm::PreparedConvolutionOperand, which can be used to compute future convolutions with this list of values faster.

Although the ConvolutionAlgorithm::PreparedConvolutionOperand does not have any explicit reference to the list of values it was created for, passing it to ConvolutionAlgorithm::compute_convolution_prepared() with another list of values will give erroneous results.

Length-dependence when preparing a convolution

For some algorithms, different data is required to speed up the convolution with an operand, depending on the length of the other operand. For example, for FFT-based convolutions, the prepared data would consist of the Fourier transform of the list of values, zero-padded to a length that can store the complete result of the (future) convolution.

To handle this, implementations can make use of the length_hint, which - if given - should be an upper bound to the length of the output of any future convolution that uses the given operand. Alternatively, implementations are encouraged to not compute any data during ConvolutionAlgorithm::prepare_convolution_operand(), but initialize an object with interior mutability, and use it to cache data computed during ConvolutionAlgorithm::compute_convolution_prepared().

TODO: At next breaking release, remove the default implementation

Example

let ring = Zn::new(65537);
let convolution = NTTConvolution::new(ring);
let lhs = ring.elements().take(10).collect::<Vec<_>>();
let rhs = ring.elements().take(10).collect::<Vec<_>>();
// "standard" use
let mut expected = (0..19).map(|_| ring.zero()).collect::<Vec<_>>();
convolution.compute_convolution(&lhs, &rhs, &mut expected, ring);
 
// "prepared" variant
let lhs_prep = convolution.prepare_convolution_operand(&lhs, None, ring);
let rhs_prep = convolution.prepare_convolution_operand(&rhs, None, ring);
let mut actual = (0..19).map(|_| ring.zero()).collect::<Vec<_>>();
// this will now be faster than `convolution.compute_convolution()`
convolution.compute_convolution_prepared(&lhs, Some(&lhs_prep), &rhs, Some(&rhs_prep), &mut actual, ring);
println!("{:?}, {:?}", actual.iter().map(|x| ring.format(x)).collect::<Vec<_>>(), expected.iter().map(|x| ring.format(x)).collect::<Vec<_>>());
assert!(expected.iter().zip(actual.iter()).all(|(l, r)| ring.eq_el(l, r)));

fn compute_convolution_prepared<S, V1, V2>( &self, lhs: V1, _lhs_prep: Option<&Self::PreparedConvolutionOperand>, rhs: V2, _rhs_prep: Option<&Self::PreparedConvolutionOperand>, dst: &mut [R::Element], ring: S, )

where S: RingStore<Type = R> + Copy, V1: VectorView<R::Element>, V2: VectorView<R::Element>,

Elementwise adds the convolution of lhs and rhs to dst. If provided, the given prepared convolution operands are used for a faster computation.

When called with None as both the prepared convolution operands, this is exactly equivalent to ConvolutionAlgorithm::compute_convolution().

fn compute_convolution_sum<'a, S, I, V1, V2>( &self, values: I, dst: &mut [R::Element], ring: S, )

where S: RingStore<Type = R> + Copy, I: ExactSizeIterator<Item = (V1, Option<&'a Self::PreparedConvolutionOperand>, V2, Option<&'a Self::PreparedConvolutionOperand>)>, V1: VectorView<R::Element>, V2: VectorView<R::Element>, Self: 'a, R: 'a,

Computes a convolution for each tuple in the given sequence, and sums the result of each convolution to dst.

In other words, this computes dst[k] += sum_l sum_(i + j = k) values[l][i] * values[l][k]. It can be faster than calling ConvolutionAlgorithm::prepare_convolution_operand().

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<'a, R, C> ConvolutionAlgorithm<R> for C

where R: ?Sized + RingBase, C: Deref, C::Target: ConvolutionAlgorithm<R>,

type PreparedConvolutionOperand = <<C as Deref>::Target as ConvolutionAlgorithm<R>>::PreparedConvolutionOperand

impl<I, A> ConvolutionAlgorithm<I> for FFTConvolution<A>

where I: ?Sized + IntegerRing, A: Allocator + Clone,

type PreparedConvolutionOperand = PreparedConvolutionOperand<I, A>

impl<R, A> ConvolutionAlgorithm<R> for FFTConvolutionZn<A>

where R: ?Sized + ZnRing + CanHomFrom<StaticRingBase<i64>>, A: Allocator + Clone,

type PreparedConvolutionOperand = PreparedConvolutionOperand<R, A>

impl<R, I, C, A, CreateC> ConvolutionAlgorithm<R> for RNSConvolution<I, C, A, CreateC>

where I: RingStore + Clone, I::Type: IntegerRing, C: ConvolutionAlgorithm<ZnBase>, A: Allocator + Clone, CreateC: Fn(Zn) -> C, R: ?Sized + IntegerRing,

type PreparedConvolutionOperand = PreparedConvolutionOperand<R, C>

impl<R, I, C, A, CreateC> ConvolutionAlgorithm<R> for RNSConvolutionZn<I, C, A, CreateC>

where I: RingStore + Clone, I::Type: IntegerRing, C: ConvolutionAlgorithm<ZnBase>, A: Allocator + Clone, CreateC: Fn(Zn) -> C, R: ?Sized + ZnRing + CanHomFrom<I::Type>,

type PreparedConvolutionOperand = PreparedConvolutionOperand<R, C>

impl<R: ?Sized + RingBase, A: Allocator> ConvolutionAlgorithm<R> for KaratsubaAlgorithm<A>

impl<R_main, R_twiddle, H, A> ConvolutionAlgorithm<R_main> for NTTConvolution<R_main, R_twiddle, H, A>

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

type PreparedConvolutionOperand = PreparedConvolutionOperand<R_main, A>