Trait BasedVectorSpace

Source

pub trait BasedVectorSpace<F: PrimeCharacteristicRing>: Sized {
    const DIMENSION: usize;

    // Required methods
    fn as_basis_coefficients_slice(&self) -> &[F];
    fn from_basis_coefficients_fn<Fn: FnMut(usize) -> F>(f: Fn) -> Self;
    fn from_basis_coefficients_iter<I: ExactSizeIterator<Item = F>>(
        iter: I,
    ) -> Option<Self>;

    // Provided methods
    fn from_basis_coefficients_slice(slice: &[F]) -> Option<Self> { ... }
    fn ith_basis_element(i: usize) -> Option<Self> { ... }
    fn flatten_to_base(vec: Vec<Self>) -> Vec<F> { ... }
    fn reconstitute_from_base(vec: Vec<F>) -> Vec<Self>
       where F: Sync,
             Self: Send { ... }
}

Expand description

A vector space V over F with a fixed basis. Fixing the basis allows elements of V to be converted to and from DIMENSION many elements of F which are interpreted as basis coefficients.

We usually expect F to be a field but do not enforce this and so allow it to be just a ring. This lets every ring implement BasedVectorSpace<Self> and is useful in a couple of other cases.

§Safety

We make no guarantees about consistency of the choice of basis across different versions of Plonky3. If this choice of basis changes, the behaviour of BasedVectorSpace will also change. Due to this, we recommend avoiding using this trait unless absolutely necessary.

§Mathematical Description

Given a vector space, A over F, a basis is a set of elements B = {b_0, ..., b_{n-1}} in A such that, given any element a, we can find a unique set of n elements of F, f_0, ..., f_{n - 1} satisfying a = f_0 b_0 + ... + f_{n - 1} b_{n - 1}. Thus the choice of B gives rise to a natural linear map between the vector space A and the canonical n dimensional vector space F^n.

This allows us to map between elements of A and arrays of n elements of F. Clearly this map depends entirely on the choice of basis B which may change across versions of Plonky3.

The situation is slightly more complicated in cases where F is not a field but boils down to an identical description once we enforce that A is a free module over F.

Required Associated Constants§

Source

const DIMENSION: usize

The dimension of the vector space, i.e. the number of elements in its basis.

Required Methods§

Source

fn as_basis_coefficients_slice(&self) -> &[F]

Fixes a basis for the algebra A and uses this to map an element of A to a slice of DIMENSION F elements.

§Safety

The value produced by this function fundamentally depends on the choice of basis. Care must be taken to ensure portability if these values might ever be passed to (or rederived within) another compilation environment where a different basis might have been used.

Source

fn from_basis_coefficients_fn<Fn: FnMut(usize) -> F>(f: Fn) -> Self

Fixes a basis for the algebra A and uses this to map DIMENSION F elements to an element of A. Similar to core:array::from_fn, the DIMENSION F elements are given by Fn(0), ..., Fn(DIMENSION - 1) called in that order.

§Safety

The value produced by this function fundamentally depends on the choice of basis. Care must be taken to ensure portability if these values might ever be passed to (or rederived within) another compilation environment where a different basis might have been used.

Source

fn from_basis_coefficients_iter<I: ExactSizeIterator<Item = F>>( iter: I, ) -> Option<Self>

Fixes a basis for the algebra A and uses this to map DIMENSION F elements to an element of A.

§Safety

The value produced by this function fundamentally depends on the choice of basis. Care must be taken to ensure portability if these values might ever be passed to (or rederived within) another compilation environment where a different basis might have been used.

Returns None if the length of the iterator is different to DIMENSION.

Provided Methods§

Source

fn from_basis_coefficients_slice(slice: &[F]) -> Option<Self>

Fixes a basis for the algebra A and uses this to map DIMENSION F elements to an element of A.

§Safety

The value produced by this function fundamentally depends on the choice of basis. Care must be taken to ensure portability if these values might ever be passed to (or rederived within) another compilation environment where a different basis might have been used.

Returns None if the length of the slice is different to DIMENSION.

Source

fn ith_basis_element(i: usize) -> Option<Self>

Given a basis for the Algebra A, return the i’th basis element.

§Safety

The value produced by this function fundamentally depends on the choice of basis. Care must be taken to ensure portability if these values might ever be passed to (or rederived within) another compilation environment where a different basis might have been used.

Returns None if i is greater than or equal to DIMENSION.

Source

fn flatten_to_base(vec: Vec<Self>) -> Vec<F>

Convert from a vector of Self to a vector of F by flattening the basis coefficients.

Depending on the BasedVectorSpace this may be essentially a no-op and should certainly be reimplemented in those cases.

§Safety

The value produced by this function fundamentally depends on the choice of basis. Care must be taken to ensure portability if these values might ever be passed to (or rederived within) another compilation environment where a different basis might have been used.

Source

fn reconstitute_from_base(vec: Vec<F>) -> Vec<Self>
where F: Sync, Self: Send,

Convert from a vector of F to a vector of Self by combining the basis coefficients.

Depending on the BasedVectorSpace this may be essentially a no-op and should certainly be reimplemented in those cases.

§Panics

This will panic if the length of vec is not a multiple of Self::DIMENSION.

§Safety

The value produced by this function fundamentally depends on the choice of basis. Care must be taken to ensure portability if these values might ever be passed to (or rederived within) another compilation environment where a different basis might have been used.