Struct feanor_math::rings::poly::sparse_poly::SparsePolyRingBase

pub struct SparsePolyRingBase<R: RingStore> { /* private fields */ }

The univariate polynomial ring R[X]. Polynomials are stored as sparse vectors of coefficients, thus giving improved performance in the case that most coefficients are zero.

Example

 
let ZZ = StaticRing::<i32>::RING;
let P = SparsePolyRing::new(ZZ, "X");
let x10_plus_1 = P.add(P.pow(P.indeterminate(), 10), P.int_hom().map(1));
let power = P.pow(x10_plus_1, 10);
assert_eq!(0, *P.coefficient_at(&power, 1));

This ring has a CanIsoFromTo to dense_poly::DensePolyRingBase.

 
let ZZ = StaticRing::<i32>::RING;
let P = SparsePolyRing::new(ZZ, "X");
let P2 = DensePolyRing::new(ZZ, "X");
let high_power_of_x = P.pow(P.indeterminate(), 10);
assert_el_eq!(&P2, &P2.pow(P2.indeterminate(), 10), &P.can_iso(&P2).unwrap().map(high_power_of_x));

Implementations

impl<R: RingStore> SparsePolyRingBase<R>

pub fn new(base_ring: R, unknown_name: &'static str) -> Self

Trait Implementations

impl<R, P> CanHomFrom<P> for SparsePolyRingBase<R>

where R: RingStore, R::Type: CanHomFrom<<P::BaseRing as RingStore>::Type>, P: ImplGenericCanIsoFromToMarker,

type Homomorphism = <<<SparsePolyRingBase<R> as RingExtension>::BaseRing as RingStore>::Type as CanHomFrom<<<P as RingExtension>::BaseRing as RingStore>::Type>>::Homomorphism

fn has_canonical_hom(&self, from: &P) -> Option<Self::Homomorphism>

fn map_in( &self, from: &P, el: P::Element, hom: &Self::Homomorphism, ) -> Self::Element

fn map_in_ref( &self, from: &S, el: &S::Element, hom: &Self::Homomorphism, ) -> Self::Element

fn mul_assign_map_in( &self, from: &S, lhs: &mut Self::Element, rhs: S::Element, hom: &Self::Homomorphism, )

fn mul_assign_map_in_ref( &self, from: &S, lhs: &mut Self::Element, rhs: &S::Element, hom: &Self::Homomorphism, )

impl<R1, R2> CanHomFrom<SparsePolyRingBase<R1>> for SparsePolyRingBase<R2>

where R1: RingStore, R2: RingStore, R2::Type: CanHomFrom<R1::Type>,

type Homomorphism = <<R2 as RingStore>::Type as CanHomFrom<<R1 as RingStore>::Type>>::Homomorphism

fn has_canonical_hom( &self, from: &SparsePolyRingBase<R1>, ) -> Option<Self::Homomorphism>

fn map_in_ref( &self, from: &SparsePolyRingBase<R1>, el: &SparseVectorMut<Rc<R1>>, hom: &Self::Homomorphism, ) -> Self::Element

fn map_in( &self, from: &SparsePolyRingBase<R1>, el: <SparsePolyRingBase<R1> as RingBase>::Element, hom: &Self::Homomorphism, ) -> Self::Element

fn mul_assign_map_in( &self, from: &S, lhs: &mut Self::Element, rhs: S::Element, hom: &Self::Homomorphism, )

fn mul_assign_map_in_ref( &self, from: &S, lhs: &mut Self::Element, rhs: &S::Element, hom: &Self::Homomorphism, )

impl<R, P> CanIsoFromTo<P> for SparsePolyRingBase<R>

where R: RingStore, R::Type: CanIsoFromTo<<P::BaseRing as RingStore>::Type>, P: ImplGenericCanIsoFromToMarker,

type Isomorphism = <<<SparsePolyRingBase<R> as RingExtension>::BaseRing as RingStore>::Type as CanIsoFromTo<<<P as RingExtension>::BaseRing as RingStore>::Type>>::Isomorphism

fn has_canonical_iso(&self, from: &P) -> Option<Self::Isomorphism>

fn map_out( &self, from: &P, el: Self::Element, iso: &Self::Isomorphism, ) -> P::Element

impl<R1, R2> CanIsoFromTo<SparsePolyRingBase<R1>> for SparsePolyRingBase<R2>

where R1: RingStore, R2: RingStore, R2::Type: CanIsoFromTo<R1::Type>,

type Isomorphism = <<R2 as RingStore>::Type as CanIsoFromTo<<R1 as RingStore>::Type>>::Isomorphism

fn has_canonical_iso( &self, from: &SparsePolyRingBase<R1>, ) -> Option<Self::Isomorphism>

fn map_out( &self, from: &SparsePolyRingBase<R1>, el: Self::Element, iso: &Self::Isomorphism, ) -> SparseVectorMut<Rc<R1>>

impl<R: RingStore + Clone> Clone for SparsePolyRingBase<R>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<R> DivisibilityRing for SparsePolyRingBase<R>

where R: DivisibilityRingStore, R::Type: DivisibilityRing,

fn checked_left_div( &self, lhs: &Self::Element, rhs: &Self::Element, ) -> Option<Self::Element>

Checks whether there is an element x such that rhs * x = lhs, and returns it if it exists. Note that this does not have to be unique, if rhs is a left zero-divisor. In particular, this function will return any element in the ring if lhs = rhs = 0.

fn is_unit(&self, x: &Self::Element) -> bool

impl<R> EuclideanRing for SparsePolyRingBase<R>

where R: RingStore, R::Type: Field,

fn euclidean_div_rem( &self, lhs: Self::Element, rhs: &Self::Element, ) -> (Self::Element, Self::Element)

fn euclidean_deg(&self, val: &Self::Element) -> Option<usize>

fn euclidean_div( &self, lhs: Self::Element, rhs: &Self::Element, ) -> Self::Element

fn euclidean_rem( &self, lhs: Self::Element, rhs: &Self::Element, ) -> Self::Element

impl<R> PartialEq for SparsePolyRingBase<R>

where R: RingStore,

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

This method tests for self and other values to be equal, and is used by ==.

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

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

impl<R> PolyRing for SparsePolyRingBase<R>

where R: RingStore,

type TermsIterator<'a> = TermIterator<'a, R> where Self: 'a

fn indeterminate(&self) -> Self::Element

fn terms<'a>(&'a self, f: &'a Self::Element) -> TermIterator<'a, R>

fn add_assign_from_terms<I>(&self, lhs: &mut Self::Element, rhs: I)

where I: Iterator<Item = (El<Self::BaseRing>, usize)>,

fn coefficient_at<'a>( &'a self, f: &'a Self::Element, i: usize, ) -> &'a El<Self::BaseRing>

fn degree(&self, f: &Self::Element) -> Option<usize>

fn div_rem_monic( &self, lhs: Self::Element, rhs: &Self::Element, ) -> (Self::Element, Self::Element)

fn mul_assign_monomial(&self, lhs: &mut Self::Element, rhs_power: usize)

fn map_terms<P, H>(&self, from: &P, el: &P::Element, hom: &H) -> Self::Element

where P: ?Sized + PolyRing, H: Homomorphism<<P::BaseRing as RingStore>::Type, <Self::BaseRing as RingStore>::Type>,

fn evaluate<R, H>( &self, f: &Self::Element, value: &R::Element, hom: &H, ) -> R::Element

where R: ?Sized + RingBase, H: Homomorphism<<Self::BaseRing as RingStore>::Type, R>,

impl<R> PrincipalIdealRing for SparsePolyRingBase<R>

where R: RingStore, R::Type: Field,

fn extended_ideal_gen( &self, lhs: &Self::Element, rhs: &Self::Element, ) -> (Self::Element, Self::Element, Self::Element)

Computes a Bezout identity for the generator g of the ideal (lhs, rhs) as g = s * lhs + t * rhs.

fn ideal_gen(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element

Computes a generator g of the ideal (lhs, rhs) = (g), also known as greatest common divisor.

fn lcm(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element

Computes a generator of the ideal (lhs) ∩ (rhs), also known as least common multiple.

impl<R: RingStore> RingBase for SparsePolyRingBase<R>

type Element = SparseVectorMut<Rc<R>>

fn clone_el(&self, val: &Self::Element) -> Self::Element

fn add_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element)

fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element)

fn sub_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element)

fn negate_inplace(&self, lhs: &mut Self::Element)

fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element)

fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element)

fn zero(&self) -> Self::Element

fn from_int(&self, value: i32) -> Self::Element

fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool

fn is_commutative(&self) -> bool

fn is_noetherian(&self) -> bool

fn dbg<'a>(&self, value: &Self::Element, out: &mut Formatter<'a>) -> Result

fn square(&self, value: &mut Self::Element)

fn mul_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element

fn mul_assign_int(&self, lhs: &mut Self::Element, rhs: i32)

fn characteristic<I: IntegerRingStore>(&self, ZZ: &I) -> Option<El<I>>

where I::Type: IntegerRing,

Returns the characteristic of this ring as an element of the given implementation of ZZ.

fn one(&self) -> Self::Element

fn neg_one(&self) -> Self::Element

fn is_zero(&self, value: &Self::Element) -> bool

fn is_one(&self, value: &Self::Element) -> bool

fn is_neg_one(&self, value: &Self::Element) -> bool

fn is_approximate(&self) -> bool

Returns whether this ring computes with approximations to elements. This would usually be the case for rings that are based on f32 or f64, to represent real or complex numbers.

fn negate(&self, value: Self::Element) -> Self::Element

fn sub_assign(&self, lhs: &mut Self::Element, rhs: Self::Element)

fn mul_int(&self, lhs: Self::Element, rhs: i32) -> Self::Element

fn mul_int_ref(&self, lhs: &Self::Element, rhs: i32) -> Self::Element

fn sub_self_assign(&self, lhs: &mut Self::Element, rhs: Self::Element)

Computes lhs := rhs - lhs.

fn sub_self_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element)

Computes lhs := rhs - lhs.

fn add_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element

fn add_ref_fst(&self, lhs: &Self::Element, rhs: Self::Element) -> Self::Element

fn add_ref_snd(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

fn add(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element

fn sub_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element

fn sub_ref_fst(&self, lhs: &Self::Element, rhs: Self::Element) -> Self::Element

fn sub_ref_snd(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

fn sub(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element

fn mul_ref_fst(&self, lhs: &Self::Element, rhs: Self::Element) -> Self::Element

fn mul_ref_snd(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element

fn mul(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element

fn pow_gen<R: IntegerRingStore>( &self, x: Self::Element, power: &El<R>, integers: R, ) -> Self::Element

where R::Type: IntegerRing,

Raises x to the power of an arbitrary, nonnegative integer given by a custom integer ring implementation.

fn sum<I>(&self, els: I) -> Self::Element

where I: Iterator<Item = Self::Element>,

fn prod<I>(&self, els: I) -> Self::Element

where I: Iterator<Item = Self::Element>,

impl<R: RingStore> RingExtension for SparsePolyRingBase<R>

type BaseRing = R

fn base_ring<'a>(&'a self) -> &'a Self::BaseRing

fn from(&self, x: El<Self::BaseRing>) -> Self::Element

fn from_ref(&self, x: &El<Self::BaseRing>) -> Self::Element

fn mul_assign_base(&self, lhs: &mut Self::Element, rhs: &El<Self::BaseRing>)

Computes lhs := lhs * rhs, where rhs is mapped into this ring via RingExtension::from_ref(). Note that this may be faster than self.mul_assign(lhs, self.from_ref(rhs)).

impl<R> Domain for SparsePolyRingBase<R>

where R: RingStore, R::Type: Domain,

impl<R> ImplGenericCanIsoFromToMarker for SparsePolyRingBase<R>

where R: RingStore,