carl  24.04
Computer ARithmetic Library
Public Member Functions | Private Types | Private Member Functions | Private Attributes
carl::EZGCD< Coeff, Ordering, Policies > Class Template Reference

Extended Zassenhaus algorithm for multivariate GCD calculation. More...

#include <EZGCD.h>

Collaboration diagram for carl::EZGCD< Coeff, Ordering, Policies >:
Collaboration graph
[legend]

Public Member Functions

 EZGCD (const MultivariatePolynomial< Coeff, Ordering, Policies > &p1, const MultivariatePolynomial< Coeff, Ordering, Policies > &p2)
 
Result calculate (bool approx=true)
 

Private Types

typedef MultivariatePolynomial< Coeff, Ordering, Policies > Polynomial
 
typedef GCDResult< Coeff, Ordering, Policies > Result
 
typedef Polynomial::TermType Term
 
typedef IntegralType< Coeff >::type Integer
 
typedef UnivariatePolynomial< MultivariatePolynomial< Coeff, Ordering, Policies > > UnivReprPol
 
typedef UnivariatePolynomial< Coeff > UnivPol
 

Private Member Functions

Variable getMainVar (const Polynomial p1, const Polynomial p2) const
 Given the two polynomials, find a suitable main variable for gcd. More...
 
Integer getPrime (const UnivReprPol &A, const UnivReprPol &B)
 
std::map< Variable, Integer > findEval (const UnivReprPol &A, const UnivReprPol &B, Integer p) const
 Find a valid evaluation point b = (b_1, ... More...
 

Private Attributes

const Polynomial & mp1
 
const Polynomial & mp2
 
PrimeFactory< Integer > mPrimeFactory
 

Detailed Description

template<typename Coeff, typename Ordering = GrLexOrdering, typename Policies = StdMultivariatePolynomialPolicies<>>
class carl::EZGCD< Coeff, Ordering, Policies >

Extended Zassenhaus algorithm for multivariate GCD calculation.

Definition at line 21 of file EZGCD.h.

Member Typedef Documentation

◆ Integer

template<typename Coeff , typename Ordering = GrLexOrdering, typename Policies = StdMultivariatePolynomialPolicies<>>
typedef IntegralType<Coeff>::type carl::EZGCD< Coeff, Ordering, Policies >::Integer
private

Definition at line 27 of file EZGCD.h.

◆ Polynomial

template<typename Coeff , typename Ordering = GrLexOrdering, typename Policies = StdMultivariatePolynomialPolicies<>>
typedef MultivariatePolynomial<Coeff,Ordering,Policies> carl::EZGCD< Coeff, Ordering, Policies >::Polynomial
private

Definition at line 24 of file EZGCD.h.

◆ Result

template<typename Coeff , typename Ordering = GrLexOrdering, typename Policies = StdMultivariatePolynomialPolicies<>>
typedef GCDResult<Coeff,Ordering,Policies> carl::EZGCD< Coeff, Ordering, Policies >::Result
private

Definition at line 25 of file EZGCD.h.

◆ Term

template<typename Coeff , typename Ordering = GrLexOrdering, typename Policies = StdMultivariatePolynomialPolicies<>>
typedef Polynomial::TermType carl::EZGCD< Coeff, Ordering, Policies >::Term
private

Definition at line 26 of file EZGCD.h.

◆ UnivPol

template<typename Coeff , typename Ordering = GrLexOrdering, typename Policies = StdMultivariatePolynomialPolicies<>>
typedef UnivariatePolynomial<Coeff> carl::EZGCD< Coeff, Ordering, Policies >::UnivPol
private

Definition at line 29 of file EZGCD.h.

◆ UnivReprPol

template<typename Coeff , typename Ordering = GrLexOrdering, typename Policies = StdMultivariatePolynomialPolicies<>>
typedef UnivariatePolynomial<MultivariatePolynomial<Coeff,Ordering,Policies> > carl::EZGCD< Coeff, Ordering, Policies >::UnivReprPol
private

Definition at line 28 of file EZGCD.h.

Constructor & Destructor Documentation

◆ EZGCD()

template<typename Coeff , typename Ordering = GrLexOrdering, typename Policies = StdMultivariatePolynomialPolicies<>>
carl::EZGCD< Coeff, Ordering, Policies >::EZGCD ( const MultivariatePolynomial< Coeff, Ordering, Policies > &  p1,
const MultivariatePolynomial< Coeff, Ordering, Policies > &  p2 
)
inline

Definition at line 37 of file EZGCD.h.

Member Function Documentation

◆ calculate()

template<typename Coeff , typename Ordering = GrLexOrdering, typename Policies = StdMultivariatePolynomialPolicies<>>
Result carl::EZGCD< Coeff, Ordering, Policies >::calculate ( bool  approx = true)
inline
Parameters
approx
Returns

Definition at line 48 of file EZGCD.h.

Here is the call graph for this function:

◆ findEval()

template<typename Coeff , typename Ordering = GrLexOrdering, typename Policies = StdMultivariatePolynomialPolicies<>>
std::map<Variable, Integer> carl::EZGCD< Coeff, Ordering, Policies >::findEval ( const UnivReprPol &  A,
const UnivReprPol &  B,
Integer  p 
) const
inlineprivate

Find a valid evaluation point b = (b_1, ...

, b_k) with 0 <= b_i < p and b_i = 0 for as many i as possible.

Parameters
APolynomial in Z[x, y_1,...,y_k]
BPolynomial in Z[x, y_1,...,y_k]
pPrime number
Returns
the evaluation point.

Definition at line 226 of file EZGCD.h.

Here is the caller graph for this function:

◆ getMainVar()

template<typename Coeff , typename Ordering = GrLexOrdering, typename Policies = StdMultivariatePolynomialPolicies<>>
Variable carl::EZGCD< Coeff, Ordering, Policies >::getMainVar ( const Polynomial  p1,
const Polynomial  p2 
) const
inlineprivate

Given the two polynomials, find a suitable main variable for gcd.

Parameters
p1
p2
Returns
NoVariable if intersection is empty, otherwise some variable v which is in p1 and p2.

Definition at line 187 of file EZGCD.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ getPrime()

template<typename Coeff , typename Ordering = GrLexOrdering, typename Policies = StdMultivariatePolynomialPolicies<>>
Integer carl::EZGCD< Coeff, Ordering, Policies >::getPrime ( const UnivReprPol &  A,
const UnivReprPol &  B 
)
inlineprivate

Definition at line 207 of file EZGCD.h.

Here is the call graph for this function:
Here is the caller graph for this function:

Field Documentation

◆ mp1

template<typename Coeff , typename Ordering = GrLexOrdering, typename Policies = StdMultivariatePolynomialPolicies<>>
const Polynomial& carl::EZGCD< Coeff, Ordering, Policies >::mp1
private

Definition at line 31 of file EZGCD.h.

◆ mp2

template<typename Coeff , typename Ordering = GrLexOrdering, typename Policies = StdMultivariatePolynomialPolicies<>>
const Polynomial& carl::EZGCD< Coeff, Ordering, Policies >::mp2
private

Definition at line 32 of file EZGCD.h.

◆ mPrimeFactory

template<typename Coeff , typename Ordering = GrLexOrdering, typename Policies = StdMultivariatePolynomialPolicies<>>
PrimeFactory<Integer> carl::EZGCD< Coeff, Ordering, Policies >::mPrimeFactory
private

Definition at line 33 of file EZGCD.h.

The documentation for this class was generated from the following file: