Struct SparsePolynomial 

pub struct SparsePolynomial<F: Field, T: Term> {
    pub num_vars: usize,
    pub terms: Vec<(F, T)>,
}

Stores a sparse multivariate polynomial in coefficient form.

Fields

num_vars: usize

The number of variables the polynomial supports

terms: Vec<(F, T)>

List of each term along with its coefficient

Trait Implementations

impl<'a, F: Field, T: Term> Add<&'a SparsePolynomial<F, T>> for &SparsePolynomial<F, T>

type Output = SparsePolynomial<F, T>

The resulting type after applying the + operator.

fn add(self, other: &'a SparsePolynomial<F, T>) -> SparsePolynomial<F, T>

Performs the + operation.

impl<F: Field, T: Term> Add for SparsePolynomial<F, T>

type Output = SparsePolynomial<F, T>

The resulting type after applying the + operator.

fn add(self, other: Self) -> Self

Performs the + operation.

impl<'a, F: Field, T: Term> AddAssign<&'a SparsePolynomial<F, T>> for SparsePolynomial<F, T>

fn add_assign(&mut self, other: &'a Self)

Performs the += operation.

impl<'a, F: Field, T: Term> AddAssign<(F, &'a SparsePolynomial<F, T>)> for SparsePolynomial<F, T>

fn add_assign(&mut self, (f, other): (F, &'a Self))

Performs the += operation.

impl<F: Field, T: Term> CanonicalDeserialize for SparsePolynomial<F, T>

fn deserialize_with_mode<R: Read>( reader: R, compress: Compress, validate: Validate, ) -> Result<Self, SerializationError>

The general deserialize method that takes in customization flags.

fn deserialize_compressed<R>(reader: R) -> Result<Self, SerializationError>

where R: Read,

Reads Self from reader using the compressed form if applicable. Performs validation if applicable.

fn deserialize_compressed_unchecked<R>( reader: R, ) -> Result<Self, SerializationError>

where R: Read,

Reads Self from reader using the compressed form if applicable, without validating the deserialized value.

fn deserialize_uncompressed<R>(reader: R) -> Result<Self, SerializationError>

where R: Read,

Reads Self from reader using the uncompressed form. Performs validation if applicable.

fn deserialize_uncompressed_unchecked<R>( reader: R, ) -> Result<Self, SerializationError>

where R: Read,

Reads Self from reader using the uncompressed form, without validating the deserialized value.

impl<F: Field, T: Term> CanonicalSerialize for SparsePolynomial<F, T>

fn serialize_with_mode<W: Write>( &self, writer: W, compress: Compress, ) -> Result<(), SerializationError>

The general serialize method that takes in customization flags.

fn serialized_size(&self, compress: Compress) -> usize

Returns the size in bytes of the serialized version of self with the given compression mode.

fn serialize_compressed<W>(&self, writer: W) -> Result<(), SerializationError>

where W: Write,

Serializes self into writer using the compressed form if applicable.

fn compressed_size(&self) -> usize

Returns the size in bytes of the compressed serialized version of self.

fn serialize_uncompressed<W>(&self, writer: W) -> Result<(), SerializationError>

where W: Write,

Serializes self into writer using the uncompressed form.

fn uncompressed_size(&self) -> usize

Returns the size in bytes of the uncompressed serialized version of self.

impl<F: Field, T: Term> Clone for SparsePolynomial<F, T>

where usize: Clone, Vec<(F, T)>: Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<F: Field, T: Term> Debug for SparsePolynomial<F, T>

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

Formats the value using the given formatter.

impl<F: Field, T: Term> Default for SparsePolynomial<F, T>

where usize: Default, Vec<(F, T)>: Default,

fn default() -> Self

Returns the “default value” for a type.

impl<F: Field> DenseMVPolynomial<F> for SparsePolynomial<F, SparseTerm>

fn num_vars(&self) -> usize

Returns the number of variables in self

fn rand<R: Rng>(d: usize, l: usize, rng: &mut R) -> Self

Outputs an l-variate polynomial which is the sum of l d-degree univariate polynomials where each coefficient is sampled uniformly at random.

fn from_coefficients_vec(num_vars: usize, terms: Vec<(F, SparseTerm)>) -> Self

Constructs a new polynomial from a list of tuples of the form (coeff, Self::Term)

Examples

use ark_poly::{
    polynomial::multivariate::{SparsePolynomial, SparseTerm, Term},
    DenseMVPolynomial, Polynomial,
};
use ark_test_curves::bls12_381::Fq;

// Create a multivariate polynomial in 3 variables, with 4 terms:
// 2*x_0^3 + x_0*x_2 + x_1*x_2 + 5
let poly = SparsePolynomial::from_coefficients_vec(
    3,
    vec![
        (Fq::from(2), SparseTerm::new(vec![(0, 3)])),
        (Fq::from(1), SparseTerm::new(vec![(0, 1), (2, 1)])),
        (Fq::from(1), SparseTerm::new(vec![(1, 1), (2, 1)])),
        (Fq::from(5), SparseTerm::new(vec![])),
    ],
);

fn terms(&self) -> &[(F, Self::Term)]

Returns the terms of a self as a list of tuples of the form (coeff, Self::Term)

type Term = SparseTerm

The type of the terms of self

fn from_coefficients_slice(num_vars: usize, terms: &[(F, Self::Term)]) -> Self

Constructs a new polynomial from a list of tuples of the form (coeff, Self::Term)

impl<F: Field, T: Term> Hash for SparsePolynomial<F, T>

where usize: Hash, Vec<(F, T)>: Hash,

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<F: Field, T: Term> Neg for SparsePolynomial<F, T>

type Output = SparsePolynomial<F, T>

The resulting type after applying the - operator.

fn neg(self) -> Self

Performs the unary - operation.

impl<F: Field, T: Term> PartialEq for SparsePolynomial<F, T>

where Vec<(F, T)>: PartialEq,

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<F: Field> Polynomial<F> for SparsePolynomial<F, SparseTerm>

fn degree(&self) -> usize

Returns the total degree of the polynomial

Examples

use ark_poly::{
    polynomial::multivariate::{SparsePolynomial, SparseTerm},
    DenseMVPolynomial, Polynomial,
};
use ark_std::test_rng;
use ark_test_curves::bls12_381::Fq;

let rng = &mut test_rng();
// Create a multivariate polynomial of degree 7
let poly: SparsePolynomial<Fq, SparseTerm> = SparsePolynomial::rand(7, 2, rng);
assert_eq!(poly.degree(), 7);

fn evaluate(&self, point: &Vec<F>) -> F

Evaluates self at the given point in Self::Point.

Examples

use ark_ff::UniformRand;
use ark_poly::{
    polynomial::multivariate::{SparsePolynomial, SparseTerm, Term},
    DenseMVPolynomial, Polynomial,
};
use ark_std::test_rng;
use ark_test_curves::bls12_381::Fq;

let rng = &mut test_rng();
let poly = SparsePolynomial::rand(4, 3, rng);
let random_point = vec![Fq::rand(rng); 3];
// The result will be a single element in the field.
let result: Fq = poly.evaluate(&random_point);

type Point = Vec<F>

The type of evaluation points for this polynomial.

impl<'a, F: Field, T: Term> Sub<&'a SparsePolynomial<F, T>> for &SparsePolynomial<F, T>

type Output = SparsePolynomial<F, T>

The resulting type after applying the - operator.

fn sub(self, other: &'a SparsePolynomial<F, T>) -> SparsePolynomial<F, T>

Performs the - operation.

impl<'a, F: Field, T: Term> SubAssign<&'a SparsePolynomial<F, T>> for SparsePolynomial<F, T>

fn sub_assign(&mut self, other: &'a Self)

Performs the -= operation.

impl<F: Field, T: Term> Valid for SparsePolynomial<F, T>

const TRIVIAL_CHECK: bool

Whether the check method is trivial (i.e. always returns Ok(())). If this is true, the batch_check method will skip all checks and return Ok(()). This should be set to true for types where check is trivial, e.g. integers, field elements, etc. This is false by default. This is primarily an optimization to skip unnecessary checks in batch_check.

fn check(&self) -> Result<(), SerializationError>

Checks whether self is valid. If self is valid, returns Ok(()). Otherwise, returns an error describing the failure. This method is called by deserialize_with_mode if validate is Validate::Yes.

fn batch_check<'a>( batch: impl Iterator<Item = &'a Self> + Send, ) -> Result<(), SerializationError>

where Self: 'a,

Checks whether all items in batch are valid. If all items are valid, returns Ok(()). Otherwise, returns an error describing the first failure.

impl<F: Field, T: Term> Zero for SparsePolynomial<F, T>

fn zero() -> Self

Returns the zero polynomial.

fn is_zero(&self) -> bool

Checks if the given polynomial is zero.

fn set_zero(&mut self)

Sets self to the additive identity element of Self, 0.

impl<F: Field, T: Term> Eq for SparsePolynomial<F, T>

where Vec<(F, T)>: PartialEq,