PolyTFracGCDRing

feanor_math::algorithms::poly_gcd

Trait PolyTFracGCDRing 

Source 
pub trait PolyTFracGCDRing {
    // Required methods
    fn power_decomposition<P>(poly_ring: P, poly: &El<P>) -> Vec<(El<P>, usize)>
       where P: RingStore + Copy,
             P::Type: PolyRing + DivisibilityRing,
             <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>;
    fn gcd<P>(poly_ring: P, lhs: &El<P>, rhs: &El<P>) -> El<P>
       where P: RingStore + Copy,
             P::Type: PolyRing + DivisibilityRing,
             <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>;

    // Provided methods
    fn squarefree_part<P>(poly_ring: P, poly: &El<P>) -> El<P>
       where P: RingStore + Copy,
             P::Type: PolyRing + DivisibilityRing,
             <P::Type as RingExtension>::BaseRing: RingStore<Type = Self> { ... }
    fn power_decomposition_with_controller<P, Controller>(
        poly_ring: P,
        poly: &El<P>,
        _: Controller,
    ) -> Vec<(El<P>, usize)>
       where P: RingStore + Copy,
             P::Type: PolyRing + DivisibilityRing,
             <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,
             Controller: ComputationController { ... }
    fn gcd_with_controller<P, Controller>(
        poly_ring: P,
        lhs: &El<P>,
        rhs: &El<P>,
        _: Controller,
    ) -> El<P>
       where P: RingStore + Copy,
             P::Type: PolyRing + DivisibilityRing,
             <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,
             Controller: ComputationController { ... }
}
Expand description

Trait for domain R for which there is an efficient way of computing the gcd of univariate polynomials over TFrac(R), where TFrac(R) is the total ring of fractions.

However, computations in TFrac(R) are avoided by most implementations due to performance reasons, and both inputs and outputs are polynomials over R. Despite this, the gcd is the gcd over TFrac(R) and not R (the gcd over R is often not even defined, since R does not have to be UFD).

§Example

let ZZX = DensePolyRing::new(StaticRing::<i64>::RING, "X");
let [f, g, expected] = ZZX.with_wrapped_indeterminate(|X| [X.pow_ref(2) - 2 * X + 1, X.pow_ref(2) - 1, X - 1]);
assert_el_eq!(&ZZX, expected, <_ as PolyTFracGCDRing>::gcd(&ZZX, &f, &g));

§Implementation notes

Efficient implementations for polynomial gcds are often quite complicated, since the standard euclidean algorithm is only efficient over finite fields, where no coefficient explosion happens. The general idea for other rings/fields is to reduce it to the finite case, by considering the situation modulo a finite-index ideal. The requirements for this approach are defined by the trait PolyGCDLocallyDomain, and there is a blanket impl R: PolyTFracGCDRing where R: PolyGCDLocallyDomain.

Note that this blanket impl used crate::specialization::FiniteRingSpecializable to use the standard algorithm whenever the corresponding ring is actually finite. In other words, despite the fact that the blanket implementation for PolyGCDLocallyDomains also applies to finite fields, the local implementation is not actually used in these cases.

Required Methods§

Source

fn power_decomposition<P>(poly_ring: P, poly: &El<P>) -> Vec<(El<P>, usize)>
where P: RingStore + Copy, P::Type: PolyRing + DivisibilityRing, <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,

Compute square-free polynomials f1, f2, ... such that a f = f1 f2^2 f3^3 ... for some non-zero-divisor a of this ring. They are returned as tuples (fi, i) where deg(fi) > 0.

These values are unique up to multiplication by units. If the base ring is a field, we impose the additional constraint that all fi be monic, which makes them unique.

Source

fn gcd<P>(poly_ring: P, lhs: &El<P>, rhs: &El<P>) -> El<P>
where P: RingStore + Copy, P::Type: PolyRing + DivisibilityRing, <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,

Computes the greatest common divisor of two polynomials f, g over the fraction field, which is the largest-degree polynomial d such that d | a f, a g for some non-zero-divisor a of this ring.

This value is unique up to multiplication by units. If the base ring is a field, we impose the additional constraint that it be monic, which makes it unique.

§Example
let ZZX = DensePolyRing::new(StaticRing::<i64>::RING, "X");
let [f, g, expected] = ZZX.with_wrapped_indeterminate(|X| [X.pow_ref(2) - 2 * X + 1, 2 * X.pow_ref(2) - 2, X - 1]);
// note that `expected` is not the gcd over `ZZ[X]` (which would be `2 X - 2`), but `X - 1`, i.e. the (monic) gcd over `QQ[X]`
assert_el_eq!(&ZZX, expected, <_ as PolyTFracGCDRing>::gcd(&ZZX, &f, &g));
 
// of course, the result does not have to be monic
let [f, g, expected] = ZZX.with_wrapped_indeterminate(|X| [4 * X.pow_ref(2) - 1, 4 * X.pow_ref(2) - 4 * X + 1, - 2 * X + 1]);
assert_el_eq!(&ZZX, expected, <_ as PolyTFracGCDRing>::gcd(&ZZX, &f, &g));

Provided Methods§

Source

fn squarefree_part<P>(poly_ring: P, poly: &El<P>) -> El<P>
where P: RingStore + Copy, P::Type: PolyRing + DivisibilityRing, <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>,

Computes the square-free part of a polynomial f, which is the largest-degree squarefree polynomial d such that d | a f for some non-zero-divisor a of this ring.

This value is unique up to multiplication by units. If the base ring is a field, we impose the additional constraint that it be monic, which makes it unique.

§Example
let ZZX = DensePolyRing::new(StaticRing::<i64>::RING, "X");
let [f] = ZZX.with_wrapped_indeterminate(|X| [1 - X.pow_ref(2)]);
assert_el_eq!(&ZZX, &f, <_ as PolyTFracGCDRing>::squarefree_part(&ZZX, &ZZX.mul_ref(&f, &f)));
Source

fn power_decomposition_with_controller<P, Controller>( poly_ring: P, poly: &El<P>, _: Controller, ) -> Vec<(El<P>, usize)>
where P: RingStore + Copy, P::Type: PolyRing + DivisibilityRing, <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>, Controller: ComputationController,

As PolyTFracGCDRing::power_decomposition(), this writes a polynomial as a product of powers of square-free polynomials. However, it additionally accepts a ComputationController to customize the performed computation.

Source

fn gcd_with_controller<P, Controller>( poly_ring: P, lhs: &El<P>, rhs: &El<P>, _: Controller, ) -> El<P>
where P: RingStore + Copy, P::Type: PolyRing + DivisibilityRing, <P::Type as RingExtension>::BaseRing: RingStore<Type = Self>, Controller: ComputationController,

As PolyTFracGCDRing::gcd(), this computes the gcd of two polynomials. However, it additionally accepts a ComputationController to customize the performed computation.

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§