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, 'b, F: Field, T: Term> Add<&'a SparsePolynomial<F, T>> for &'b 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: SparsePolynomial<F, T>) -> 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 SparsePolynomial<F, T>)

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 SparsePolynomial<F, T>))

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,

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

where R: Read,

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

where R: Read,

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

where R: Read,

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

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

where W: Write,

fn compressed_size(&self) -> usize

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

where W: Write,

fn uncompressed_size(&self) -> usize

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

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

fn clone(&self) -> Self

Returns a copy 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) -> SparsePolynomial<F, T>

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, 'b, F: Field, T: Term> Sub<&'a SparsePolynomial<F, T>> for &'b 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 SparsePolynomial<F, T>)

Performs the -= operation.

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

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

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

where Self: 'a,

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,