My Project
Loading...
Searching...
No Matches
factory.h File Reference

‘factory.h’ is the user interface to Factory. More...

Go to the source code of this file.

Data Structures

class  Variable
 factory's class for variables More...
 
class  CanonicalForm
 factory's main class More...
 
class  Evaluation
 class to evaluate a polynomial at points More...
 
class  CFGenerator
 virtual class for generators More...
 
class  IntGenerator
 generate integers starting from 0 More...
 
class  FFGenerator
 generate all elements in F_p starting from 0 More...
 
class  GFGenerator
 generate all elements in GF starting from 0 More...
 
class  AlgExtGenerator
 generate all elements in F_p(alpha) starting from 0 More...
 
class  CFGenFactory
 
class  CFIterator
 class to iterate through CanonicalForm's More...
 
class  CFRandom
 virtual class for random element generation More...
 
class  GFRandom
 generate random elements in GF More...
 
class  FFRandom
 generate random elements in F_p More...
 
class  IntRandom
 generate random integers More...
 
class  AlgExtRandomF
 generate random elements in F_p(alpha) More...
 
class  CFRandomFactory
 
class  modpk
 class to do operations mod p^k for int's p and k More...
 
class  MapPair
 class MapPair More...
 
class  CFMap
 class CFMap More...
 
class  REvaluation
 class to generate random evaluation points More...
 
class  StoreFactors
 class to store factors that get removed during char set computation More...
 

Macros

#define OSTREAM   std::ostream
 
#define ISTREAM   std::istream
 
#define LEVELBASE   -1000000
 
#define LEVELTRANS   -500000
 
#define LEVELQUOT   1000000
 
#define LEVELEXPR   1000001
 
#define CF_INLINE
 
#define CF_NO_INLINE
 
#define CF_INLINE
 
#define CF_NO_INLINE
 

Typedefs

typedef AFactor< CanonicalFormCFAFactor
 
typedef List< CFAFactorCFAFList
 
typedef ListIterator< CFAFactorCFAFListIterator
 
typedef Factor< CanonicalFormCFFactor
 
typedef List< CFFactorCFFList
 
typedef ListIterator< CFFactorCFFListIterator
 
typedef List< CanonicalFormCFList
 
typedef ListIterator< CanonicalFormCFListIterator
 
typedef Array< CanonicalFormCFArray
 
typedef Matrix< CanonicalFormCFMatrix
 
typedef List< CFListListCFList
 
typedef ListIterator< CFListListCFListIterator
 
typedef List< int > IntList
 
typedef ListIterator< int > IntListIterator
 
typedef List< VariableVarlist
 
typedef ListIterator< VariableVarlistIterator
 
typedef Array< int > Intarray
 
typedef termtermList
 
typedef List< MapPairMPList
 
typedef ListIterator< MapPairMPListIterator
 

Functions

int FACTORY_PUBLIC cf_getPrime (int i)
 
int FACTORY_PUBLIC cf_getNumPrimes ()
 
int FACTORY_PUBLIC cf_getSmallPrime (int i)
 
int FACTORY_PUBLIC cf_getNumSmallPrimes ()
 
int FACTORY_PUBLIC cf_getBigPrime (int i)
 
int FACTORY_PUBLIC cf_getNumBigPrimes ()
 
Variable FACTORY_PUBLIC rootOf (const CanonicalForm &, char name='@')
 returns a symbolic root of polynomial with name name Use it to define algebraic variables
 
int level (const Variable &v)
 
char name (const Variable &v)
 
void setReduce (const Variable &alpha, bool reduce)
 
void setMipo (const Variable &alpha, const CanonicalForm &mipo)
 
CanonicalForm getMipo (const Variable &alpha, const Variable &x)
 
bool hasMipo (const Variable &alpha)
 
char getDefaultVarName ()
 
char getDefaultExtName ()
 
void FACTORY_PUBLIC prune (Variable &alpha)
 
void prune1 (const Variable &alpha)
 
int ExtensionLevel ()
 
int is_imm (const InternalCF *const ptr)
 
CF_INLINE FACTORY_PUBLIC CanonicalForm operator+ (const CanonicalForm &, const CanonicalForm &)
 CF_INLINE CanonicalForm operator +, -, *, /, % ( const CanonicalForm & lhs, const CanonicalForm & rhs )
 
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator- (const CanonicalForm &, const CanonicalForm &)
 
CF_INLINE FACTORY_PUBLIC CanonicalForm operator* (const CanonicalForm &, const CanonicalForm &)
 
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator/ (const CanonicalForm &, const CanonicalForm &)
 
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator% (const CanonicalForm &, const CanonicalForm &)
 
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm div (const CanonicalForm &, const CanonicalForm &)
 
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod (const CanonicalForm &, const CanonicalForm &)
 
CanonicalForm FACTORY_PUBLIC blcm (const CanonicalForm &f, const CanonicalForm &g)
 
CanonicalForm FACTORY_PUBLIC power (const CanonicalForm &f, int n)
 exponentiation
 
CanonicalForm FACTORY_PUBLIC power (const Variable &v, int n)
 exponentiation
 
CanonicalForm FACTORY_PUBLIC gcd (const CanonicalForm &, const CanonicalForm &)
 
CanonicalForm FACTORY_PUBLIC gcd_poly (const CanonicalForm &f, const CanonicalForm &g)
 CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
 
CanonicalForm FACTORY_PUBLIC lcm (const CanonicalForm &, const CanonicalForm &)
 CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )
 
CanonicalForm FACTORY_PUBLIC pp (const CanonicalForm &)
 CanonicalForm pp ( const CanonicalForm & f )
 
CanonicalForm FACTORY_PUBLIC content (const CanonicalForm &)
 CanonicalForm content ( const CanonicalForm & f )
 
CanonicalForm FACTORY_PUBLIC content (const CanonicalForm &, const Variable &)
 CanonicalForm content ( const CanonicalForm & f, const Variable & x )
 
CanonicalForm FACTORY_PUBLIC icontent (const CanonicalForm &f)
 CanonicalForm icontent ( const CanonicalForm & f )
 
CanonicalForm FACTORY_PUBLIC vcontent (const CanonicalForm &f, const Variable &x)
 CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
 
CanonicalForm FACTORY_PUBLIC swapvar (const CanonicalForm &, const Variable &, const Variable &)
 swapvar() - swap variables x1 and x2 in f.
 
CanonicalForm FACTORY_PUBLIC replacevar (const CanonicalForm &, const Variable &, const Variable &)
 CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
 
int getNumVars (const CanonicalForm &f)
 int getNumVars ( const CanonicalForm & f )
 
CanonicalForm getVars (const CanonicalForm &f)
 CanonicalForm getVars ( const CanonicalForm & f )
 
CanonicalForm apply (const CanonicalForm &f, void(*mf)(CanonicalForm &, int &))
 CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) )
 
CanonicalForm mapdomain (const CanonicalForm &f, CanonicalForm(*mf)(const CanonicalForm &))
 CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) )
 
int * degrees (const CanonicalForm &f, int *degs=0)
 int * degrees ( const CanonicalForm & f, int * degs )
 
int totaldegree (const CanonicalForm &f)
 int totaldegree ( const CanonicalForm & f )
 
int totaldegree (const CanonicalForm &f, const Variable &v1, const Variable &v2)
 int totaldegree ( const CanonicalForm & f, const Variable & v1, const Variable & v2 )
 
int size (const CanonicalForm &f, const Variable &v)
 int size ( const CanonicalForm & f, const Variable & v )
 
int size (const CanonicalForm &f)
 int size ( const CanonicalForm & f )
 
int size_maxexp (const CanonicalForm &f, int &maxexp)
 
CanonicalForm reduce (const CanonicalForm &f, const CanonicalForm &M)
 polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of f are reduced modulo M
 
bool hasFirstAlgVar (const CanonicalForm &f, Variable &a)
 check if poly f contains an algebraic variable a
 
CanonicalForm leftShift (const CanonicalForm &F, int n)
 left shift the main variable of F by n
 
CanonicalForm lc (const CanonicalForm &f)
 
CanonicalForm Lc (const CanonicalForm &f)
 
CanonicalForm LC (const CanonicalForm &f)
 
CanonicalForm LC (const CanonicalForm &f, const Variable &v)
 
int degree (const CanonicalForm &f)
 
int degree (const CanonicalForm &f, const Variable &v)
 
int taildegree (const CanonicalForm &f)
 
CanonicalForm tailcoeff (const CanonicalForm &f)
 
CanonicalForm tailcoeff (const CanonicalForm &f, const Variable &v)
 
int level (const CanonicalForm &f)
 
Variable mvar (const CanonicalForm &f)
 
CanonicalForm num (const CanonicalForm &f)
 
CanonicalForm den (const CanonicalForm &f)
 
int sign (const CanonicalForm &a)
 
CanonicalForm deriv (const CanonicalForm &f, const Variable &x)
 
CanonicalForm sqrt (const CanonicalForm &a)
 
int ilog2 (const CanonicalForm &a)
 
CanonicalForm mapinto (const CanonicalForm &f)
 
CanonicalForm head (const CanonicalForm &f)
 
int headdegree (const CanonicalForm &f)
 
void FACTORY_PUBLIC setCharacteristic (int c)
 
void setCharacteristic (int c, int n)
 
void setCharacteristic (int c, int n, char name)
 
int FACTORY_PUBLIC getCharacteristic ()
 
int getGFDegree ()
 
CanonicalForm getGFGenerator ()
 
void FACTORY_PUBLIC On (int)
 switches
 
void FACTORY_PUBLIC Off (int)
 switches
 
bool FACTORY_PUBLIC isOn (int)
 switches
 
CanonicalForm psr (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
 
CanonicalForm psq (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
 
void psqr (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, const Variable &x)
 void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable & x )
 
CanonicalForm FACTORY_PUBLIC bCommonDen (const CanonicalForm &f)
 CanonicalForm bCommonDen ( const CanonicalForm & f )
 
bool fdivides (const CanonicalForm &f, const CanonicalForm &g)
 bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
 
bool fdivides (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &quot)
 same as fdivides if true returns quotient quot of g by f otherwise quot == 0
 
bool tryFdivides (const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
 same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f
 
CanonicalForm maxNorm (const CanonicalForm &f)
 CanonicalForm maxNorm ( const CanonicalForm & f )
 
CanonicalForm euclideanNorm (const CanonicalForm &f)
 CanonicalForm euclideanNorm ( const CanonicalForm & f )
 
void FACTORY_PUBLIC chineseRemainder (const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
 void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew )
 
void FACTORY_PUBLIC chineseRemainder (const CFArray &x, const CFArray &q, CanonicalForm &xnew, CanonicalForm &qnew)
 void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew )
 
void FACTORY_PUBLIC chineseRemainderCached (const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew, CFArray &inv)
 
void FACTORY_PUBLIC chineseRemainderCached (const CFArray &a, const CFArray &n, CanonicalForm &xnew, CanonicalForm &prod, CFArray &inv)
 
CanonicalForm Farey (const CanonicalForm &f, const CanonicalForm &q)
 Farey rational reconstruction.
 
bool isPurePoly (const CanonicalForm &f)
 
bool isPurePoly_m (const CanonicalForm &f)
 
CFFList FACTORY_PUBLIC factorize (const CanonicalForm &f, bool issqrfree=false)
 factorization over $ F_p $ or $ Q $
 
CFFList FACTORY_PUBLIC factorize (const CanonicalForm &f, const Variable &alpha)
 factorization over $ F_p(\alpha) $ or $ Q(\alpha) $
 
CFFList FACTORY_PUBLIC sqrFree (const CanonicalForm &f, bool sort=false)
 squarefree factorization
 
CanonicalForm homogenize (const CanonicalForm &f, const Variable &x)
 homogenize homogenizes f with Variable x
 
CanonicalForm homogenize (const CanonicalForm &f, const Variable &x, const Variable &v1, const Variable &v2)
 
Variable get_max_degree_Variable (const CanonicalForm &f)
 get_max_degree_Variable returns Variable with highest degree.
 
CFList get_Terms (const CanonicalForm &f)
 
void getTerms (const CanonicalForm &f, const CanonicalForm &t, CFList &result)
 get_Terms: Split the polynomial in the containing terms.
 
bool linearSystemSolve (CFMatrix &M)
 
CanonicalForm FACTORY_PUBLIC determinant (const CFMatrix &M, int n)
 
CFArray subResChain (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
 
CanonicalForm FACTORY_PUBLIC resultant (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
 
CanonicalForm abs (const CanonicalForm &f)
 inline CanonicalForm abs ( const CanonicalForm & f )
 
int factoryrandom (int n)
 random integers with abs less than n
 
void FACTORY_PUBLIC factoryseed (int s)
 random seed initializer
 
CanonicalForm replaceLc (const CanonicalForm &f, const CanonicalForm &c)
 
CanonicalForm compress (const CanonicalForm &f, CFMap &m)
 CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
 
void compress (const CFArray &a, CFMap &M, CFMap &N)
 void compress ( const CFArray & a, CFMap & M, CFMap & N )
 
void compress (const CanonicalForm &f, const CanonicalForm &g, CFMap &M, CFMap &N)
 void compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N )
 
long gf_gf2ff (long a)
 
int gf_gf2ff (int a)
 
bool gf_isff (long a)
 
bool gf_isff (int a)
 
CFMatrixcf_HNF (CFMatrix &A)
 The input matrix A is square matrix of integers output: the Hermite Normal Form of A; that is, the unique m x m matrix whose rows span L, such that.
 
CFMatrixcf_LLL (CFMatrix &A)
 performs LLL reduction.
 
void FACTORY_PUBLIC gmp_numerator (const CanonicalForm &f, mpz_ptr result)
 
void FACTORY_PUBLIC gmp_denominator (const CanonicalForm &f, mpz_ptr result)
 
int gf_value (const CanonicalForm &f)
 
CanonicalForm FACTORY_PUBLIC make_cf (const mpz_ptr n)
 
CanonicalForm FACTORY_PUBLIC make_cf (const mpz_ptr n, const mpz_ptr d, bool normalize)
 
CanonicalForm make_cf_from_gf (const int z)
 
int igcd (int a, int b)
 
int FACTORY_PUBLIC ipower (int b, int n)
 int ipower ( int b, int m )
 
void factoryError_intern (const char *s)
 
int FACTORY_PUBLIC probIrredTest (const CanonicalForm &F, double error)
 given some error probIrredTest detects irreducibility or reducibility of F with confidence level 1-error
 
CFAFList FACTORY_PUBLIC absFactorize (const CanonicalForm &G)
 absolute factorization of a multivariate poly over Q
 
CanonicalForm resultantZ (const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob=true)
 modular resultant algorihtm over Z
 
CFFList facAlgFunc2 (const CanonicalForm &f, const CFList &as)
 factorize a polynomial f that is irreducible over the ground field modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $.
 
CFFList facAlgFunc (const CanonicalForm &f, const CFList &as)
 factorize a polynomial f modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $.
 
CanonicalForm Prem (const CanonicalForm &F, const CanonicalForm &G)
 pseudo remainder of F by G with certain factors of LC (g) cancelled
 
CFList basicSet (const CFList &PS)
 basic set in the sense of Wang a.k.a. minimal ascending set in the sense of Greuel/Pfister
 
CFList charSet (const CFList &PS)
 characteristic set
 
CFList modCharSet (const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true)
 modified medial set
 
CFList modCharSet (const CFList &PS, bool removeContents)
 
CFList charSetViaCharSetN (const CFList &PS)
 compute a characteristic set via medial set
 
CFList charSetN (const CFList &PS)
 medial set
 
CFList charSetViaModCharSet (const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true)
 modified characteristic set, i.e. a characteristic set with certain factors removed
 
CFList charSetViaModCharSet (const CFList &PS, bool removeContents=true)
 modified characteristic set, i.e. a characteristic set with certain factors removed
 
ListCFList charSeries (const CFList &L)
 characteristic series
 
ListCFList FACTORY_PUBLIC irrCharSeries (const CFList &PS)
 irreducible characteristic series
 
Varlist neworder (const CFList &PolyList)
 
CFList newordercf (const CFList &PolyList)
 
IntList FACTORY_PUBLIC neworderint (const CFList &PolyList)
 
CFList reorder (const Varlist &betterorder, const CFList &PS)
 
CFFList reorder (const Varlist &betterorder, const CFFList &PS)
 
ListCFList reorder (const Varlist &betterorder, const ListCFList &Q)
 
CanonicalForm FACTORY_PUBLIC extgcd (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
 CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b )
 

Variables

const char factoryConfiguration []
 
static const int SW_RATIONAL = 0
 set to 1 for computations over Q
 
static const int SW_SYMMETRIC_FF = 1
 set to 1 for symmetric representation over F_q
 
static const int SW_USE_EZGCD = 2
 set to 1 to use EZGCD over Z
 
static const int SW_USE_EZGCD_P = 3
 set to 1 to use EZGCD over F_q
 
static const int SW_USE_NTL_SORT =4
 set to 1 to sort factors in a factorization
 
static const int SW_USE_CHINREM_GCD =5
 set to 1 to use modular gcd over Z
 
static const int SW_USE_QGCD =6
 set to 1 to use Encarnacion GCD over Q(a)
 
static const int SW_USE_FF_MOD_GCD =7
 set to 1 to use modular GCD over F_q
 
static const int SW_USE_FL_GCD_P =8
 set to 1 to use Flints gcd over F_p
 
static const int SW_USE_FL_GCD_0 =9
 set to 1 to use Flints gcd over Q/Z
 
static const int SW_BERLEKAMP =10
 set to 1 to use Factorys Berlekamp alg.
 
static const int SW_FAC_QUADRATICLIFT =11
 
static const int SW_USE_FL_FAC_P =12
 set to 1 to prefer flints multivariate factorization over Z/p
 
static const int SW_USE_FL_FAC_0 =13
 set to 1 to prefer flints multivariate factorization over Z/p
 
static const int SW_USE_FL_FAC_0A =14
 set to 1 to prefer flints multivariate factorization over Z/p(a)
 
EXTERN_VAR int singular_homog_flag
 
EXTERN_VAR void(* factoryError )(const char *s)
 

Detailed Description

‘factory.h’ is the user interface to Factory.

Created automatically by ‘makeheader’, it collects all important declarations from all important Factory header files into one overall header file leaving out all boring Factory internal stuff. See ‘./bin/makeheader’ for an explanation of the syntax of this file.

Note: In this file the order of "includes" matters (since this are not real includes)! In general, files at the end depend on files at the beginning.

Definition in file factory.h.

Macro Definition Documentation

◆ CF_INLINE [1/2]

#define CF_INLINE

Definition at line 208 of file factory.h.

◆ CF_INLINE [2/2]

#define CF_INLINE

Definition at line 208 of file factory.h.

◆ CF_NO_INLINE [1/2]

#define CF_NO_INLINE

Definition at line 210 of file factory.h.

◆ CF_NO_INLINE [2/2]

#define CF_NO_INLINE

Definition at line 210 of file factory.h.

◆ ISTREAM

#define ISTREAM   std::istream

Definition at line 41 of file factory.h.

◆ LEVELBASE

#define LEVELBASE   -1000000

Definition at line 82 of file factory.h.

◆ LEVELEXPR

#define LEVELEXPR   1000001

Definition at line 85 of file factory.h.

◆ LEVELQUOT

#define LEVELQUOT   1000000

Definition at line 84 of file factory.h.

◆ LEVELTRANS

#define LEVELTRANS   -500000

Definition at line 83 of file factory.h.

◆ OSTREAM

#define OSTREAM   std::ostream

Definition at line 40 of file factory.h.

Typedef Documentation

◆ CFAFactor

Definition at line 530 of file factory.h.

◆ CFAFList

Definition at line 531 of file factory.h.

◆ CFAFListIterator

Definition at line 532 of file factory.h.

◆ CFArray

Definition at line 538 of file factory.h.

◆ CFFactor

Definition at line 533 of file factory.h.

◆ CFFList

typedef List<CFFactor> CFFList

Definition at line 534 of file factory.h.

◆ CFFListIterator

Definition at line 535 of file factory.h.

◆ CFList

Definition at line 536 of file factory.h.

◆ CFListIterator

Definition at line 537 of file factory.h.

◆ CFMatrix

Definition at line 539 of file factory.h.

◆ Intarray

typedef Array<int> Intarray

Definition at line 546 of file factory.h.

◆ IntList

typedef List<int> IntList

Definition at line 542 of file factory.h.

◆ IntListIterator

Definition at line 543 of file factory.h.

◆ ListCFList

Definition at line 540 of file factory.h.

◆ ListCFListIterator

Definition at line 541 of file factory.h.

◆ MPList

typedef List<MapPair> MPList

Definition at line 986 of file factory.h.

◆ MPListIterator

Definition at line 987 of file factory.h.

◆ termList

typedef term* termList

Definition at line 799 of file factory.h.

◆ Varlist

typedef List<Variable> Varlist

Definition at line 544 of file factory.h.

◆ VarlistIterator

Definition at line 545 of file factory.h.

Function Documentation

◆ abs()

CanonicalForm abs ( const CanonicalForm & f)
inline

inline CanonicalForm abs ( const CanonicalForm & f )

abs() - return absolute value of ‘f’.

The absolute value is defined in terms of the function ‘sign()’. If it reports negative sign for ‘f’ than -‘f’ is returned, otherwise ‘f’.

This behaviour is most useful for integers and rationals. But it may be used to sign-normalize the leading coefficient of arbitrary polynomials, too.

Type info:

f: CurrentPP

Definition at line 638 of file factory.h.

639{
640 // it is not only more general to use `sign()' instead of a
641 // direct comparison `f < 0', it is faster, too
642 if ( sign( f ) < 0 )
643 return -f;
644 else
645 return f;
646}
FILE * f
Definition checklibs.c:9
int sign(const CanonicalForm &a)
Definition factory.h:484

◆ absFactorize()

absolute factorization of a multivariate poly over Q

Returns
absFactorize returns a list whose entries contain three entities: an absolute irreducible factor, an irreducible univariate polynomial that defines the minimal field extension over which the irreducible factor is defined (note: in case the factor is already defined over Q[t]/(t), 1 is returned), and the multiplicity of the absolute irreducible factor
Parameters
[in]Gpoly over Q

Definition at line 262 of file facAbsFact.cc.

264{
265 //TODO handle homogeneous input, is already done in LIB interface but still...
266 ASSERT (getCharacteristic() == 0, "expected poly over Q");
267
268 CanonicalForm F= G;
269
270 CanonicalForm LcF= Lc (F);
271 bool isRat= isOn (SW_RATIONAL);
272 if (isRat)
273 F *= bCommonDen (F);
274
276 F /= icontent (F);
277 if (isRat)
278 On (SW_RATIONAL);
279
280 CFFList rationalFactors= factorize (F);
281
282 CFAFList result, resultBuf;
283
285 CFFListIterator i= rationalFactors;
286 i++;
287 for (; i.hasItem(); i++)
288 {
289 resultBuf= absFactorizeMain (i.getItem().factor());
290 for (iter= resultBuf; iter.hasItem(); iter++)
291 iter.getItem()= CFAFactor (iter.getItem().factor(),
292 iter.getItem().minpoly(), i.getItem().exp());
293 result= Union (result, resultBuf);
294 }
295
296 if (isRat)
298 result.insert (CFAFactor (LcF, 1, 1));
299
300 return result;
301}
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
AFactor< CanonicalForm > CFAFactor
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition cf_gcd.cc:74
ListIterator< CFAFactor > CFAFListIterator
ListIterator< CFFactor > CFFListIterator
List< CFFactor > CFFList
CanonicalForm Lc(const CanonicalForm &f)
List< CFAFactor > CFAFList
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
int i
Definition cfEzgcd.cc:132
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
#define ASSERT(expression, message)
Definition cf_assert.h:99
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
factory's main class
CFFListIterator iter
CanonicalForm LcF
return result
CFAFList absFactorizeMain(const CanonicalForm &G)
main absolute factorization routine, expects poly which is irreducible over Q
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
STATIC_VAR TreeM * G
Definition janet.cc:31
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition syz3.cc:1027

◆ apply()

CanonicalForm apply ( const CanonicalForm & f,
void(* mf )(CanonicalForm &, int &) )

CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) )

apply() - apply mf to terms of f.

Calls mf( f[i], i ) for each term f[i]*x^i of f and builds a new term from the result. If f is in a coefficient domain, mf( f, i ) should result in an i == 0, since otherwise it is not clear which variable to use for the resulting term.

An example:

void
diff( CanonicalForm & f, int & i )
{
f = f * i;
if ( i > 0 ) i--;
}
STATIC_VAR gmp_float * diff

Then apply( f, diff ) is differentiation of f with respect to the main variable of f.

Definition at line 402 of file cf_ops.cc.

403{
404 if ( f.inCoeffDomain() )
405 {
406 int exp = 0;
408 mf( result, exp );
409 ASSERT( exp == 0, "illegal result, do not know what variable to use" );
410 return result;
411 }
412 else
413 {
414 CanonicalForm result, coeff;
416 int exp;
417 Variable x = f.mvar();
418 for ( i = f; i.hasTerms(); i++ )
419 {
420 coeff = i.coeff();
421 exp = i.exp();
422 mf( coeff, exp );
423 if ( ! coeff.isZero() )
424 result += power( x, exp ) * coeff;
425 }
426 return result;
427 }
428}
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Variable x
Definition cfModGcd.cc:4090
class to iterate through CanonicalForm's
Definition cf_iter.h:44
CF_NO_INLINE bool isZero() const
factory's class for variables
Definition factory.h:127
gmp_float exp(const gmp_float &a)

◆ basicSet()

CFList basicSet ( const CFList & PS)

basic set in the sense of Wang a.k.a. minimal ascending set in the sense of Greuel/Pfister

Definition at line 150 of file cfCharSets.cc.

151{
152 CFList QS= PS, BS, RS;
154 int cb, degb;
155
156 if (PS.length() < 2)
157 return PS;
158
160
161 while (!QS.isEmpty())
162 {
163 b= lowestRank (QS);
164 cb= b.level();
165
166 BS= Union(CFList (b), BS);
167
168 if (cb <= 0)
169 return CFList();
170 else
171 {
172 degb= degree (b);
173 RS= CFList();
174 for (i= QS; i.hasItem(); i++)
175 {
176 if (degree (i.getItem(), cb) < degb)
177 RS= Union (CFList (i.getItem()), RS);
178 }
179 QS= RS;
180 }
181 }
182
183 return BS;
184}
int degree(const CanonicalForm &f)
ListIterator< CanonicalForm > CFListIterator
List< CanonicalForm > CFList
CanonicalForm lowestRank(const CFList &L)
CanonicalForm b
Definition cfModGcd.cc:4111
int length() const
int isEmpty() const

◆ bCommonDen()

CanonicalForm bCommonDen ( const CanonicalForm & f )

bCommonDen() - calculate multivariate common denominator of coefficients of ‘f’.

The common denominator is calculated with respect to all coefficients of ‘f’ which are in a base domain. In other words, common_den( ‘f’ ) * ‘f’ is guaranteed to have integer coefficients only. The common denominator of zero is one.

Returns something non-trivial iff the current domain is Q.

Type info:

f: CurrentPP

Definition at line 293 of file cf_algorithm.cc.

294{
295 if ( getCharacteristic() == 0 && isOn( SW_RATIONAL ) )
296 {
297 // otherwise `bgcd()' returns one
298 Off( SW_RATIONAL );
300 On( SW_RATIONAL );
301 return result;
302 }
303 else
304 return CanonicalForm( 1 );
305}
static CanonicalForm internalBCommonDen(const CanonicalForm &f)
static CanonicalForm internalBCommonDen ( const CanonicalForm & f )

◆ blcm()

Definition at line 1816 of file canonicalform.cc.

1817{
1818 if ( f.isZero() || g.isZero() )
1819 return CanonicalForm( 0L );
1820/*
1821 else if (f.isOne())
1822 return g;
1823 else if (g.isOne())
1824 return f;
1825*/
1826 else
1827 return (f / bgcd( f, g )) * g;
1828}
CanonicalForm bgcd(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g )
g
Definition cfModGcd.cc:4098

◆ cf_getBigPrime()

int FACTORY_PUBLIC cf_getBigPrime ( int i)

Definition at line 39 of file cf_primes.cc.

40{
41 ASSERT( i >= 0 && i < NUMBIGPRIMES, "index to primes too high" );
42 return bigprimes[i];
43}
static const int bigprimes[]
#define NUMBIGPRIMES
Definition cf_primetab.h:9

◆ cf_getNumBigPrimes()

int FACTORY_PUBLIC cf_getNumBigPrimes ( )

Definition at line 45 of file cf_primes.cc.

46{
47 return NUMBIGPRIMES;
48}

◆ cf_getNumPrimes()

int FACTORY_PUBLIC cf_getNumPrimes ( )

Definition at line 23 of file cf_primes.cc.

24{
25 return NUMPRIMES;
26}
#define NUMPRIMES
Definition cf_primetab.h:10

◆ cf_getNumSmallPrimes()

int FACTORY_PUBLIC cf_getNumSmallPrimes ( )

Definition at line 34 of file cf_primes.cc.

35{
36 return NUMSMALLPRIMES;
37}
#define NUMSMALLPRIMES
Definition cf_primetab.h:8

◆ cf_getPrime()

int FACTORY_PUBLIC cf_getPrime ( int i)

Definition at line 14 of file cf_primes.cc.

15{
16 ASSERT( i >= 0 && i < NUMPRIMES, "index to primes too high" );
17 if ( i >= NUMSMALLPRIMES )
19 else
20 return smallprimes[i];
21}
static const int smallprimes[]
Definition cf_primetab.h:12

◆ cf_getSmallPrime()

int FACTORY_PUBLIC cf_getSmallPrime ( int i)

Definition at line 28 of file cf_primes.cc.

29{
30 ASSERT( i >= 0 && i < NUMSMALLPRIMES, "index to primes too high" );
31 return smallprimes[i];
32}

◆ cf_HNF()

CFMatrix * cf_HNF ( CFMatrix & A)

The input matrix A is square matrix of integers output: the Hermite Normal Form of A; that is, the unique m x m matrix whose rows span L, such that.

  • lower triangular,
  • the diagonal entries are positive,
  • any entry below the diagonal is a non-negative number strictly less than the diagonal entry in its column.
Note
: uses NTL

The input matrix A is square matrix of integers output: the Hermite Normal Form of A; that is, the unique m x m matrix whose rows span L, such that.

W is computed as the Hermite Normal Form of A; that is, W is the unique m x m matrix whose rows span L, such that

  • W is lower triangular,
  • the diagonal entries are positive,
  • any entry below the diagonal is a non-negative number strictly less than the diagonal entry in its column.

Definition at line 44 of file cf_hnf.cc.

45{
46#ifdef HAVE_FLINT
47 fmpz_mat_t FLINTM;
49 fmpz_mat_hnf(FLINTM,FLINTM);
51 fmpz_mat_clear(FLINTM);
52 return r;
53#elif defined(HAVE_NTL)
55 ZZ DD=convertFacCF2NTLZZ(determinant(A,A.rows()));
56 mat_ZZ WW;
57 HNF(WW,*AA,DD);
58 delete AA;
60#else
61 factoryError("NTL/FLINT missing: cf_HNF");
62 return NULL; // avoid warning
63#endif
64}
void convertFacCFMatrix2Fmpz_mat_t(fmpz_mat_t M, const CFMatrix &m)
conversion of a factory matrix over Z to a fmpz_mat_t
CFMatrix * convertFmpz_mat_t2FacCFMatrix(const fmpz_mat_t m)
conversion of a FLINT matrix over Z to a factory matrix
mat_ZZ * convertFacCFMatrix2NTLmat_ZZ(const CFMatrix &m)
CFMatrix * convertNTLmat_ZZ2FacCFMatrix(const mat_ZZ &m)
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Matrix< CanonicalForm > CFMatrix
CanonicalForm FACTORY_PUBLIC determinant(const CFMatrix &M, int n)
Definition cf_linsys.cc:222
VAR void(* factoryError)(const char *s)
Definition cf_util.cc:80
#define NULL
Definition omList.c:12
#define A
Definition sirandom.c:24

◆ cf_LLL()

CFMatrix * cf_LLL ( CFMatrix & A)

performs LLL reduction.

B is an m x n matrix, viewed as m rows of n-vectors. m may be less than, equal to, or greater than n, and the rows need not be linearly independent. B is transformed into an LLL-reduced basis, and the return value is the rank r of B. The first m-r rows of B are zero.

More specifically, elementary row transformations are performed on B so that the non-zero rows of new-B form an LLL-reduced basis for the lattice spanned by the rows of old-B. The default reduction parameter is delta=3/4, which means that the squared length of the first non-zero basis vector is no more than 2^{r-1} times that of the shortest vector in the lattice.

Note
: uses NTL or FLINT

Definition at line 66 of file cf_hnf.cc.

67{
68#ifdef HAVE_FLINT
69 fmpz_mat_t FLINTM;
71 fmpq_t delta,eta;
72 fmpq_init(delta); fmpq_set_si(delta,1,1);
73 fmpq_init(eta); fmpq_set_si(eta,3,4);
74 fmpz_mat_lll_storjohann(FLINTM,delta,eta);
76 fmpz_mat_clear(FLINTM);
77 return r;
78#elif defined(HAVE_NTL)
80 ZZ det2;
81 LLL(det2,*AA,0L);
83 delete AA;
84 return r;
85#else
86 factoryError("NTL/FLINT missing: cf_LLL");
87 return NULL; // avoid warning
88#endif
89}
bool delta(X x, Y y, D d)
Definition TestSuite.h:160

◆ charSeries()

ListCFList charSeries ( const CFList & L)

characteristic series

Definition at line 411 of file cfCharSets.cc.

412{
413 ListCFList tmp, result, tmp2, ppi1, ppi2, qqi, ppi, alreadyConsidered;
414 CFList l, charset, ini;
415
416 int count= 0;
417 int highestLevel= 1;
419
420 StoreFactors StoredFactors;
421
422 l= L;
423
424 for (iter= l; iter.hasItem(); iter++)
425 {
426 iter.getItem()= normalize (iter.getItem());
427 if (highestLevel < iter.getItem().level())
428 highestLevel= iter.getItem().level();
429 }
430
431 tmp= ListCFList (l);
432
433 while (!tmp.isEmpty())
434 {
435 sortListCFList (tmp);
436
437 l= tmp.getFirst();
438
439 tmp= Difference (tmp, l);
440
441 select (ppi, l.length(), ppi1, ppi2);
442
443 inplaceUnion (ppi2, qqi);
444
445 if (count > 0)
446 ppi= Union (ppi1, ListCFList (l));
447 else
448 ppi= ListCFList();
449
450 if (l.length() - 3 < highestLevel)
451 charset= charSetViaModCharSet (l, StoredFactors);
452 else
453 charset= charSetViaCharSetN (l);
454
455 if (charset.length() > 0 && charset.getFirst().level() > 0)
456 {
457 result= Union (ListCFList (charset), result);
458 ini= factorsOfInitials (charset);
459
460 ini= Union (ini, factorPSet (StoredFactors.FS1));
461 sortCFListByLevel (ini);
462 }
463 else
464 {
465 ini= factorPSet (StoredFactors.FS1);
466 sortCFListByLevel (ini);
467 }
468
469 tmp2= adjoin (ini, l, qqi);
470 tmp= Union (tmp2, tmp);
471
472 StoredFactors.FS1= CFList();
473 StoredFactors.FS2= CFList();
474
475 ppi1= ListCFList();
476 ppi2= ListCFList();
477
478 count++;
479 }
480
481 //TODO need to remove superflous components
482
483 return result;
484}
List< CFList > ListCFList
void inplaceUnion(const ListCFList &a, ListCFList &b)
Union of a and b stored in b.
CFList factorsOfInitials(const CFList &L)
void select(const ListCFList &ppi, int length, ListCFList &ppi1, ListCFList &ppi2)
void sortListCFList(ListCFList &list)
sort in descending order of length of elements
void sortCFListByLevel(CFList &list)
sort in descending order of level of elements
CFList factorPSet(const CFList &PS)
ListCFList adjoin(const CFList &is, const CFList &qs, const ListCFList &qh)
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents)
characteristic set via modified medial set
int l
Definition cfEzgcd.cc:100
int level() const
level() returns the level of CO.
T getFirst() const
class to store factors that get removed during char set computation
CFList FS2
candidate factors that might get removed
CFList FS1
factors that were removed
CFList tmp2
Definition facFqBivar.cc:75
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
int status int void size_t count
Definition si_signals.h:69

◆ charSet()

CFList charSet ( const CFList & PS)

characteristic set

Definition at line 187 of file cfCharSets.cc.

188{
189 CFList QS= PS, RS= PS, CSet, tmp;
192
193 while (!RS.isEmpty())
194 {
195 CSet= basicSet (QS);
196
197 RS= CFList();
198 if (CSet.length() > 0 && CSet.getFirst().level() > 0)
199 {
200 tmp= Difference (QS, CSet);
201 for (i= tmp; i.hasItem(); i++)
202 {
203 r= Prem (i.getItem(), CSet);
204 if (r != 0)
205 RS= Union (RS, CFList (r));
206 }
207 QS= Union (QS, RS);
208 }
209 }
210
211 return CSet;
212}
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
CFList basicSet(const CFList &PS)
basic set in the sense of Wang a.k.a. minimal ascending set in the sense of Greuel/Pfister

◆ charSetN()

CFList charSetN ( const CFList & PS)

medial set

Definition at line 216 of file cfCharSets.cc.

217{
218 CFList QS= PS, RS= PS, CSet, tmp;
221
222 while (!RS.isEmpty())
223 {
224 QS= uniGcd (QS);
225 CSet= basicSet (QS);
226
227 RS= CFList();
228 if (CSet.length() > 0 && CSet.getFirst().level() > 0)
229 {
230 tmp= Difference (QS, CSet);
231 for (i= tmp; i.hasItem(); i++)
232 {
233 r= Prem (i.getItem(), CSet);
234 if (!r.isZero())
235 RS= Union (RS, CFList (r));
236 }
237 QS= Union (CSet, RS);
238 }
239 }
240
241 return CSet;
242}
CFList uniGcd(const CFList &L)

◆ charSetViaCharSetN()

CFList charSetViaCharSetN ( const CFList & PS)

compute a characteristic set via medial set

Definition at line 246 of file cfCharSets.cc.

247{
248 CFList L;
249 CFFList sqrfFactors;
250 CanonicalForm sqrf;
251 CFFListIterator iter2;
252 for (CFListIterator iter= PS; iter.hasItem(); iter++)
253 {
254 sqrf= 1;
255 sqrfFactors= sqrFree (iter.getItem());
256 for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
257 sqrf *= iter2.getItem().factor();
258 L= Union (L, CFList (normalize (sqrf)));
259 }
260
262
263 if (result.isEmpty() || result.getFirst().inCoeffDomain())
264 return CFList(1);
265
267 CFList RS;
268 CFList tmp= Difference (L, result);
269
270 for (CFListIterator i= tmp; i.hasItem(); i++)
271 {
272 r= Premb (i.getItem(), result);
273 if (!r.isZero())
274 RS= Union (RS, CFList (r));
275 }
276 if (RS.isEmpty())
277 return result;
278
279 return charSetViaCharSetN (Union (L, Union (RS, result)));
280}
CanonicalForm Premb(const CanonicalForm &f, const CFList &L)
pseudo remainder of f by L with faster test for remainder being zero
CFList charSetN(const CFList &PS)
medial set
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition cf_factor.cc:961
T factor() const
T & getItem() const

◆ charSetViaModCharSet() [1/2]

CFList charSetViaModCharSet ( const CFList & PS,
bool removeContents = true )

modified characteristic set, i.e. a characteristic set with certain factors removed

Definition at line 397 of file cfCharSets.cc.

398{
399 StoreFactors tmp;
400 return charSetViaModCharSet (PS, tmp, removeContents);
401}

◆ charSetViaModCharSet() [2/2]

CFList charSetViaModCharSet ( const CFList & PS,
StoreFactors & StoredFactors,
bool removeContents )

modified characteristic set, i.e. a characteristic set with certain factors removed

modified characteristic set, i.e. a characteristic set with certain factors removed

Definition at line 356 of file cfCharSets.cc.

358{
359 CFList L;
360 CFFList sqrfFactors;
361 CanonicalForm sqrf;
362 CFFListIterator iter2;
363 for (CFListIterator iter= PS; iter.hasItem(); iter++)
364 {
365 sqrf= 1;
366 sqrfFactors= sqrFree (iter.getItem());
367 for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
368 sqrf *= iter2.getItem().factor();
369 L= Union (L, CFList (normalize (sqrf)));
370 }
371
372 L= uniGcd (L);
373
374 CFList result= modCharSet (L, StoredFactors, removeContents);
375
376 if (result.isEmpty() || result.getFirst().inCoeffDomain())
377 return CFList(1);
378
380 CFList RS;
381 CFList tmp= Difference (L, result);
382
383 for (CFListIterator i= tmp; i.hasItem(); i++)
384 {
385 r= Premb (i.getItem(), result);
386 if (!r.isZero())
387 RS= Union (RS, CFList (r));
388 }
389 if (RS.isEmpty())
390 return result;
391
392 return charSetViaModCharSet (Union (L, Union (RS, result)), StoredFactors,
393 removeContents);
394}
CFList modCharSet(const CFList &L, StoreFactors &StoredFactors, bool removeContents)
modified medial set

◆ chineseRemainder() [1/2]

void FACTORY_PUBLIC chineseRemainder ( const CanonicalForm & x1,
const CanonicalForm & q1,
const CanonicalForm & x2,
const CanonicalForm & q2,
CanonicalForm & xnew,
CanonicalForm & qnew )

void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew )

chineseRemainder - integer chinese remaindering.

Calculate xnew such that xnew=x1 (mod q1) and xnew=x2 (mod q2) and qnew = q1*q2. q1 and q2 should be positive integers, pairwise prime, x1 and x2 should be polynomials with integer coefficients. If x1 and x2 are polynomials with positive coefficients, the result is guaranteed to have positive coefficients, too.

Note: This algorithm is optimized for the case q1>>q2.

This is a standard algorithm. See, for example, Geddes/Czapor/Labahn - 'Algorithms for Computer Algebra', par. 5.6 and 5.8, or the article of M. Lauer - 'Computing by Homomorphic Images' in B. Buchberger - 'Computer Algebra - Symbolic and Algebraic Computation'.

Note: Be sure you are calculating in Z, and not in Q!

Definition at line 57 of file cf_chinese.cc.

58{
59 DEBINCLEVEL( cerr, "chineseRemainder" );
60
61 DEBOUTLN( cerr, "log(q1) = " << q1.ilog2() );
62 DEBOUTLN( cerr, "log(q2) = " << q2.ilog2() );
63
64 // We calculate xnew as follows:
65 // xnew = v1 + v2 * q1
66 // where
67 // v1 = x1 (mod q1)
68 // v2 = (x2-v1)/q1 (mod q2) (*)
69 //
70 // We do one extra test to check whether x2-v1 vanishes (mod
71 // q2) in (*) since it is not costly and may save us
72 // from calculating the inverse of q1 (mod q2).
73 //
74 // u: v1 (mod q2)
75 // d: x2-v1 (mod q2)
76 // s: 1/q1 (mod q2)
77 //
78 CanonicalForm v2, v1;
79 CanonicalForm u, d, s, dummy;
80
81 v1 = mod( x1, q1 );
82 u = mod( v1, q2 );
83 d = mod( x2-u, q2 );
84 if ( d.isZero() )
85 {
86 xnew = v1;
87 qnew = q1 * q2;
88 DEBDECLEVEL( cerr, "chineseRemainder" );
89 return;
90 }
91 (void)bextgcd( q1, q2, s, dummy );
92 v2 = mod( d*s, q2 );
93 xnew = v1 + v2*q1;
94
95 // After all, calculate new modulus. It is important that
96 // this is done at the very end of the algorithm, since q1
97 // and qnew may refer to the same object (same is true for x1
98 // and xnew).
99 qnew = q1 * q2;
100
101 DEBDECLEVEL( cerr, "chineseRemainder" );
102}
CanonicalForm bextgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
int ilog2() const
int CanonicalForm::ilog2 () const
#define DEBINCLEVEL(stream, msg)
Definition debug.h:44
#define DEBOUTLN(stream, objects)
Definition debug.h:49
#define DEBDECLEVEL(stream, msg)
Definition debug.h:45
const CanonicalForm int s
Definition facAbsFact.cc:51

◆ chineseRemainder() [2/2]

void FACTORY_PUBLIC chineseRemainder ( const CFArray & x,
const CFArray & q,
CanonicalForm & xnew,
CanonicalForm & qnew )

void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew )

chineseRemainder - integer chinese remaindering.

Calculate xnew such that xnew=x[i] (mod q[i]) and qnew is the product of all q[i]. q[i] should be positive integers, pairwise prime. x[i] should be polynomials with integer coefficients. If all coefficients of all x[i] are positive integers, the result is guaranteed to have positive coefficients, too.

This is a standard algorithm, too, except for the fact that we use a divide-and-conquer method instead of a linear approach to calculate the remainder.

Note: Be sure you are calculating in Z, and not in Q!

Definition at line 124 of file cf_chinese.cc.

125{
126 DEBINCLEVEL( cerr, "chineseRemainder( ... CFArray ... )" );
127
128 ASSERT( x.min() == q.min() && x.size() == q.size(), "incompatible arrays" );
129 CFArray X(x), Q(q);
130 int i, j, n = x.size(), start = x.min();
131
132 DEBOUTLN( cerr, "array size = " << n );
133
134 while ( n != 1 )
135 {
136 i = j = start;
137 while ( i < start + n - 1 )
138 {
139 // This is a little bit dangerous: X[i] and X[j] (and
140 // Q[i] and Q[j]) may refer to the same object. But
141 // xnew and qnew in the above function are modified
142 // at the very end of the function, so we do not
143 // modify x1 and q1, resp., by accident.
144 chineseRemainder( X[i], Q[i], X[i+1], Q[i+1], X[j], Q[j] );
145 i += 2;
146 j++;
147 }
148
149 if ( n & 1 )
150 {
151 X[j] = X[i];
152 Q[j] = Q[i];
153 }
154 // Maybe we would get some memory back at this point if
155 // we would set X[j+1, ..., n] and Q[j+1, ..., n] to zero
156 // at this point?
157
158 n = ( n + 1) / 2;
159 }
160 xnew = X[start];
161 qnew = Q[q.min()];
162
163 DEBDECLEVEL( cerr, "chineseRemainder( ... CFArray ... )" );
164}
Array< CanonicalForm > CFArray
void chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2,...
Definition cf_chinese.cc:57
int size() const
int min() const
int j
Definition facHensel.cc:110
#define Q
Definition sirandom.c:26

◆ chineseRemainderCached() [1/2]

void FACTORY_PUBLIC chineseRemainderCached ( const CanonicalForm & x1,
const CanonicalForm & q1,
const CanonicalForm & x2,
const CanonicalForm & q2,
CanonicalForm & xnew,
CanonicalForm & qnew,
CFArray & inv )

Definition at line 308 of file cf_chinese.cc.

309{
310 CFArray A(2); A[0]=a; A[1]=b;
311 CFArray Q(2); Q[0]=q1; Q[1]=q2;
312 chineseRemainderCached(A,Q,xnew,qnew,inv);
313}
void chineseRemainderCached(const CFArray &a, const CFArray &n, CanonicalForm &xnew, CanonicalForm &prod, CFArray &inv)

◆ chineseRemainderCached() [2/2]

void FACTORY_PUBLIC chineseRemainderCached ( const CFArray & a,
const CFArray & n,
CanonicalForm & xnew,
CanonicalForm & prod,
CFArray & inv )

Definition at line 290 of file cf_chinese.cc.

291{
292 CanonicalForm p, sum=0L; prod=1L;
293 int i;
294 int len=n.size();
295
296 for (i = 0; i < len; i++) prod *= n[i];
297
298 for (i = 0; i < len; i++)
299 {
300 p = prod / n[i];
301 sum += a[i] * chin_mul_inv(p, n[i], i, inv) * p;
302 }
303
304 xnew = mod(sum , prod);
305}
int p
Definition cfModGcd.cc:4086
static CanonicalForm chin_mul_inv(const CanonicalForm a, const CanonicalForm b, int ind, CFArray &inv)
fq_nmod_poly_t prod
Definition facHensel.cc:100

◆ compress() [1/3]

CanonicalForm compress ( const CanonicalForm & f,
CFMap & m )

CanonicalForm compress ( const CanonicalForm & f, CFMap & m )

compress() - compress the canonical form f.

Compress the polynomial f such that the levels of its polynomial variables are ordered without any gaps starting from level 1. Return the compressed polynomial and a map m to undo the compression. That is, if f' = compress(f, m), than f = m(f').

Definition at line 210 of file cf_map.cc.

211{
213 int i, n;
214 int * degs = degrees( f );
215
216 m = CFMap();
217 n = i = 1;
218 while ( i <= level( f ) ) {
219 while( degs[i] == 0 ) i++;
220 if ( i != n ) {
221 // swap variables and remember the swap in the map
222 m.newpair( Variable( n ), Variable( i ) );
223 result = swapvar( result, Variable( i ), Variable( n ) );
224 }
225 n++; i++;
226 }
227 DELETE_ARRAY(degs);
228 return result;
229}
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition cf_ops.cc:493
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
int level(const CanonicalForm &f)
int m
Definition cfEzgcd.cc:128
#define DELETE_ARRAY(P)
Definition cf_defs.h:65
class CFMap
Definition cf_map.h:85

◆ compress() [2/3]

void compress ( const CanonicalForm & f,
const CanonicalForm & g,
CFMap & M,
CFMap & N )

void compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N )

compress() - compress the variables occurring in f and g with respect to optimal variables

Compress the polynomial variables occurring in f and g so that the levels of variables common to f and g are ordered without any gaps starting from level 1, whereas the variables occuring in only one of f or g are moved to levels higher than the levels of the common variables. Return the CFMap M to realize the compression and its inverse, the CFMap N. N needs only variables common to f and g.

Definition at line 349 of file cf_map.cc.

350{
351 int n = tmax( f.level(), g.level() );
352 int i, k, p1, pe;
353 int * degsf = NEW_ARRAY(int,n+1);
354 int * degsg = NEW_ARRAY(int,n+1);
355
356 for ( i = 0; i <= n; i++ )
357 {
358 degsf[i] = degsg[i] = 0;
359 }
360
361 degsf = degrees( f, degsf );
362 degsg = degrees( g, degsg );
363 optvalues( degsf, degsg, n, p1, pe );
364
365 i = 1; k = 1;
366 if ( pe > 1 )
367 {
368 M.newpair( Variable(pe), Variable(k) );
369 N.newpair( Variable(k), Variable(pe) );
370 k++;
371 }
372 while ( i <= n )
373 {
374 if ( degsf[i] > 0 && degsg[i] > 0 )
375 {
376 if ( ( i != k ) && ( i != pe ) && ( i != p1 ) )
377 {
378 M.newpair( Variable(i), Variable(k) );
379 N.newpair( Variable(k), Variable(i) );
380 }
381 k++;
382 }
383 i++;
384 }
385 if ( p1 != pe )
386 {
387 M.newpair( Variable(p1), Variable(k) );
388 N.newpair( Variable(k), Variable(p1) );
389 k++;
390 }
391 i = 1;
392 while ( i <= n )
393 {
394 if ( degsf[i] > 0 && degsg[i] == 0 ) {
395 if ( i != k )
396 {
397 M.newpair( Variable(i), Variable(k) );
398 k++;
399 }
400 }
401 else if ( degsf[i] == 0 && degsg[i] > 0 )
402 {
403 if ( i != k )
404 {
405 M.newpair( Variable(i), Variable(k) );
406 k++;
407 }
408 }
409 i++;
410 }
411
414}
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
int * degsf
Definition cfEzgcd.cc:59
int k
Definition cfEzgcd.cc:99
int * degsg
Definition cfEzgcd.cc:60
#define NEW_ARRAY(T, N)
Definition cf_defs.h:64
static void optvalues(const int *df, const int *dg, const int n, int &p1, int &pe)
Definition cf_map.cc:296
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
#define M
Definition sirandom.c:25

◆ compress() [3/3]

void compress ( const CFArray & a,
CFMap & M,
CFMap & N )

void compress ( const CFArray & a, CFMap & M, CFMap & N )

compress() - compress the variables occuring in an a.

Compress the polynomial variables occuring in a so that their levels are ordered without any gaps starting from level 1. Return the CFMap M to realize the compression and its inverse, the CFMap N. Note that if you compress a member of a using M the result of the compression is not necessarily compressed, since the map is constructed using all variables occuring in a.

Definition at line 245 of file cf_map.cc.

246{
247 M = N = CFMap();
248 if ( a.size() == 0 )
249 return;
250 int maxlevel = level( a[a.min()] );
251 int i, j;
252
253 // get the maximum of levels in a
254 for ( i = a.min() + 1; i <= a.max(); i++ )
255 if ( level( a[i] ) > maxlevel )
256 maxlevel = level( a[i] );
257 if ( maxlevel <= 0 )
258 return;
259
260 int * degs = NEW_ARRAY(int,maxlevel+1);
261 int * tmp = NEW_ARRAY(int,maxlevel+1);
262 for ( i = maxlevel; i >= 1; i-- )
263 degs[i] = 0;
264
265 // calculate the union of all levels occuring in a
266 for ( i = a.min(); i <= a.max(); i++ )
267 {
268 tmp = degrees( a[i], tmp );
269 for ( j = 1; j <= level( a[i] ); j++ )
270 if ( tmp[j] != 0 )
271 degs[j] = 1;
272 }
273
274 // create the maps
275 i = 1; j = 1;
276 while ( i <= maxlevel )
277 {
278 if ( degs[i] != 0 )
279 {
280 M.newpair( Variable(i), Variable(j) );
281 N.newpair( Variable(j), Variable(i) );
282 j++;
283 }
284 i++;
285 }
286 DELETE_ARRAY(degs);
287 DELETE_ARRAY(tmp);
288}
int max() const

◆ content() [1/2]

CanonicalForm content ( const CanonicalForm & f )

content() - return content(f) with respect to main variable.

Normalizes result.

Definition at line 603 of file cf_gcd.cc.

604{
605 if ( f.inPolyDomain() || ( f.inExtension() && ! getReduce( f.mvar() ) ) )
606 {
607 CFIterator i = f;
608 CanonicalForm result = abs( i.coeff() );
609 i++;
610 while ( i.hasTerms() && ! result.isOne() )
611 {
612 result = gcd( i.coeff(), result );
613 i++;
614 }
615 return result;
616 }
617 else
618 return abs( f );
619}
Rational abs(const Rational &a)
Definition GMPrat.cc:436
CanonicalForm gcd(const CanonicalForm &f, const CanonicalForm &g)
Definition cf_gcd.cc:685
bool getReduce(const Variable &alpha)
Definition variable.cc:232

◆ content() [2/2]

CanonicalForm content ( const CanonicalForm & f, const Variable & x )

content() - return content(f) with respect to x.

x should be a polynomial variable.

Definition at line 629 of file cf_gcd.cc.

630{
631 if (f.inBaseDomain()) return f;
632 ASSERT( x.level() > 0, "cannot calculate content with respect to algebraic variable" );
633 Variable y = f.mvar();
634
635 if ( y == x )
636 return cf_content( f, 0 );
637 else if ( y < x )
638 return f;
639 else
640 return swapvar( content( swapvar( f, y, x ), y ), y, x );
641}
static CanonicalForm cf_content(const CanonicalForm &f, const CanonicalForm &g)
static CanonicalForm cf_content ( const CanonicalForm & f, const CanonicalForm & g )
Definition cf_gcd.cc:578
CanonicalForm content(const CanonicalForm &f)
CanonicalForm content ( const CanonicalForm & f )
Definition cf_gcd.cc:603
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53

◆ degree() [1/2]

int degree ( const CanonicalForm & f)
inline

Definition at line 457 of file factory.h.

457{ return f.degree(); }

◆ degree() [2/2]

int degree ( const CanonicalForm & f,
const Variable & v )
inline

Definition at line 460 of file factory.h.

460{ return f.degree( v ); }
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39

◆ degrees()

int * degrees ( const CanonicalForm & f,
int * degs )

int * degrees ( const CanonicalForm & f, int * degs )

degress() - return the degrees of all polynomial variables in f.

Returns 0 if f is in a coefficient domain, the degrees of f in all its polynomial variables in an array of int otherwise:

degrees( f, 0 )[i] = degree( f, Variable(i) )

If degs is not the zero pointer the degrees are stored in this array. In this case degs should be larger than the level of f. If degs is the zero pointer, an array of sufficient size is allocated automatically.

Definition at line 493 of file cf_ops.cc.

494{
495 if ( f.inCoeffDomain() )
496 {
497 if (degs != 0)
498 return degs;
499 else
500 return 0;
501 }
502 else
503 {
504 int level = f.level();
505 if ( degs == NULL )
506 degs = NEW_ARRAY(int,level+1);
507 for ( int i = level; i >= 0; i-- )
508 degs[i] = 0;
509 degreesRec( f, degs );
510 return degs;
511 }
512}
static void degreesRec(const CanonicalForm &f, int *degs)
static void degreesRec ( const CanonicalForm & f, int * degs )
Definition cf_ops.cc:463

◆ den()

CanonicalForm den ( const CanonicalForm & f)
inline

Definition at line 481 of file factory.h.

481{ return f.den(); }

◆ deriv()

CanonicalForm deriv ( const CanonicalForm & f,
const Variable & x )
inline

Definition at line 487 of file factory.h.

487{ return f.deriv( x ); }

◆ determinant()

CanonicalForm FACTORY_PUBLIC determinant ( const CFMatrix & M,
int n )

Definition at line 222 of file cf_linsys.cc.

223{
224 typedef int* int_ptr;
225
226 ASSERT( rows <= M.rows() && rows <= M.columns() && rows > 0, "undefined determinant" );
227 if ( rows == 1 )
228 return M(1,1);
229 else if ( rows == 2 )
230 return M(1,1)*M(2,2)-M(2,1)*M(1,2);
231 else if ( matrix_in_Z( M, rows ) )
232 {
233 int ** mm = new int_ptr[rows];
234 CanonicalForm x, q, Qhalf, B;
235 int n, i, intdet, p, pno;
236 for ( i = 0; i < rows; i++ )
237 {
238 mm[i] = new int[rows];
239 }
240 pno = 0; n = 0;
241 TIMING_START(det_bound);
242 B = detbound( M, rows );
243 TIMING_END(det_bound);
244 q = 1;
245 TIMING_START(det_numprimes);
246 while ( B > q && n < cf_getNumBigPrimes() )
247 {
248 q *= cf_getBigPrime( n );
249 n++;
250 }
251 TIMING_END(det_numprimes);
252
253 CFArray X(1,n), Q(1,n);
254
255 while ( pno < n )
256 {
257 p = cf_getBigPrime( pno );
259 // map matrix into char p
260 TIMING_START(det_mapping);
261 fill_int_mat( M, mm, rows );
262 TIMING_END(det_mapping);
263 pno++;
264 DEBOUT( cerr, "." );
265 TIMING_START(det_determinant);
266 intdet = determinant( mm, rows );
267 TIMING_END(det_determinant);
269 X[pno] = intdet;
270 Q[pno] = p;
271 }
272 TIMING_START(det_chinese);
273 chineseRemainder( X, Q, x, q );
274 TIMING_END(det_chinese);
275 Qhalf = q / 2;
276 if ( x > Qhalf )
277 x = x - q;
278 for ( i = 0; i < rows; i++ )
279 delete [] mm[i];
280 delete [] mm;
281 return x;
282 }
283 else
284 {
285 CFMatrix m( M );
286 CanonicalForm divisor = 1, pivot, mji;
287 int i, j, k, sign = 1;
288 for ( i = 1; i <= rows; i++ ) {
289 pivot = m(i,i); k = i;
290 for ( j = i+1; j <= rows; j++ ) {
291 if ( betterpivot( pivot, m(j,i) ) ) {
292 pivot = m(j,i);
293 k = j;
294 }
295 }
296 if ( pivot.isZero() )
297 return 0;
298 if ( i != k )
299 {
300 m.swapRow( i, k );
301 sign = -sign;
302 }
303 for ( j = i+1; j <= rows; j++ )
304 {
305 if ( ! m(j,i).isZero() )
306 {
307 divisor *= pivot;
308 mji = m(j,i);
309 m(j,i) = 0;
310 for ( k = i+1; k <= rows; k++ )
311 m(j,k) = m(j,k) * pivot - m(i,k)*mji;
312 }
313 }
314 }
315 pivot = sign;
316 for ( i = 1; i <= rows; i++ )
317 pivot *= m(i,i);
318 return pivot / divisor;
319 }
320}
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
void FACTORY_PUBLIC chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2,...
Definition cf_chinese.cc:57
bool matrix_in_Z(const CFMatrix &M, int rows)
Definition cf_linsys.cc:39
bool betterpivot(const CanonicalForm &oldpivot, const CanonicalForm &newpivot)
Definition cf_linsys.cc:61
CanonicalForm detbound(const CFMatrix &M, int rows)
Definition cf_linsys.cc:486
int determinant(int **extmat, int n)
Definition cf_linsys.cc:556
static bool fill_int_mat(const CFMatrix &M, int **m, int rows)
Definition cf_linsys.cc:203
int cf_getBigPrime(int i)
Definition cf_primes.cc:39
int cf_getNumBigPrimes()
Definition cf_primes.cc:45
#define DEBOUT(stream, objects)
Definition debug.h:47
b *CanonicalForm B
Definition facBivar.cc:52
bool isZero(const CFArray &A)
checks if entries of A are zero
bool pivot(const matrix aMat, const int r1, const int r2, const int c1, const int c2, int *bestR, int *bestC, const ring R)
This code computes a score for each non-zero matrix entry in aMat[r1..r2, c1..c2].
static int sign(int x)
Definition ring.cc:3503
int * int_ptr
Definition structs.h:50
#define TIMING_END(t)
Definition timing.h:93
#define TIMING_START(t)
Definition timing.h:92

◆ div()

◆ euclideanNorm()

CanonicalForm euclideanNorm ( const CanonicalForm & f)

CanonicalForm euclideanNorm ( const CanonicalForm & f )

euclideanNorm() - return Euclidean norm of ‘f’.

Returns the largest integer smaller or equal norm(‘f’) = sqrt(sum( ‘f’[i]^2 )).

Type info:

f: UVPoly( Z )

Definition at line 565 of file cf_algorithm.cc.

566{
567 ASSERT( (f.inBaseDomain() || f.isUnivariate()) && f.LC().inZ(),
568 "type error: univariate poly over Z expected" );
569
571 for ( CFIterator i = f; i.hasTerms(); i++ ) {
572 CanonicalForm coeff = i.coeff();
573 result += coeff*coeff;
574 }
575 return sqrt( result );
576}
gmp_float sqrt(const gmp_float &a)

◆ ExtensionLevel()

int ExtensionLevel ( )

Definition at line 254 of file variable.cc.

255{
256 if( var_names_ext == 0)
257 return 0;
258 return strlen( var_names_ext )-1;
259}
STATIC_VAR char * var_names_ext
Definition variable.cc:43

◆ extgcd()

CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b )

extgcd() - returns polynomial extended gcd of f and g.

Returns gcd(f, g) and a and b sucht that f*a+g*b=gcd(f, g). The gcd is calculated using an extended euclidean polynomial remainder sequence, so f and g should be polynomials over an euclidean domain. Normalizes result.

Note: be sure that f and g have the same level!

Definition at line 174 of file cfUnivarGcd.cc.

175{
176 if (f.isZero())
177 {
178 a= 0;
179 b= 1;
180 return g;
181 }
182 else if (g.isZero())
183 {
184 a= 1;
185 b= 0;
186 return f;
187 }
188#ifdef HAVE_FLINT
190 && (f.level()==g.level()) && isPurePoly(f) && isPurePoly(g))
191 {
192 nmod_poly_t F1, G1, A, B, R;
198 nmod_poly_xgcd (R, A, B, F1, G1);
199 a= convertnmod_poly_t2FacCF (A, f.mvar());
200 b= convertnmod_poly_t2FacCF (B, f.mvar());
203 nmod_poly_clear (G1);
207 return r;
208 }
209#elif defined(HAVE_NTL)
211 && (f.level()==g.level()) && isPurePoly(f) && isPurePoly(g))
212 {
214 {
216 zz_p::init(getCharacteristic());
217 }
219 zz_pX G1=convertFacCF2NTLzzpX(g);
220 zz_pX R;
221 zz_pX A,B;
222 XGCD(R,A,B,F1,G1);
223 a=convertNTLzzpX2CF(A,f.mvar());
224 b=convertNTLzzpX2CF(B,f.mvar());
225 return convertNTLzzpX2CF(R,f.mvar());
226 }
227#endif
228#ifdef HAVE_FLINT
229 if (( getCharacteristic() ==0) && (f.level()==g.level())
230 && isPurePoly(f) && isPurePoly(g))
231 {
232 fmpq_poly_t F1, G1;
235 fmpq_poly_t R, A, B;
236 fmpq_poly_init (R);
237 fmpq_poly_init (A);
238 fmpq_poly_init (B);
239 fmpq_poly_xgcd (R, A, B, F1, G1);
240 a= convertFmpq_poly_t2FacCF (A, f.mvar());
241 b= convertFmpq_poly_t2FacCF (B, f.mvar());
243 fmpq_poly_clear (F1);
244 fmpq_poly_clear (G1);
245 fmpq_poly_clear (A);
246 fmpq_poly_clear (B);
247 fmpq_poly_clear (R);
248 return r;
249 }
250#elif defined(HAVE_NTL)
251 if (( getCharacteristic() ==0)
252 && (f.level()==g.level()) && isPurePoly(f) && isPurePoly(g))
253 {
256 ZZX F1=convertFacCF2NTLZZX(f*fc);
257 ZZX G1=convertFacCF2NTLZZX(g*gc);
258 ZZX R=GCD(F1,G1);
260 ZZ RR;
261 ZZX A,B;
262 if (r.inCoeffDomain())
263 {
264 XGCD(RR,A,B,F1,G1,1);
266 if(!rr.isZero())
267 {
268 a=convertNTLZZX2CF(A,f.mvar())*fc/rr;
269 b=convertNTLZZX2CF(B,f.mvar())*gc/rr;
270 return CanonicalForm(1);
271 }
272 else
273 {
274 F1 /= R;
275 G1 /= R;
276 XGCD (RR, A,B,F1,G1,1);
277 rr=convertZZ2CF(RR);
278 a=convertNTLZZX2CF(A,f.mvar())*(fc/rr);
279 b=convertNTLZZX2CF(B,f.mvar())*(gc/rr);
280 }
281 }
282 else
283 {
284 XGCD(RR,A,B,F1,G1,1);
286 if (!rr.isZero())
287 {
288 a=convertNTLZZX2CF(A,f.mvar())*fc;
289 b=convertNTLZZX2CF(B,f.mvar())*gc;
290 }
291 else
292 {
293 F1 /= R;
294 G1 /= R;
295 XGCD (RR, A,B,F1,G1,1);
296 rr=convertZZ2CF(RR);
297 a=convertNTLZZX2CF(A,f.mvar())*(fc/rr);
298 b=convertNTLZZX2CF(B,f.mvar())*(gc/rr);
299 }
300 return r;
301 }
302 }
303#endif
304 // may contain bug in the co-factors, see track 107
305 CanonicalForm contf = content( f );
306 CanonicalForm contg = content( g );
307
308 CanonicalForm p0 = f / contf, p1 = g / contg;
309 CanonicalForm f0 = 1, f1 = 0, g0 = 0, g1 = 1, q, r;
310
311 while ( ! p1.isZero() )
312 {
313 divrem( p0, p1, q, r );
314 p0 = p1; p1 = r;
315 r = g0 - g1 * q;
316 g0 = g1; g1 = r;
317 r = f0 - f1 * q;
318 f0 = f1; f1 = r;
319 }
320 CanonicalForm contp0 = content( p0 );
321 a = f0 / ( contf * contp0 );
322 b = g0 / ( contg * contp0 );
323 p0 /= contp0;
324 if ( p0.sign() < 0 )
325 {
326 p0 = -p0;
327 a = -a;
328 b = -b;
329 }
330 return p0;
331}
CanonicalForm convertFmpq_poly_t2FacCF(const fmpq_poly_t p, const Variable &x)
conversion of a FLINT poly over Q to CanonicalForm
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
void convertFacCF2Fmpq_poly_t(fmpq_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomials over Q to fmpq_poly_t
CanonicalForm convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
VAR long fac_NTL_char
Definition NTLconvert.cc:46
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition cf_gcd.cc:603
bool isPurePoly(const CanonicalForm &f)
Definition cf_factor.cc:248
#define GaloisFieldDomain
Definition cf_defs.h:18
static int gettype()
Definition cf_factory.h:28
int sign() const
int CanonicalForm::sign () const
bool inCoeffDomain() const
nmod_poly_init(FLINTmipo, getCharacteristic())
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
#define R
Definition sirandom.c:27
int F1(int a1, int &r1)
F1.

◆ facAlgFunc()

CFFList facAlgFunc ( const CanonicalForm & f,
const CFList & as )

factorize a polynomial f modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $.

Returns
the returned factors are not necessarily monic but only primitive and the product of the factors equals f up to a unit.

factorize a polynomial f modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $.

Parameters
[in]funivariate poly
[in]asirreducible characteristic set

Definition at line 1043 of file facAlgFunc.cc.

1044{
1045 bool isRat= isOn (SW_RATIONAL);
1046 if (!isRat && getCharacteristic() == 0)
1047 On (SW_RATIONAL);
1048 CFFList Output, output, Factors= factorize(f);
1049 if (Factors.getFirst().factor().inCoeffDomain())
1050 Factors.removeFirst();
1051
1052 if (as.length() == 0)
1053 {
1054 if (!isRat && getCharacteristic() == 0)
1055 Off (SW_RATIONAL);
1056 return Factors;
1057 }
1058 if (f.level() <= as.getLast().level())
1059 {
1060 if (!isRat && getCharacteristic() == 0)
1061 Off (SW_RATIONAL);
1062 return Factors;
1063 }
1064
1065 for (CFFListIterator i=Factors; i.hasItem(); i++)
1066 {
1067 if (i.getItem().factor().level() > as.getLast().level())
1068 {
1069 output= facAlgFunc2 (i.getItem().factor(), as);
1070 for (CFFListIterator j= output; j.hasItem(); j++)
1071 Output= append (Output, CFFactor (j.getItem().factor(),
1072 j.getItem().exp()*i.getItem().exp()));
1073 }
1074 }
1075
1076 if (!isRat && getCharacteristic() == 0)
1077 Off (SW_RATIONAL);
1078 return Output;
1079}
Factor< CanonicalForm > CFFactor
void removeFirst()
T getLast() const
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CFFList facAlgFunc2(const CanonicalForm &f, const CFList &as)
factorize a polynomial that is irreducible over the ground field modulo an extension given by an irre...

◆ facAlgFunc2()

CFFList facAlgFunc2 ( const CanonicalForm & f,
const CFList & as )

factorize a polynomial f that is irreducible over the ground field modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $.

Returns
the returned factors are not necessarily monic but only primitive and the product of the factors equals f up to a unit.

factorize a polynomial f that is irreducible over the ground field modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $.

Parameters
[in]funivariate poly
[in]asirreducible characteristic set

Definition at line 905 of file facAlgFunc.cc.

906{
907 bool isRat= isOn (SW_RATIONAL);
908 if (!isRat && getCharacteristic() == 0)
909 On (SW_RATIONAL);
910 Variable vf=f.mvar();
913 CFList reduceresult;
915
916// F1: [Test trivial cases]
917// 1) first trivial cases:
918 if (vf.level() <= as.getLast().level())
919 {
920 if (!isRat && getCharacteristic() == 0)
922 return CFFList(CFFactor(f,1));
923 }
924
925// 2) Setup list of those polys in AS having degree > 1
926 CFList Astar;
927 Variable x;
928 CanonicalForm elem;
929 Varlist ord, uord;
930 for (int ii= 1; ii < level (vf); ii++)
931 uord.append (Variable (ii));
932
933 for (i= as; i.hasItem(); i++)
934 {
935 elem= i.getItem();
936 x= elem.mvar();
937 if (degree (elem, x) > 1) // otherwise it's not an extension
938 {
939 Astar.append (elem);
940 ord.append (x);
941 }
942 }
943 uord= Difference (uord, ord);
944
945// 3) second trivial cases: we already proved irr. of f over no extensions
946 if (Astar.length() == 0)
947 {
948 if (!isRat && getCharacteristic() == 0)
950 return CFFList (CFFactor (f, 1));
951 }
952
953// 4) Look if elements in uord actually occur in any of the minimal
954// polynomials. If no element of uord occures in any of the minimal
955// polynomials the field is an alg. number field not an alg. function field
956 Varlist newuord= varsInAs (uord, Astar);
957
958 CFFList Factorlist;
959 Varlist gcdord= Union (ord, newuord);
960 gcdord.append (f.mvar());
961 bool isFunctionField= (newuord.length() > 0);
962
963 // TODO alg_sqrfree?
964 CanonicalForm Fgcd= 0;
965 if (isFunctionField)
966 Fgcd= alg_gcd (f, f.deriv(), Astar);
967
968 bool derivZero= f.deriv().isZero();
969 if (isFunctionField && (degree (Fgcd, f.mvar()) > 0) && !derivZero)
970 {
971 CanonicalForm Ggcd= divide(f, Fgcd,Astar);
972 if (getCharacteristic() == 0)
973 {
974 CFFList result= facAlgFunc2 (Ggcd, as); //Ggcd is the squarefree part of f
975 multiplicity (result, f, Astar);
976 if (!isRat && getCharacteristic() == 0)
978 return result;
979 }
980
981 Fgcd= pp (Fgcd);
982 Ggcd= pp (Ggcd);
983 if (!isRat && getCharacteristic() == 0)
985 return merge (facAlgFunc2 (Fgcd, as), facAlgFunc2 (Ggcd, as));
986 }
987
988 if (getCharacteristic() > 0)
989 {
990 IntList degreelist;
991 Variable vminpoly;
992 for (i= Astar; i.hasItem(); i++)
993 degreelist.append (degree (i.getItem()));
994
995 int extdeg= getDegOfExt (degreelist, degree (f));
996
997 if (newuord.length() == 0) // no parameters
998 {
999 if (extdeg > 1)
1000 {
1001 CanonicalForm MIPO= generateMipo (extdeg);
1002 vminpoly= rootOf(MIPO);
1003 }
1004 Factorlist= Trager(f, Astar, vminpoly, as, isFunctionField);
1005 if (extdeg > 1)
1006 prune (vminpoly);
1007 return Factorlist;
1008 }
1009 else if (isInseparable(Astar) || derivZero) // inseparable case
1010 {
1011 Factorlist= SteelTrager (f, Astar);
1012 return Factorlist;
1013 }
1014 else // separable case
1015 {
1016 if (extdeg > 1)
1017 {
1018 CanonicalForm MIPO=generateMipo (extdeg);
1019 vminpoly= rootOf (MIPO);
1020 }
1021 Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
1022 if (extdeg > 1)
1023 prune (vminpoly);
1024 return Factorlist;
1025 }
1026 }
1027 else // char 0
1028 {
1029 Variable vminpoly;
1030 Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
1031 if (!isRat && getCharacteristic() == 0)
1032 Off (SW_RATIONAL);
1033 return Factorlist;
1034 }
1035
1036 return CFFList (CFFactor(f,1));
1037}
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition cf_gcd.cc:676
List< int > IntList
List< Variable > Varlist
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
void append(const T &)
int level() const
Definition factory.h:143
Varlist varsInAs(const Varlist &uord, const CFList &Astar)
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
int getDegOfExt(IntList &degreelist, int n)
bool isInseparable(const CFList &Astar)
CanonicalForm generateMipo(int degOfExt)
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
Definition facAlgFunc.cc:61
CFFList SteelTrager(const CanonicalForm &f, const CFList &AS)
algorithm of A. Steel described in "Conquering Inseparability: Primarydecomposition and multivariate ...
static CFFList Trager(const CanonicalForm &F, const CFList &Astar, const Variable &vminpoly, const CFList &as, bool isFunctionField)
Trager's algorithm, i.e. convert to one field extension and factorize over this field extension.
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition variable.cc:162
void FACTORY_PUBLIC prune(Variable &alpha)
Definition variable.cc:261
STATIC_VAR int * multiplicity

◆ factorize() [1/2]

CFFList FACTORY_PUBLIC factorize ( const CanonicalForm & f,
bool issqrfree = false )

factorization over $ F_p $ or $ Q $

Definition at line 409 of file cf_factor.cc.

410{
411 if ( f.inCoeffDomain() )
412 return CFFList( f );
413#ifndef NOASSERT
414 Variable a;
415 ASSERT (!hasFirstAlgVar (f, a), "f has an algebraic variable use factorize \
416 ( const CanonicalForm & f, const Variable & alpha ) instead");
417#endif
418 //out_cf("factorize:",f,"==================================\n");
419 if (! f.isUnivariate() ) // preprocess homog. polys
420 {
421 if ( singular_homog_flag && f.isHomogeneous())
422 {
424 int d_xn = degree(f,xn);
425 CFMap n;
426 CanonicalForm F = compress(f(1,xn),n);
427 CFFList Intermediatelist;
428 Intermediatelist = factorize(F);
429 CFFList Homoglist;
431 for ( j=Intermediatelist; j.hasItem(); j++ )
432 {
433 Homoglist.append(
434 CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
435 }
436 CFFList Unhomoglist;
437 CanonicalForm unhomogelem;
438 for ( j=Homoglist; j.hasItem(); j++ )
439 {
440 unhomogelem= homogenize(j.getItem().factor(),xn);
441 Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
442 d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
443 }
444 if ( d_xn != 0 ) // have to append xn^(d_xn)
445 Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
446 if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF);
447 return Unhomoglist;
448 }
449 }
450 CFFList F;
451 if ( getCharacteristic() > 0 )
452 {
453 if (f.isUnivariate())
454 {
455#ifdef HAVE_FLINT
456#ifdef HAVE_NTL
457 if (degree (f) < 300)
458#endif
459 {
460 // use FLINT: char p, univariate
461 nmod_poly_t f1;
463 nmod_poly_factor_t result;
464 nmod_poly_factor_init (result);
465 mp_limb_t leadingCoeff= nmod_poly_factor (result, f1);
466 F= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, f.mvar());
467 nmod_poly_factor_clear (result);
468 nmod_poly_clear (f1);
470 return F;
471 }
472#endif
473#ifdef HAVE_NTL
474 { // NTL char 2, univariate
475 if (getCharacteristic()==2)
476 {
477 // Specialcase characteristic==2
478 if (fac_NTL_char != 2)
479 {
480 fac_NTL_char = 2;
481 zz_p::init(2);
482 }
483 // convert to NTL using the faster conversion routine for characteristic 2
484 GF2X f1=convertFacCF2NTLGF2X(f);
485 // no make monic necessary in GF2
486 //factorize
487 vec_pair_GF2X_long factors;
488 CanZass(factors,f1);
489
490 // convert back to factory again using the faster conversion routine for vectors over GF2X
491 F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
493 return F;
494 }
495 }
496#endif
497#ifdef HAVE_NTL
498 {
499 // use NTL char p, univariate
501 {
503 zz_p::init(getCharacteristic());
504 }
505
506 // convert to NTL
507 zz_pX f1=convertFacCF2NTLzzpX(f);
508 zz_p leadcoeff = LeadCoeff(f1);
509
510 //make monic
511 f1=f1 / LeadCoeff(f1);
512 // factorize
513 vec_pair_zz_pX_long factors;
514 CanZass(factors,f1);
515
516 F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
517 //test_cff(F,f);
519 return F;
520 }
521#endif
522#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
523 // Use Factory without NTL and without FLINT: char p, univariate
524 {
525 if ( isOn( SW_BERLEKAMP ) )
526 F=FpFactorizeUnivariateB( f, issqrfree );
527 else
528 F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() );
529 return F;
530 }
531#endif
532 }
533 else // char p, multivariate
534 {
536 {
537 #if defined(HAVE_NTL)
538 if (issqrfree)
539 {
540 CFList factors;
542 factors= GFSqrfFactorize (f);
543 for (CFListIterator i= factors; i.hasItem(); i++)
544 F.append (CFFactor (i.getItem(), 1));
545 }
546 else
547 {
549 F= GFFactorize (f);
550 }
551 #else
552 factoryError ("multivariate factorization over GF depends on NTL(missing)");
553 return CFFList (CFFactor (f, 1));
554 #endif
555 }
556 else
557 {
558 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
559 if (!isOn(SW_USE_FL_FAC_P))
560 {
561 #endif
562 #if defined(HAVE_NTL)
563 if (issqrfree)
564 {
565 CFList factors;
567 factors= FpSqrfFactorize (f);
568 for (CFListIterator i= factors; i.hasItem(); i++)
569 F.append (CFFactor (i.getItem(), 1));
570 goto end_charp;
571 }
572 else
573 {
575 F= FpFactorize (f);
576 goto end_charp;
577 }
578 #endif
579 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
580 }
581 #endif
582 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
583 nmod_mpoly_ctx_t ctx;
584 nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,getCharacteristic());
585 nmod_mpoly_t Flint_f;
586 nmod_mpoly_init(Flint_f,ctx);
587 convFactoryPFlintMP(f,Flint_f,ctx,f.level());
588 nmod_mpoly_factor_t factors;
589 nmod_mpoly_factor_init(factors,ctx);
590 int okay;
591 if (issqrfree) okay=nmod_mpoly_factor_squarefree(factors,Flint_f,ctx);
592 else okay=nmod_mpoly_factor(factors,Flint_f,ctx);
593 nmod_mpoly_t fac;
594 nmod_mpoly_init(fac,ctx);
595 CanonicalForm cf_fac;
596 int cf_exp;
597 cf_fac=nmod_mpoly_factor_get_constant_ui(factors,ctx);
598 F.append(CFFactor(cf_fac,1));
599 for(int i=nmod_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
600 {
601 nmod_mpoly_factor_get_base(fac,factors,i,ctx);
602 cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
603 cf_exp=nmod_mpoly_factor_get_exp_si(factors,i,ctx);
604 F.append(CFFactor(cf_fac,cf_exp));
605 }
606 nmod_mpoly_factor_clear(factors,ctx);
607 nmod_mpoly_clear(Flint_f,ctx);
608 nmod_mpoly_ctx_clear(ctx);
609 if (okay==0)
610 {
613 F=factorize(f,issqrfree);
616 }
617 #endif
618 #if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
619 #ifndef HAVE_NTL
620 factoryError ("multivariate factorization depends on NTL/FLINT(missing)");
621 return CFFList (CFFactor (f, 1));
622 #endif
623 #endif
624 }
625 }
626 }
627 else // char 0
628 {
629 bool on_rational = isOn(SW_RATIONAL);
632 CanonicalForm fz = f * cd;
634 if ( f.isUnivariate() )
635 {
636 CanonicalForm ic=icontent(fz);
637 fz/=ic;
638 if (fz.degree()==1)
639 {
640 F=CFFList(CFFactor(fz,1));
641 F.insert(CFFactor(ic,1));
642 }
643 else
644 #if defined(HAVE_FLINT) && (__FLINT_RELEASE>=20503) && (__FLINT_RELEASE!= 20600)
645 {
646 // FLINT 2.6.0 has a bug:
647 // factorize x^12-13*x^10-13*x^8+13*x^4+13*x^2-1 runs forever
648 // use FLINT: char 0, univariate
649 fmpz_poly_t f1;
651 fmpz_poly_factor_t result;
652 fmpz_poly_factor_init (result);
653 fmpz_poly_factor(result, f1);
655 fmpz_poly_factor_clear (result);
656 fmpz_poly_clear (f1);
657 if ( ! ic.isOne() )
658 {
659 // according to convertFLINTfmpz_polyfactor2FcaCFFlist,
660 // first entry is in CoeffDomain
661 CFFactor new_first( F.getFirst().factor() * ic );
662 F.removeFirst();
663 F.insert( new_first );
664 }
665 }
666 goto end_char0;
667 #elif defined(HAVE_NTL)
668 {
669 //use NTL
670 ZZ c;
671 vec_pair_ZZX_long factors;
672 //factorize the converted polynomial
673 factor(c,factors,convertFacCF2NTLZZX(fz));
674
675 //convert the result back to Factory
677 if ( ! ic.isOne() )
678 {
679 // according to convertNTLvec_pair_ZZX_long2FacCFFList
680 // first entry is in CoeffDomain
681 CFFactor new_first( F.getFirst().factor() * ic );
682 F.removeFirst();
683 F.insert( new_first );
684 }
685 }
686 goto end_char0;
687 #else
688 {
689 //Use Factory without NTL: char 0, univariate
690 F = ZFactorizeUnivariate( fz, issqrfree );
691 goto end_char0;
692 }
693 #endif
694 }
695 else // multivariate, char 0
696 {
697 #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
699 {
700 On (SW_RATIONAL);
701 fmpz_mpoly_ctx_t ctx;
702 fmpz_mpoly_ctx_init(ctx,f.level(),ORD_LEX);
703 fmpz_mpoly_t Flint_f;
704 fmpz_mpoly_init(Flint_f,ctx);
705 convFactoryPFlintMP(fz,Flint_f,ctx,fz.level());
706 fmpz_mpoly_factor_t factors;
707 fmpz_mpoly_factor_init(factors,ctx);
708 int rr;
709 if (issqrfree) rr=fmpz_mpoly_factor_squarefree(factors,Flint_f,ctx);
710 else rr=fmpz_mpoly_factor(factors,Flint_f,ctx);
711 if (rr==0) printf("fail\n");
712 fmpz_mpoly_t fac;
713 fmpz_mpoly_init(fac,ctx);
714 CanonicalForm cf_fac;
715 int cf_exp;
716 fmpz_t c;
717 fmpz_init(c);
718 fmpz_mpoly_factor_get_constant_fmpz(c,factors,ctx);
719 cf_fac=convertFmpz2CF(c);
720 fmpz_clear(c);
721 F.append(CFFactor(cf_fac,1));
722 for(int i=fmpz_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
723 {
724 fmpz_mpoly_factor_get_base(fac,factors,i,ctx);
725 cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
726 cf_exp=fmpz_mpoly_factor_get_exp_si(factors,i,ctx);
727 F.append(CFFactor(cf_fac,cf_exp));
728 }
729 fmpz_mpoly_factor_clear(factors,ctx);
730 fmpz_mpoly_clear(Flint_f,ctx);
731 fmpz_mpoly_ctx_clear(ctx);
732 goto end_char0;
733 }
734 #endif
735 #if defined(HAVE_NTL)
736 On (SW_RATIONAL);
737 if (issqrfree)
738 {
739 CFList factors= ratSqrfFactorize (fz);
740 for (CFListIterator i= factors; i.hasItem(); i++)
741 F.append (CFFactor (i.getItem(), 1));
742 }
743 else
744 {
745 F = ratFactorize (fz);
746 }
747 #endif
748 #if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
749 #ifndef HAVE_NTL
750 F=ZFactorizeMultivariate(fz, issqrfree);
751 #endif
752 #endif
753 }
754
755end_char0:
756 if ( on_rational )
758 else
760 if ( ! cd.isOne() )
761 {
762 CFFactor new_first( F.getFirst().factor() / cd );
763 F.removeFirst();
764 F.insert( new_first );
765 }
766 }
767
768#if defined(HAVE_NTL)
769end_charp:
770#endif
772 return F;
773}
CanonicalForm convertFmpz2CF(const fmpz_t coefficient)
conversion of a FLINT integer to CanonicalForm
CFFList convertFLINTnmod_poly_factor2FacCFFList(const nmod_poly_factor_t fac, const mp_limb_t leadingCoeff, const Variable &x)
conversion of a FLINT factorization over Z/p (for word size p) to a CFFList
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
CFFList convertFLINTfmpz_poly_factor2FacCFFList(const fmpz_poly_factor_t fac, const Variable &x)
conversion of a FLINT factorization over Z to a CFFList
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p cont, const Variable &x)
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
CFFList convertNTLvec_pair_ZZX_long2FacCFFList(const vec_pair_ZZX_long &e, const ZZ &cont, const Variable &x)
NAME: convertNTLvec_pair_ZZX_long2FacCFFList.
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition cf_ops.cc:679
CanonicalForm cd(bCommonDen(FF))
Definition cfModGcd.cc:4097
EXTERN_VAR int singular_homog_flag
static const int SW_USE_FL_GCD_P
set to 1 to use Flints gcd over F_p
Definition cf_defs.h:47
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition cf_defs.h:39
static const int SW_USE_FL_FAC_0
set to 1 to prefer flints multivariate factorization over Z/p
Definition cf_defs.h:57
static const int SW_USE_FL_FAC_P
set to 1 to prefer flints multivariate factorization over Z/p
Definition cf_defs.h:55
static const int SW_BERLEKAMP
set to 1 to use Factorys Berlekamp alg.
Definition cf_defs.h:51
Variable get_max_degree_Variable(const CanonicalForm &f)
get_max_degree_Variable returns Variable with highest degree.
Definition cf_factor.cc:264
int cmpCF(const CFFactor &f, const CFFactor &g)
Definition cf_factor.cc:398
CanonicalForm homogenize(const CanonicalForm &f, const Variable &x)
homogenize homogenizes f with Variable x
Definition cf_factor.cc:317
CFFList factorize(const CanonicalForm &f, bool issqrfree)
factorization over or
Definition cf_factor.cc:409
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition cf_map.cc:210
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
CF_NO_INLINE bool isOne() const
void sort(int(*)(const T &, const T &))
void insert(const T &)
Variable alpha
CanonicalForm factor
Definition facAbsFact.cc:97
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
CFList ratSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree multivariate polynomial over
CFList FpSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
CFList GFSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over GF
CFFList FpFactorizeUnivariateB(const CanonicalForm &f, bool issqrfree=false)
CFFList FpFactorizeUnivariateCZ(const CanonicalForm &f, bool issqrfree, int numext, const Variable alpha, const Variable beta)
CFFList ZFactorizeMultivariate(const CanonicalForm &f, bool issqrfree)
CFFList ZFactorizeUnivariate(const CanonicalForm &ff, bool issqrfree=false)
VAR int xn
Definition walk.cc:4509

◆ factorize() [2/2]

CFFList FACTORY_PUBLIC factorize ( const CanonicalForm & f,
const Variable & alpha )

factorization over $ F_p(\alpha) $ or $ Q(\alpha) $

Definition at line 778 of file cf_factor.cc.

779{
780 if ( f.inCoeffDomain() )
781 return CFFList( f );
782 //out_cf("factorize:",f,"==================================\n");
783 //out_cf("mipo:",getMipo(alpha),"\n");
784
785 CFFList F;
786 ASSERT( alpha.level() < 0 && getReduce (alpha), "not an algebraic extension" );
787#ifndef NOASSERT
789 if (hasFirstAlgVar(f, beta))
790 ASSERT (beta == alpha, "f has an algebraic variable that \
791 does not coincide with alpha");
792#endif
793 int ch=getCharacteristic();
794 if (ch>0)
795 {
796 if (f.isUnivariate())
797 {
798#ifdef HAVE_NTL
799 if (/*getCharacteristic()*/ch==2)
800 {
801 // special case : GF2
802
803 // remainder is two ==> nothing to do
804
805 // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
806 GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
807 GF2E::init (minPo);
808
809 // convert to NTL again using the faster conversion routines
810 GF2EX f1;
811 if (isPurePoly(f))
812 {
813 GF2X f_tmp=convertFacCF2NTLGF2X(f);
814 f1=to_GF2EX(f_tmp);
815 }
816 else
817 f1=convertFacCF2NTLGF2EX(f,minPo);
818
819 // make monic (in Z/2(a))
820 GF2E f1_coef=LeadCoeff(f1);
821 MakeMonic(f1);
822
823 // factorize using NTL
824 vec_pair_GF2EX_long factors;
825 CanZass(factors,f1);
826
827 // return converted result
828 F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
830 return F;
831 }
832#endif
833#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
834 {
835 // use FLINT
836 nmod_poly_t FLINTmipo, leadingCoeff;
837 fq_nmod_ctx_t fq_con;
838
839 nmod_poly_init (FLINTmipo, ch);
840 nmod_poly_init (leadingCoeff, ch);
842
843 fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
844 fq_nmod_poly_t FLINTF;
846 fq_nmod_poly_factor_t res;
847 fq_nmod_poly_factor_init (res, fq_con);
848 fq_nmod_poly_factor (res, leadingCoeff, FLINTF, fq_con);
850 F.insert (CFFactor (Lc (f), 1));
851
852 fq_nmod_poly_factor_clear (res, fq_con);
853 fq_nmod_poly_clear (FLINTF, fq_con);
854 nmod_poly_clear (FLINTmipo);
855 nmod_poly_clear (leadingCoeff);
858 return F;
859 }
860#endif
861#ifdef HAVE_NTL
862 {
863 // use NTL
864 if (fac_NTL_char != ch)
865 {
866 fac_NTL_char = ch;
867 zz_p::init(ch);
868 }
869
870 // set minimal polynomial in NTL
871 zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
872 zz_pE::init (minPo);
873
874 // convert to NTL
875 zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
876 zz_pE leadcoeff= LeadCoeff(f1);
877
878 //make monic
879 f1=f1 / leadcoeff; //leadcoeff==LeadCoeff(f1);
880
881 // factorize
882 vec_pair_zz_pEX_long factors;
883 CanZass(factors,f1);
884
885 // return converted result
886 F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
887 //test_cff(F,f);
889 return F;
890 }
891#endif
892#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
893 // char p, extension, univariate
894 CanonicalForm c=Lc(f);
895 CanonicalForm fc=f/c;
896 F=FpFactorizeUnivariateCZ( fc, false, 1, alpha, Variable() );
897 F.insert (CFFactor (c, 1));
898#endif
899 }
900 else // char p, multivariate
901 {
902 #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
903 // use FLINT
904 nmod_poly_t FLINTmipo;
905 fq_nmod_ctx_t fq_con;
906 fq_nmod_mpoly_ctx_t ctx;
907
908 nmod_poly_init (FLINTmipo, ch);
910
911 fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
912 fq_nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,fq_con);
913
914 fq_nmod_mpoly_t FLINTF;
915 fq_nmod_mpoly_init(FLINTF,ctx);
916 convertFacCF2Fq_nmod_mpoly_t(FLINTF,f,ctx,f.level(),fq_con);
917 fq_nmod_mpoly_factor_t res;
918 fq_nmod_mpoly_factor_init (res, ctx);
919 fq_nmod_mpoly_factor (res, FLINTF, ctx);
920 F= convertFLINTFq_nmod_mpoly_factor2FacCFFList (res, ctx,f.level(),fq_con,alpha);
921 //F.insert (CFFactor (Lc (f), 1));
922
923 fq_nmod_mpoly_factor_clear (res, ctx);
924 fq_nmod_mpoly_clear (FLINTF, ctx);
925 nmod_poly_clear (FLINTmipo);
926 fq_nmod_mpoly_ctx_clear (ctx);
929 return F;
930 #elif defined(HAVE_NTL)
931 F= FqFactorize (f, alpha);
932 #else
933 factoryError ("multivariate factorization over Z/pZ(alpha) depends on NTL/Flint(missing)");
934 return CFFList (CFFactor (f, 1));
935 #endif
936 }
937 }
938 else // Q(a)[x]
939 {
940 if (f.isUnivariate())
941 {
942 F= AlgExtFactorize (f, alpha);
943 }
944 else //Q(a)[x1,...,xn]
945 {
946 #if defined(HAVE_NTL) || defined(HAVE_FLINT)
947 F= ratFactorize (f, alpha);
948 #else
949 factoryError ("multivariate factorization over Q(alpha) depends on NTL or FLINT (missing)");
950 return CFFList (CFFactor (f, 1));
951 #endif
952 }
953 }
955 return F;
956}
CFFList convertFLINTFq_nmod_poly_factor2FacCFFList(const fq_nmod_poly_factor_t fac, const Variable &x, const Variable &alpha, const fq_nmod_ctx_t fq_con)
conversion of a FLINT factorization over Fq (for word size p) to a CFFList
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &cont, const Variable &x, const Variable &alpha)
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &cont, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
bool isPurePoly(const CanonicalForm &f)
Definition cf_factor.cc:248
CanonicalForm res
Definition facAbsFact.cc:60
Variable beta
Definition facAbsFact.cc:95
CFFList AlgExtFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a univariate polynomial over algebraic extension of Q
Definition facAlgExt.cc:370
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
fq_nmod_ctx_t fq_con
Definition facHensel.cc:99
fq_nmod_ctx_clear(fq_con)
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207

◆ factoryError_intern()

void factoryError_intern ( const char * s)

Definition at line 75 of file cf_util.cc.

76{
77 fputs(s,stderr);
78 abort();
79}

◆ factoryrandom()

int factoryrandom ( int n)

random integers with abs less than n

Definition at line 180 of file cf_random.cc.

181{
182 if ( n == 0 )
183 return (int)ranGen.generate();
184 else
185 return ranGen.generate() % n;
186}
INST_VAR RandomGenerator ranGen
Definition cf_random.cc:66

◆ factoryseed()

void FACTORY_PUBLIC factoryseed ( int s)

random seed initializer

Definition at line 189 of file cf_random.cc.

190{
191 ranGen.seed( s );
192
193#ifdef HAVE_FLINT
194 flint_randinit(FLINTrandom);
195#endif
196}
GLOBAL_VAR flint_rand_t FLINTrandom
Definition cf_random.cc:25

◆ Farey()

Farey rational reconstruction.

If NTL is available it uses the fast algorithm from NTL, i.e. Encarnacion, Collins.

Definition at line 202 of file cf_chinese.cc.

203{
204 int is_rat=isOn(SW_RATIONAL);
206 Variable x = f.mvar();
210#ifdef HAVE_FLINT
211 fmpz_t FLINTq;
212 fmpz_init(FLINTq);
213 convertCF2initFmpz(FLINTq,q);
214 fmpz_t FLINTc;
215 fmpz_init(FLINTc);
216 fmpq_t FLINTres;
217 fmpq_init(FLINTres);
218#elif defined(HAVE_NTL)
219 ZZ NTLq= convertFacCF2NTLZZ (q);
220 ZZ bound;
221 SqrRoot (bound, NTLq/2);
222#else
223 factoryError("NTL/FLINT missing:Farey");
224#endif
225 for ( i = f; i.hasTerms(); i++ )
226 {
227 c = i.coeff();
228 if ( c.inCoeffDomain())
229 {
230#ifdef HAVE_FLINT
231 if (c.inZ())
232 {
233 convertCF2initFmpz(FLINTc,c);
234 fmpq_reconstruct_fmpz(FLINTres,FLINTc,FLINTq);
235 result += power (x, i.exp())*(convertFmpq2CF(FLINTres));
236 }
237#elif defined(HAVE_NTL)
238 if (c.inZ())
239 {
240 ZZ NTLc= convertFacCF2NTLZZ (c);
241 bool lessZero= (sign (NTLc) == -1);
242 if (lessZero)
243 NTL::negate (NTLc, NTLc);
244 ZZ NTLnum, NTLden;
245 if (ReconstructRational (NTLnum, NTLden, NTLc, NTLq, bound, bound))
246 {
247 if (lessZero)
248 NTL::negate (NTLnum, NTLnum);
249 CanonicalForm num= convertNTLZZX2CF (to_ZZX (NTLnum), Variable (1));
250 CanonicalForm den= convertNTLZZX2CF (to_ZZX (NTLden), Variable (1));
251 On (SW_RATIONAL);
252 result += power (x, i.exp())*(num/den);
254 }
255 }
256#else
257 if (c.inZ())
258 result += power (x, i.exp()) * Farey_n(c,q);
259#endif
260 else
261 result += power( x, i.exp() ) * Farey(c,q);
262 }
263 else
264 result += power( x, i.exp() ) * Farey(c,q);
265 }
266 if (is_rat) On(SW_RATIONAL);
267#ifdef HAVE_FLINT
268 fmpq_clear(FLINTres);
269 fmpz_clear(FLINTc);
270 fmpz_clear(FLINTq);
271#endif
272 return result;
273}
CanonicalForm convertFmpq2CF(const fmpq_t q)
conversion of a FLINT rational to CanonicalForm
void convertCF2initFmpz(fmpz_t result, const CanonicalForm &f)
conversion of a factory integer to fmpz_t(init.)
CanonicalForm num(const CanonicalForm &f)
CanonicalForm den(const CanonicalForm &f)
CanonicalForm Farey(const CanonicalForm &f, const CanonicalForm &q)
Farey rational reconstruction.
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
bool inZ() const
predicates

◆ fdivides() [1/2]

bool fdivides ( const CanonicalForm & f,
const CanonicalForm & g )

bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )

fdivides() - check whether ‘f’ divides ‘g’.

Returns true iff ‘f’ divides ‘g’. Uses some extra heuristic to avoid polynomial division. Without the heuristic, the test essentialy looks like ‘divremt(g, f, q, r) && r.isZero()’.

Type info:

f, g: Current

Elements from prime power domains (or polynomials over such domains) are admissible if ‘f’ (or lc(‘f’), resp.) is not a zero divisor. This is a slightly stronger precondition than mathematically necessary since divisibility is a well-defined notion in arbitrary rings. Hence, we decided not to declare the weaker type ‘CurrentPP’.

Developers note:

One may consider the the test ‘fdivides( f.LC(), g.LC() )’ in the main ‘if’-test superfluous since ‘divremt()’ in the ‘if’-body repeats the test. However, ‘divremt()’ does not use any heuristic to do so.

It seems not reasonable to call ‘fdivides()’ from ‘divremt()’ to check divisibility of leading coefficients. ‘fdivides()’ is on a relatively high level compared to ‘divremt()’.

Definition at line 340 of file cf_algorithm.cc.

341{
342 // trivial cases
343 if ( g.isZero() )
344 return true;
345 else if ( f.isZero() )
346 return false;
347
348 if ( (f.inCoeffDomain() || g.inCoeffDomain())
349 && ((getCharacteristic() == 0 && isOn( SW_RATIONAL ))
350 || (getCharacteristic() > 0) ))
351 {
352 // if we are in a field all elements not equal to zero are units
353 if ( f.inCoeffDomain() )
354 return true;
355 else
356 // g.inCoeffDomain()
357 return false;
358 }
359
360 // we may assume now that both levels either equal LEVELBASE
361 // or are greater zero
362 int fLevel = f.level();
363 int gLevel = g.level();
364 if ( (gLevel > 0) && (fLevel == gLevel) )
365 // f and g are polynomials in the same main variable
366 if ( degree( f ) <= degree( g )
367 && fdivides( f.tailcoeff(), g.tailcoeff() )
368 && fdivides( f.LC(), g.LC() ) )
369 {
370 CanonicalForm q, r;
371 return divremt( g, f, q, r ) && r.isZero();
372 }
373 else
374 return false;
375 else if ( gLevel < fLevel )
376 // g is a coefficient w.r.t. f
377 return false;
378 else
379 {
380 // either f is a coefficient w.r.t. polynomial g or both
381 // f and g are from a base domain (should be Z or Z/p^n,
382 // then)
383 CanonicalForm q, r;
384 return divremt( g, f, q, r ) && r.isZero();
385 }
386}
bool divremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )

◆ fdivides() [2/2]

bool fdivides ( const CanonicalForm & f,
const CanonicalForm & g,
CanonicalForm & quot )

same as fdivides if true returns quotient quot of g by f otherwise quot == 0

Definition at line 390 of file cf_algorithm.cc.

391{
392 quot= 0;
393 // trivial cases
394 if ( g.isZero() )
395 return true;
396 else if ( f.isZero() )
397 return false;
398
399 if ( (f.inCoeffDomain() || g.inCoeffDomain())
400 && ((getCharacteristic() == 0 && isOn( SW_RATIONAL ))
401 || (getCharacteristic() > 0) ))
402 {
403 // if we are in a field all elements not equal to zero are units
404 if ( f.inCoeffDomain() )
405 {
406 quot= g/f;
407 return true;
408 }
409 else
410 // g.inCoeffDomain()
411 return false;
412 }
413
414 // we may assume now that both levels either equal LEVELBASE
415 // or are greater zero
416 int fLevel = f.level();
417 int gLevel = g.level();
418 if ( (gLevel > 0) && (fLevel == gLevel) )
419 // f and g are polynomials in the same main variable
420 if ( degree( f ) <= degree( g )
421 && fdivides( f.tailcoeff(), g.tailcoeff() )
422 && fdivides( f.LC(), g.LC() ) )
423 {
424 CanonicalForm q, r;
425 if (divremt( g, f, q, r ) && r.isZero())
426 {
427 quot= q;
428 return true;
429 }
430 else
431 return false;
432 }
433 else
434 return false;
435 else if ( gLevel < fLevel )
436 // g is a coefficient w.r.t. f
437 return false;
438 else
439 {
440 // either f is a coefficient w.r.t. polynomial g or both
441 // f and g are from a base domain (should be Z or Z/p^n,
442 // then)
443 CanonicalForm q, r;
444 if (divremt( g, f, q, r ) && r.isZero())
445 {
446 quot= q;
447 return true;
448 }
449 else
450 return false;
451 }
452}

◆ gcd()

Definition at line 685 of file cf_gcd.cc.

686{
687 bool b = f.isZero();
688 if ( b || g.isZero() )
689 {
690 if ( b )
691 return abs( g );
692 else
693 return abs( f );
694 }
695 if ( f.inPolyDomain() || g.inPolyDomain() )
696 {
697 if ( f.mvar() != g.mvar() )
698 {
699 if ( f.mvar() > g.mvar() )
700 return cf_content( f, g );
701 else
702 return cf_content( g, f );
703 }
704 if (isOn(SW_USE_QGCD))
705 {
706 Variable m;
707 if (
708 (getCharacteristic() == 0) &&
710 )
711 {
712 bool on_rational = isOn(SW_RATIONAL);
715 CanonicalForm cdF = bCommonDen( r );
716 if (!on_rational) Off(SW_RATIONAL);
717 return cdF*r;
718 }
719 }
720
721 if ( f.inExtension() && getReduce( f.mvar() ) )
722 return CanonicalForm(1);
723 else
724 {
725 if ( fdivides( f, g ) )
726 return abs( f );
727 else if ( fdivides( g, f ) )
728 return abs( g );
729 if ( !( getCharacteristic() == 0 && isOn( SW_RATIONAL ) ) )
730 {
732 d = gcd_poly( f, g );
733 return abs( d );
734 }
735 else
736 {
737 CanonicalForm cdF = bCommonDen( f );
738 CanonicalForm cdG = bCommonDen( g );
739 CanonicalForm F = f * cdF, G = g * cdG;
740 Off( SW_RATIONAL );
741 CanonicalForm l = gcd_poly( F, G );
742 On( SW_RATIONAL );
743 return abs( l );
744 }
745 }
746 }
747 if ( f.inBaseDomain() && g.inBaseDomain() )
748 return bgcd( f, g );
749 else
750 return 1;
751}
CanonicalForm QGCD(const CanonicalForm &F, const CanonicalForm &G)
gcd over Q(a)
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition cf_defs.h:43
CanonicalForm gcd_poly(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
Definition cf_gcd.cc:492

◆ gcd_poly()

CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )

gcd_poly() - calculate polynomial gcd.

This is the dispatcher for polynomial gcd calculation. Different gcd variants get called depending the input, characteristic, and on switches (cf_defs.h)

With the current settings from Singular (i.e. SW_USE_EZGCD= on, SW_USE_EZGCD_P= on, SW_USE_CHINREM_GCD= on, the EZ GCD variants are the default algorithms for multivariate polynomial GCD computations)

See also
gcd(), cf_defs.h

Definition at line 492 of file cf_gcd.cc.

493{
494 CanonicalForm fc, gc;
495 bool fc_isUnivariate=f.isUnivariate();
496 bool gc_isUnivariate=g.isUnivariate();
497 bool fc_and_gc_Univariate=fc_isUnivariate && gc_isUnivariate;
498 fc = f;
499 gc = g;
500 int ch=getCharacteristic();
501 if ( ch != 0 )
502 {
503 if (0) {} // dummy, to be able to build without NTL and FLINT
504 #if defined(HAVE_FLINT) && ( __FLINT_RELEASE >= 20503)
505 if ( isOn( SW_USE_FL_GCD_P)
507 #ifdef HAVE_NTL
508 && (ch>10) // if we have NTL: it is better for char <11
509 #endif
510 &&(!hasAlgVar(fc)) && (!hasAlgVar(gc)))
511 {
512 return gcdFlintMP_Zp(fc,gc);
513 }
514 #endif
515 #ifdef HAVE_NTL
516 if ((!fc_and_gc_Univariate) && (isOn( SW_USE_EZGCD_P )))
517 {
518 fc= EZGCD_P (fc, gc);
519 }
520 #endif
521 #if defined(HAVE_NTL) || defined(HAVE_FLINT)
522 else if (isOn(SW_USE_FF_MOD_GCD) && !fc_and_gc_Univariate)
523 {
524 Variable a;
525 if (hasFirstAlgVar (fc, a) || hasFirstAlgVar (gc, a))
526 fc=modGCDFq (fc, gc, a);
528 fc=modGCDGF (fc, gc);
529 else
530 fc=modGCDFp (fc, gc);
531 }
532 #endif
533 else
534 fc = gcd_poly_p( fc, gc );
535 }
536 else if (!fc_and_gc_Univariate) /* && char==0*/
537 {
538 #if defined(HAVE_FLINT) && ( __FLINT_RELEASE >= 20503)
539 if (( isOn( SW_USE_FL_GCD_0) )
540 &&(!hasAlgVar(fc)) && (!hasAlgVar(gc)))
541 {
542 return gcdFlintMP_QQ(fc,gc);
543 }
544 else
545 #endif
546 #ifdef HAVE_NTL
547 if ( isOn( SW_USE_EZGCD ) )
548 fc= ezgcd (fc, gc);
549 else
550 #endif
551 #if defined(HAVE_NTL) || defined(HAVE_FLINT)
553 fc = modGCDZ( fc, gc);
554 else
555 #endif
556 {
557 fc = gcd_poly_0( fc, gc );
558 }
559 }
560 else
561 {
562 fc = gcd_poly_0( fc, gc );
563 }
564 if ((ch>0)&&(!hasAlgVar(fc))) fc/=fc.lc();
565 return fc;
566}
CanonicalForm EZGCD_P(const CanonicalForm &FF, const CanonicalForm &GG)
Extended Zassenhaus GCD for finite fields. In case things become too dense we switch to a modular alg...
Definition cfEzgcd.cc:876
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
Definition cfEzgcd.cc:498
CanonicalForm modGCDFq(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, Variable &alpha, CFList &l, bool &topLevel)
GCD of F and G over , l and topLevel are only used internally, output is monic based on Alg....
Definition cfModGcd.cc:479
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition cfModGcd.cc:1224
CanonicalForm modGCDGF(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, CFList &l, bool &topLevel)
GCD of F and G over GF, based on Alg. 7.2. as described in "Algorithms forComputer Algebra" by Geddes...
Definition cfModGcd.cc:873
CanonicalForm modGCDZ(const CanonicalForm &FF, const CanonicalForm &GG)
modular GCD over Z
static const int SW_USE_CHINREM_GCD
set to 1 to use modular gcd over Z
Definition cf_defs.h:41
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition cf_defs.h:37
static const int SW_USE_FF_MOD_GCD
set to 1 to use modular GCD over F_q
Definition cf_defs.h:45
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
Definition cf_defs.h:35
static const int SW_USE_FL_GCD_0
set to 1 to use Flints gcd over Q/Z
Definition cf_defs.h:49
static CanonicalForm gcd_poly_0(const CanonicalForm &f, const CanonicalForm &g)
Definition cf_gcd.cc:417
static CanonicalForm gcd_poly_p(const CanonicalForm &f, const CanonicalForm &g)
Definition cf_gcd.cc:264
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
int hasAlgVar(const CanonicalForm &f, const Variable &v)

◆ get_max_degree_Variable()

Variable get_max_degree_Variable ( const CanonicalForm & f)

get_max_degree_Variable returns Variable with highest degree.

We assume f is not a constant!

Definition at line 264 of file cf_factor.cc.

265{
266 ASSERT( ( ! f.inCoeffDomain() ), "no constants" );
267 int max=0, maxlevel=0, n=level(f);
268 for ( int i=1; i<=n; i++ )
269 {
270 if (degree(f,Variable(i)) >= max)
271 {
272 max= degree(f,Variable(i)); maxlevel= i;
273 }
274 }
275 return Variable(maxlevel);
276}
static int max(int a, int b)
Definition fast_mult.cc:264

◆ get_Terms()

CFList get_Terms ( const CanonicalForm & f)

Definition at line 293 of file cf_factor.cc.

293 {
294 CFList result,dummy,dummy2;
297
298 if ( getNumVars(f) == 0 ) result.append(f);
299 else{
300 Variable _x(level(f));
301 for ( i=f; i.hasTerms(); i++ ){
302 getTerms(i.coeff(), 1, dummy);
303 for ( j=dummy; j.hasItem(); j++ )
304 result.append(j.getItem() * power(_x, i.exp()));
305
306 dummy= dummy2; // have to initalize new
307 }
308 }
309 return result;
310}
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition cf_ops.cc:314
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
Definition cf_factor.cc:283

◆ getCharacteristic()

int FACTORY_PUBLIC getCharacteristic ( )

Definition at line 70 of file cf_char.cc.

71{
72 return theCharacteristic;
73}
STATIC_VAR int theCharacteristic
Definition cf_char.cc:25

◆ getDefaultExtName()

char getDefaultExtName ( )

Definition at line 249 of file variable.cc.

250{
251 return default_name_ext;
252}
STATIC_VAR char default_name_ext
Definition variable.cc:45

◆ getDefaultVarName()

char getDefaultVarName ( )

Definition at line 244 of file variable.cc.

245{
246 return default_name;
247}
STATIC_VAR char default_name
Definition variable.cc:44

◆ getGFDegree()

int getGFDegree ( )

Definition at line 75 of file cf_char.cc.

76{
77 //ASSERT( theDegree > 0, "not in GF(q)" );
78 return theDegree;
79}
STATIC_VAR int theDegree
Definition cf_char.cc:26

◆ getGFGenerator()

CanonicalForm getGFGenerator ( )

Definition at line 81 of file cf_char.cc.

82{
83 ASSERT( theDegree > 1, "not in GF(q)" );
84 return int2imm_gf( 1 );
85}
InternalCF * int2imm_gf(long i)
Definition imm.h:106

◆ getMipo()

CanonicalForm getMipo ( const Variable & alpha,
const Variable & x )

Definition at line 207 of file variable.cc.

208{
209 ASSERT( alpha.level() < 0 && alpha.level() != LEVELBASE, "illegal extension" );
210 return CanonicalForm( algextensions[-alpha.level()].mipo()->copyObject() )(x,alpha);
211}
#define LEVELBASE
Definition cf_defs.h:25
STATIC_VAR ext_entry * algextensions
Definition variable.cc:41

◆ getNumVars()

int getNumVars ( const CanonicalForm & f)

int getNumVars ( const CanonicalForm & f )

getNumVars() - get number of polynomial variables in f.

Definition at line 314 of file cf_ops.cc.

315{
316 int n;
317 if ( f.inCoeffDomain() )
318 return 0;
319 else if ( (n = f.level()) == 1 )
320 return 1;
321 else
322 {
323 int * vars = NEW_ARRAY(int, n+1);
324 int i;
325 for ( i = n-1; i >=0; i-- ) vars[i] = 0;
326
327 // look for variables
328 for ( CFIterator I = f; I.hasTerms(); ++I )
329 fillVarsRec( I.coeff(), vars );
330
331 // count them
332 int m = 0;
333 for ( i = 1; i < n; i++ )
334 if ( vars[i] != 0 ) m++;
335
336 DELETE_ARRAY(vars);
337 // do not forget to count our own variable
338 return m+1;
339 }
340}
static void fillVarsRec(const CanonicalForm &f, int *vars)
static void fillVarsRec ( const CanonicalForm & f, int * vars )
Definition cf_ops.cc:296

◆ getTerms()

void getTerms ( const CanonicalForm & f,
const CanonicalForm & t,
CFList & result )

get_Terms: Split the polynomial in the containing terms.

getTerms: the real work is done here.

Definition at line 283 of file cf_factor.cc.

284{
285 if ( getNumVars(f) == 0 ) result.append(f*t);
286 else{
287 Variable x(level(f));
288 for ( CFIterator i=f; i.hasTerms(); i++ )
289 getTerms( i.coeff(), t*power(x,i.exp()), result);
290 }
291}

◆ getVars()

CanonicalForm getVars ( const CanonicalForm & f )

getVars() - get polynomial variables of f.

Return the product of all of them, 1 if there are not any.

Definition at line 350 of file cf_ops.cc.

351{
352 int n;
353 if ( f.inCoeffDomain() )
354 return 1;
355 else if ( (n = f.level()) == 1 )
356 return Variable( 1 );
357 else
358 {
359 int * vars = NEW_ARRAY(int, n+1);
360 int i;
361 for ( i = n; i >= 0; i-- ) vars[i] = 0;
362
363 // look for variables
364 for ( CFIterator I = f; I.hasTerms(); ++I )
365 fillVarsRec( I.coeff(), vars );
366
367 // multiply them all
369 for ( i = n; i > 0; i-- )
370 if ( vars[i] != 0 ) result *= Variable( i );
371
372 DELETE_ARRAY(vars);
373 // do not forget our own variable
374 return f.mvar() * result;
375 }
376}

◆ gf_gf2ff() [1/2]

int gf_gf2ff ( int a)

Definition at line 231 of file gfops.cc.

232{
233 if ( gf_iszero( a ) )
234 return 0;
235 else
236 {
237 // starting from z^0=1, step through the table
238 // counting the steps until we hit z^a or z^0
239 // again. since we are working in char(p), the
240 // latter is guaranteed to be fulfilled.
241 int i = 0, ff = 1;
242 do
243 {
244 if ( i == a )
245 return ff;
246 ff++;
247 i = gf_table[i];
248 } while ( i != 0 );
249 return -1;
250 }
251}
VAR unsigned short * gf_table
Definition gfops.cc:54
bool gf_iszero(int a)
Definition gfops.h:43

◆ gf_gf2ff() [2/2]

long gf_gf2ff ( long a)

Definition at line 209 of file gfops.cc.

210{
211 if ( gf_iszero( a ) )
212 return 0;
213 else
214 {
215 // starting from z^0=1, step through the table
216 // counting the steps until we hit z^a or z^0
217 // again. since we are working in char(p), the
218 // latter is guaranteed to be fulfilled.
219 long i = 0, ff = 1;
220 do
221 {
222 if ( i == a )
223 return ff;
224 ff++;
225 i = gf_table[i];
226 } while ( i != 0 );
227 return -1;
228 }
229}

◆ gf_isff() [1/2]

bool gf_isff ( int a)

Definition at line 264 of file gfops.cc.

265{
266 if ( gf_iszero( a ) )
267 return true;
268 else
269 {
270 // z^a in GF(p) iff (z^a)^p-1=1
271 return gf_isone( gf_power( a, gf_p - 1 ) );
272 }
273}
VAR int gf_p
Definition gfops.cc:48
bool gf_isone(int a)
Definition gfops.h:53
int gf_power(int a, int n)
Definition gfops.h:222

◆ gf_isff() [2/2]

bool gf_isff ( long a)

Definition at line 253 of file gfops.cc.

254{
255 if ( gf_iszero( a ) )
256 return true;
257 else
258 {
259 // z^a in GF(p) iff (z^a)^p-1=1
260 return gf_isone( gf_power( a, gf_p - 1 ) );
261 }
262}

◆ gf_value()

int gf_value ( const CanonicalForm & f)

Definition at line 60 of file singext.cc.

61{
62 InternalCF * ff = f.getval();
63 return ((intptr_t)ff) >>2;
64}
virtual class for internal CanonicalForm's
Definition int_cf.h:47

◆ gmp_denominator()

void FACTORY_PUBLIC gmp_denominator ( const CanonicalForm & f,
mpz_ptr result )

Definition at line 40 of file singext.cc.

41{
42 InternalCF * ff = f.getval();
43 ASSERT( ! is_imm( ff ), "illegal type" );
44 if ( ff->levelcoeff() == IntegerDomain )
45 {
46 mpz_init_set_si( result, 1 );
47 ff->deleteObject();
48 }
49 else if ( ff->levelcoeff() == RationalDomain )
50 {
51 mpz_init_set( result, (InternalRational::MPQDEN( ff )) );
52 ff->deleteObject();
53 }
54 else
55 {
56 ASSERT( 0, "illegal type" );
57 }
58}
int is_imm(const InternalCF *const ptr)
#define RationalDomain
Definition cf_defs.h:20
#define IntegerDomain
Definition cf_defs.h:21
virtual int levelcoeff() const
Definition int_cf.h:68
int deleteObject()
Definition int_cf.h:61
static mpz_ptr MPQDEN(const InternalCF *const c)
Definition int_rat.h:143

◆ gmp_numerator()

void FACTORY_PUBLIC gmp_numerator ( const CanonicalForm & f,
mpz_ptr result )

Definition at line 20 of file singext.cc.

21{
22 InternalCF * ff = f.getval();
23 ASSERT( ! is_imm( ff ), "illegal type" );
24 if ( ff->levelcoeff() == IntegerDomain )
25 {
26 mpz_init_set( result, (InternalInteger::MPI( ff )) );
27 ff->deleteObject();
28 }
29 else if ( ff->levelcoeff() == RationalDomain )
30 {
31 mpz_init_set( result, (InternalRational::MPQNUM( ff )) );
32 ff->deleteObject();
33 }
34 else
35 {
36 ASSERT( 0, "illegal type" );
37 }
38}
static mpz_ptr MPI(const InternalCF *const c)
MPI() - return underlying mpz_t of ‘c’.
Definition int_int.h:252
static mpz_ptr MPQNUM(const InternalCF *const c)
Definition int_rat.h:138

◆ hasFirstAlgVar()

bool hasFirstAlgVar ( const CanonicalForm & f,
Variable & a )

check if poly f contains an algebraic variable a

Definition at line 679 of file cf_ops.cc.

680{
681 if( f.inBaseDomain() ) // f has NO alg. variable
682 return false;
683 if( f.level()<0 ) // f has only alg. vars, so take the first one
684 {
685 a = f.mvar();
686 return true;
687 }
688 for(CFIterator i=f; i.hasTerms(); i++)
689 if( hasFirstAlgVar( i.coeff(), a ))
690 return true; // 'a' is already set
691 return false;
692}
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition cf_ops.cc:679

◆ hasMipo()

bool hasMipo ( const Variable & alpha)

Definition at line 226 of file variable.cc.

227{
228 ASSERT( alpha.level() < 0, "illegal extension" );
229 return (alpha.level() != LEVELBASE && (algextensions!=NULL) && getReduce(alpha) );
230}

◆ head()

CanonicalForm head ( const CanonicalForm & f)
inline

Definition at line 501 of file factory.h.

502{
503 if ( f.level() > 0 )
504 return power( f.mvar(), f.degree() ) * f.LC();
505 else
506 return f;
507}
CanonicalForm FACTORY_PUBLIC power(const CanonicalForm &f, int n)
exponentiation

◆ headdegree()

int headdegree ( const CanonicalForm & f)
inline

Definition at line 510 of file factory.h.

510{ return totaldegree( head( f ) ); }
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition cf_ops.cc:523
CanonicalForm head(const CanonicalForm &f)
Definition factory.h:501

◆ homogenize() [1/2]

CanonicalForm homogenize ( const CanonicalForm & f,
const Variable & x )

homogenize homogenizes f with Variable x

Definition at line 317 of file cf_factor.cc.

318{
319#if 0
320 int maxdeg=totaldegree(f), deg;
322 CanonicalForm elem, result(0);
323
324 for (i=f; i.hasTerms(); i++)
325 {
326 elem= i.coeff()*power(f.mvar(),i.exp());
327 deg = totaldegree(elem);
328 if ( deg < maxdeg )
329 result += elem * power(x,maxdeg-deg);
330 else
331 result+=elem;
332 }
333 return result;
334#else
335 CFList Newlist, Termlist= get_Terms(f);
336 int maxdeg=totaldegree(f), deg;
338 CanonicalForm elem, result(0);
339
340 for (i=Termlist; i.hasItem(); i++)
341 {
342 elem= i.getItem();
343 deg = totaldegree(elem);
344 if ( deg < maxdeg )
345 Newlist.append(elem * power(x,maxdeg-deg));
346 else
347 Newlist.append(elem);
348 }
349 for (i=Newlist; i.hasItem(); i++) // rebuild
350 result += i.getItem();
351
352 return result;
353#endif
354}
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition cf_ops.cc:523
CFList get_Terms(const CanonicalForm &f)
Definition cf_factor.cc:293

◆ homogenize() [2/2]

CanonicalForm homogenize ( const CanonicalForm & f,
const Variable & x,
const Variable & v1,
const Variable & v2 )

Definition at line 357 of file cf_factor.cc.

358{
359#if 0
360 int maxdeg=totaldegree(f), deg;
362 CanonicalForm elem, result(0);
363
364 for (i=f; i.hasTerms(); i++)
365 {
366 elem= i.coeff()*power(f.mvar(),i.exp());
367 deg = totaldegree(elem);
368 if ( deg < maxdeg )
369 result += elem * power(x,maxdeg-deg);
370 else
371 result+=elem;
372 }
373 return result;
374#else
375 CFList Newlist, Termlist= get_Terms(f);
376 int maxdeg=totaldegree(f), deg;
378 CanonicalForm elem, result(0);
379
380 for (i=Termlist; i.hasItem(); i++)
381 {
382 elem= i.getItem();
383 deg = totaldegree(elem,v1,v2);
384 if ( deg < maxdeg )
385 Newlist.append(elem * power(x,maxdeg-deg));
386 else
387 Newlist.append(elem);
388 }
389 for (i=Newlist; i.hasItem(); i++) // rebuild
390 result += i.getItem();
391
392 return result;
393#endif
394}

◆ icontent()

CanonicalForm icontent ( const CanonicalForm & f )

icontent() - return gcd over all coefficients of f which are in a coefficient domain.

Definition at line 74 of file cf_gcd.cc.

75{
76 return icontent( f, 0 );
77}
static CanonicalForm icontent(const CanonicalForm &f, const CanonicalForm &c)
static CanonicalForm icontent ( const CanonicalForm & f, const CanonicalForm & c )
Definition cf_gcd.cc:49

◆ igcd()

int igcd ( int a,
int b )

Definition at line 56 of file cf_util.cc.

57{
58 if ( a < 0 ) a = -a;
59 if ( b < 0 ) b = -b;
60
61 int c;
62
63 while ( b != 0 )
64 {
65 c = a % b;
66 a = b;
67 b = c;
68 }
69 return a;
70}

◆ ilog2()

int ilog2 ( const CanonicalForm & a)
inline

Definition at line 493 of file factory.h.

493{ return a.ilog2(); }

◆ ipower()

int FACTORY_PUBLIC ipower ( int b,
int m )

int ipower ( int b, int m )

ipower() - calculate b^m in standard integer arithmetic.

Note: Beware of overflows.

Definition at line 27 of file cf_util.cc.

28{
29 int prod = 1;
30
31 while ( m != 0 )
32 {
33 if ( m % 2 != 0 )
34 prod *= b;
35 m /= 2;
36 if ( m != 0 )
37 b *= b;
38 }
39 return prod;
40}

◆ irrCharSeries()

ListCFList FACTORY_PUBLIC irrCharSeries ( const CFList & PS)

irreducible characteristic series

Definition at line 568 of file cfCharSets.cc.

569{
570 CanonicalForm reducible, reducible2;
571 CFList qs, cs, factorset, is, ts, L;
572 CanonicalForm sqrf;
573 CFFList sqrfFactors;
574 CFFListIterator iter2;
575 for (CFListIterator iter= PS; iter.hasItem(); iter++)
576 {
577 sqrf= 1;
578 sqrfFactors= sqrFree (iter.getItem());
579 if (sqrfFactors.getFirst().factor().inCoeffDomain())
580 sqrfFactors.removeFirst();
581 for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
582 sqrf *= iter2.getItem().factor();
583 sqrf= normalize (sqrf);
584 L= Union (CFList (sqrf), L);
585 }
586
587 ListCFList pi, ppi, qqi, qsi, iss, qhi= ListCFList(L);
588
589 int nr_of_iteration= 0, indexRed, highestlevel= 0;
590
591 for (CFListIterator iter= PS; iter.hasItem(); iter++)
592 {
593 if (level (iter.getItem()) > highestlevel)
594 highestlevel= level(iter.getItem());
595 }
596
597 while (!qhi.isEmpty())
598 {
599 sortListCFList (qhi);
600
601 qs= qhi.getFirst();
602
603 ListCFList ppi1,ppi2;
604 select (ppi, qs.length(), ppi1, ppi2);
605
606 inplaceUnion (ppi2, qqi);
607
608 if (nr_of_iteration == 0)
609 {
610 nr_of_iteration += 1;
611 ppi= ListCFList();
612 }
613 else
614 {
615 nr_of_iteration += 1;
616 ppi= Union (ppi1, ListCFList (qs));
617 }
618
619 StoreFactors StoredFactors;
620 if (qs.length() - 3 < highestlevel)
621 cs= modCharSet (qs, StoredFactors, false);
622 else
623 cs= charSetN (qs);
624 cs= removeContent (cs, StoredFactors);
625
626 factorset= StoredFactors.FS1;
627
628 if (!cs.isEmpty() && cs.getFirst().level() > 0)
629 {
630 ts= irredAS (cs, indexRed, reducible);
631
632 if (indexRed <= 0) // irreducible
633 {
634 if (!isSubset (cs,qs))
635 cs= charSetViaCharSetN (Union (qs,cs));
636 if (!find (pi, cs))
637 {
638 pi= Union (ListCFList (cs), pi);
639 if (cs.getFirst().level() > 0)
640 {
641 ts= irredAS (cs, indexRed, reducible);
642
643 if (indexRed <= 0) //irreducible
644 {
645 qsi= Union (ListCFList(cs), qsi);
646 if (cs.length() == highestlevel)
647 is= factorPSet (factorset);
648 else
649 is= Union (factorsOfInitials (cs), factorPSet (factorset));
650 iss= adjoin (is, qs, qqi);
651 }
652 }
653 else
654 iss= adjoin (factorPSet (factorset), qs, qqi);
655 }
656 else
657 iss= adjoin (factorPSet (factorset), qs, qqi);
658 }
659
660 if (indexRed > 0)
661 {
662 is= factorPSet (factorset);
663 if (indexRed > 1)
664 {
665 CFList cst;
666 for (CFListIterator i= cs ; i.hasItem(); i++)
667 {
668 if (i.getItem() == reducible)
669 break;
670 else
671 cst.append (i.getItem());
672 }
673 is= Union (factorsOfInitials (Union (cst, CFList (reducible))), is);
674 iss= Union (adjoinb (ts, qs, qqi, cst), adjoin (is, qs, qqi));
675 }
676 else
677 iss= adjoin (Union (is, ts), qs, qqi);
678 }
679 }
680 else
681 iss= adjoin (factorPSet (factorset), qs, qqi);
682 if (qhi.length() > 1)
683 {
684 qhi.removeFirst();
685 qhi= Union (iss, qhi);
686 }
687 else
688 qhi= iss;
689 }
690 if (!qsi.isEmpty())
691 return contract (qsi);
692 return ListCFList(CFList (1)) ;
693}
void removeContent(CanonicalForm &F, CanonicalForm &cF)
bool isSubset(const CFList &PS, const CFList &Cset)
is PS a subset of Cset ?
ListCFList adjoinb(const CFList &is, const CFList &qs, const ListCFList &qh, const CFList &cs)
ListCFList contract(const ListCFList &cs)
static CFList irredAS(CFList &AS, int &indexRed, CanonicalForm &reducible)
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
#define pi
Definition libparse.cc:1145

◆ is_imm()

int is_imm ( const InternalCF *const ptr)
inline

Definition at line 215 of file factory.h.

216{
217 // returns 0 if ptr is not immediate
218 return ( ((int)((intptr_t)ptr)) & 3 );
219}

◆ isOn()

bool FACTORY_PUBLIC isOn ( int sw)

switches

Definition at line 1971 of file canonicalform.cc.

1972{
1973 return cf_glob_switches.isOn( sw );
1974}
INST_VAR CFSwitches cf_glob_switches

◆ isPurePoly()

bool isPurePoly ( const CanonicalForm & f)

Definition at line 248 of file cf_factor.cc.

249{
250 if (f.level()<=0) return false;
251 for (CFIterator i=f;i.hasTerms();i++)
252 {
253 if (!(i.coeff().inBaseDomain())) return false;
254 }
255 return true;
256}

◆ isPurePoly_m()

bool isPurePoly_m ( const CanonicalForm & f)

Definition at line 238 of file cf_factor.cc.

239{
240 if (f.inBaseDomain()) return true;
241 if (f.level()<0) return false;
242 for (CFIterator i=f;i.hasTerms();i++)
243 {
244 if (!isPurePoly_m(i.coeff())) return false;
245 }
246 return true;
247}
bool isPurePoly_m(const CanonicalForm &f)
Definition cf_factor.cc:238

◆ LC() [1/2]

CanonicalForm LC ( const CanonicalForm & f)
inline

Definition at line 451 of file factory.h.

451{ return f.LC(); }

◆ LC() [2/2]

CanonicalForm LC ( const CanonicalForm & f,
const Variable & v )
inline

Definition at line 454 of file factory.h.

454{ return f.LC( v ); }

◆ Lc()

CanonicalForm Lc ( const CanonicalForm & f)
inline

Definition at line 448 of file factory.h.

448{ return f.Lc(); }

◆ lc()

CanonicalForm lc ( const CanonicalForm & f)
inline

Definition at line 445 of file factory.h.

445{ return f.lc(); }

◆ lcm()

CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )

lcm() - return least common multiple of f and g.

The lcm is calculated using the formula lcm(f, g) = f * g / gcd(f, g).

Returns zero if one of f or g equals zero.

Definition at line 763 of file cf_gcd.cc.

764{
765 if ( f.isZero() || g.isZero() )
766 return 0;
767 else
768 return ( f / gcd( f, g ) ) * g;
769}

◆ leftShift()

CanonicalForm leftShift ( const CanonicalForm & F,
int n )

left shift the main variable of F by n

Returns
if x is the main variable of F the result is F(x^n)

Definition at line 697 of file cf_ops.cc.

698{
699 ASSERT (n >= 0, "cannot left shift by negative number");
700 if (F.inBaseDomain())
701 return F;
702 if (n == 0)
703 return F;
704 Variable x=F.mvar();
706 for (CFIterator i= F; i.hasTerms(); i++)
707 result += i.coeff()*power (x, i.exp()*n);
708 return result;
709}
bool inBaseDomain() const

◆ level() [1/2]

int level ( const CanonicalForm & f)
inline

Definition at line 472 of file factory.h.

472{ return f.level(); }

◆ level() [2/2]

int level ( const Variable & v)
inline

Definition at line 188 of file factory.h.

188{ return v.level(); }

◆ linearSystemSolve()

bool linearSystemSolve ( CFMatrix & M)

Definition at line 78 of file cf_linsys.cc.

79{
80 typedef int* int_ptr;
81
82 if ( ! matrix_in_Z( M ) ) {
83 int nrows = M.rows(), ncols = M.columns();
84 int i, j, k;
85 CanonicalForm rowpivot, pivotrecip;
86 // triangularization
87 for ( i = 1; i <= nrows; i++ ) {
88 //find "pivot"
89 for (j = i; j <= nrows; j++ )
90 if ( M(j,i) != 0 ) break;
91 if ( j > nrows ) return false;
92 if ( j != i )
93 M.swapRow( i, j );
94 pivotrecip = 1 / M(i,i);
95 for ( j = 1; j <= ncols; j++ )
96 M(i,j) *= pivotrecip;
97 for ( j = i+1; j <= nrows; j++ ) {
98 rowpivot = M(j,i);
99 if ( rowpivot == 0 ) continue;
100 for ( k = i; k <= ncols; k++ )
101 M(j,k) -= M(i,k) * rowpivot;
102 }
103 }
104 // matrix is now upper triangular with 1s down the diagonal
105 // back-substitute
106 for ( i = nrows-1; i > 0; i-- ) {
107 for ( j = nrows+1; j <= ncols; j++ ) {
108 for ( k = i+1; k <= nrows; k++ )
109 M(i,j) -= M(k,j) * M(i,k);
110 }
111 }
112 return true;
113 }
114 else {
115 int rows = M.rows(), cols = M.columns();
116 CFMatrix MM( rows, cols );
117 int ** mm = new int_ptr[rows];
118 CanonicalForm Q, Qhalf, mnew, qnew, B;
119 int i, j, p, pno;
120 bool ok;
121
122 // initialize room to hold the result and the result mod p
123 for ( i = 0; i < rows; i++ ) {
124 mm[i] = new int[cols];
125 }
126
127 // calculate the bound for the result
128 B = bound( M );
129 DEBOUTLN( cerr, "bound = " << B );
130
131 // find a first solution mod p
132 pno = 0;
133 do {
134 DEBOUTSL( cerr );
135 DEBOUT( cerr, "trying prime(" << pno << ") = " );
136 p = cf_getBigPrime( pno );
137 DEBOUT( cerr, p );
138 DEBOUTENDL( cerr );
140 // map matrix into char p
141 for ( i = 1; i <= rows; i++ )
142 for ( j = 1; j <= cols; j++ )
143 mm[i-1][j-1] = mapinto( M(i,j) ).intval();
144 // solve mod p
145 ok = solve( mm, rows, cols );
146 pno++;
147 } while ( ! ok );
148
149 // initialize the result matrix with first solution
151 for ( i = 1; i <= rows; i++ )
152 for ( j = rows+1; j <= cols; j++ )
153 MM(i,j) = mm[i-1][j-1];
154
155 // Q so far
156 Q = p;
157 while ( Q < B && pno < cf_getNumBigPrimes() ) {
158 do {
159 DEBOUTSL( cerr );
160 DEBOUT( cerr, "trying prime(" << pno << ") = " );
161 p = cf_getBigPrime( pno );
162 DEBOUT( cerr, p );
163 DEBOUTENDL( cerr );
165 for ( i = 1; i <= rows; i++ )
166 for ( j = 1; j <= cols; j++ )
167 mm[i-1][j-1] = mapinto( M(i,j) ).intval();
168 // solve mod p
169 ok = solve( mm, rows, cols );
170 pno++;
171 } while ( ! ok );
172 // found a solution mod p
173 // now chinese remainder it to a solution mod Q*p
175 for ( i = 1; i <= rows; i++ )
176 for ( j = rows+1; j <= cols; j++ )
177 {
178 chineseRemainder( MM[i][j], Q, CanonicalForm(mm[i-1][j-1]), CanonicalForm(p), mnew, qnew );
179 MM(i, j) = mnew;
180 }
181 Q = qnew;
182 }
183 if ( pno == cf_getNumBigPrimes() )
184 fuzzy_result = true;
185 else
186 fuzzy_result = false;
187 // store the result in M
188 Qhalf = Q / 2;
189 for ( i = 1; i <= rows; i++ ) {
190 for ( j = rows+1; j <= cols; j++ )
191 if ( MM(i,j) > Qhalf )
192 M(i,j) = MM(i,j) - Q;
193 else
194 M(i,j) = MM(i,j);
195 delete [] mm[i-1];
196 }
197 delete [] mm;
198 return ! fuzzy_result;
199 }
200}
CanonicalForm mapinto(const CanonicalForm &f)
int int ncols
Definition cf_linsys.cc:32
VAR bool fuzzy_result
Definition cf_linsys.cc:75
int nrows
Definition cf_linsys.cc:32
bool solve(int **extmat, int nrows, int ncols)
Definition cf_linsys.cc:504
long intval() const
conversion functions
#define DEBOUTENDL(stream)
Definition debug.h:48
#define DEBOUTSL(stream)
Definition debug.h:46

◆ make_cf() [1/2]

CanonicalForm FACTORY_PUBLIC make_cf ( const mpz_ptr n)

Definition at line 66 of file singext.cc.

67{
68 return CanonicalForm( CFFactory::basic( n ) );
69}
static InternalCF * basic(int value)
Definition cf_factory.cc:61

◆ make_cf() [2/2]

CanonicalForm FACTORY_PUBLIC make_cf ( const mpz_ptr n,
const mpz_ptr d,
bool normalize )

Definition at line 71 of file singext.cc.

72{
74}
static InternalCF * rational(long num, long den)

◆ make_cf_from_gf()

CanonicalForm make_cf_from_gf ( const int z)

Definition at line 76 of file singext.cc.

77{
78 return CanonicalForm(int2imm_gf(z));
79}

◆ mapdomain()

CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) )

mapdomain() - map all coefficients of f through mf.

Recursively descends down through f to the coefficients which are in a coefficient domain mapping each such coefficient through mf and returns the result.

Definition at line 440 of file cf_ops.cc.

441{
442 if ( f.inBaseDomain() )
443 return mf( f );
444 else
445 {
448 Variable x = f.mvar();
449 for ( i = f; i.hasTerms(); i++ )
450 result += power( x, i.exp() ) * mapdomain( i.coeff(), mf );
451 return result;
452 }
453}
CanonicalForm mapdomain(const CanonicalForm &f, CanonicalForm(*mf)(const CanonicalForm &))
CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) )
Definition cf_ops.cc:440

◆ mapinto()

CanonicalForm mapinto ( const CanonicalForm & f)
inline

Definition at line 496 of file factory.h.

496{ return f.mapinto(); }

◆ maxNorm()

CanonicalForm maxNorm ( const CanonicalForm & f )

maxNorm() - return maximum norm of ‘f’.

That is, the base coefficient of ‘f’ with the largest absolute value.

Valid for arbitrary polynomials over arbitrary domains, but most useful for multivariate polynomials over Z.

Type info:

f: CurrentPP

Definition at line 536 of file cf_algorithm.cc.

537{
538 if ( f.inBaseDomain() )
539 return abs( f );
540 else {
542 for ( CFIterator i = f; i.hasTerms(); i++ ) {
543 CanonicalForm coeffMaxNorm = maxNorm( i.coeff() );
544 if ( coeffMaxNorm > result )
545 result = coeffMaxNorm;
546 }
547 return result;
548 }
549}
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )

◆ mod()

◆ modCharSet() [1/2]

CFList modCharSet ( const CFList & PS,
bool removeContents )

Definition at line 404 of file cfCharSets.cc.

405{
406 StoreFactors tmp;
407 return modCharSet (PS, tmp, removeContents);
408}

◆ modCharSet() [2/2]

CFList modCharSet ( const CFList & PS,
StoreFactors & StoredFactors,
bool removeContents = true )

modified medial set

Definition at line 284 of file cfCharSets.cc.

285{
286 CFList QS, RS= L, CSet, tmp, contents, initial, removedFactors;
288 CanonicalForm r, cF;
289 bool noRemainder= true;
290 StoreFactors StoredFactors2;
291
292 QS= uniGcd (L);
293
294 while (!RS.isEmpty())
295 {
296 noRemainder= true;
297 CSet= basicSet (QS);
298
300
301 StoredFactors2.FS1= StoredFactors.FS1;
302 StoredFactors2.FS2= Union (StoredFactors2.FS2, initial);
303
304 RS= CFList();
305
306 if (CSet.length() > 0 && CSet.getFirst().level() > 0)
307 {
308 tmp= Difference (QS, CSet);
309
310 for (i= tmp; i.hasItem(); i++)
311 {
312 r= Prem (i.getItem(), CSet);
313 if (!r.isZero())
314 {
315 noRemainder= false;
316 if (removeContents)
317 {
318 removeContent (r, cF);
319
320 if (!cF.isZero())
321 contents= Union (contents, factorPSet (CFList(cF))); //factorPSet maybe too much it should suffice to do a squarefree factorization instead
322 }
323
324 removeFactors (r, StoredFactors2, removedFactors);
325 StoredFactors2.FS1= Union (StoredFactors2.FS1, removedFactors);
326 StoredFactors2.FS2= Difference (StoredFactors2.FS2, removedFactors);
327
328 removedFactors= CFList();
329
330 RS= Union (RS, CFList (r));
331 }
332 }
333
334 if (removeContents && !noRemainder)
335 {
336 StoredFactors.FS1= Union (StoredFactors2.FS1, contents);
337 StoredFactors.FS2= StoredFactors2.FS2;
338 }
339 else
340 StoredFactors= StoredFactors2;
341
342 QS= Union (CSet, RS);
343
344 contents= CFList();
345 removedFactors= CFList();
346 }
347 else
348 StoredFactors= StoredFactors2;
349 }
350
351 return CSet;
352}
void removeFactors(CanonicalForm &r, StoreFactors &StoredFactors, CFList &removedFactors)
poly initial(const poly p, const ring r, const gfan::ZVector &w)
Returns the initial form of p with respect to w.
Definition initial.cc:30

◆ mvar()

Variable mvar ( const CanonicalForm & f)
inline

Definition at line 475 of file factory.h.

475{ return f.mvar(); }

◆ name()

char name ( const Variable & v)
inline

Definition at line 189 of file factory.h.

189{ return v.name(); }

◆ neworder()

Varlist neworder ( const CFList & PolyList)

◆ newordercf()

CFList newordercf ( const CFList & PolyList)

Definition at line 75 of file cfCharSets.cc.

76{
77 Varlist reorder= neworder (PolyList);
78 CFList output;
79
80 for (VarlistIterator i=reorder; i.hasItem(); i++)
81 output.append (CanonicalForm (i.getItem()));
82
83 return output;
84}
ListIterator< Variable > VarlistIterator
CFList reorder(const Varlist &betterorder, const CFList &PS)
Varlist neworder(const CFList &PolyList)

◆ neworderint()

IntList FACTORY_PUBLIC neworderint ( const CFList & PolyList)

Definition at line 88 of file cfCharSets.cc.

89{
90 Varlist reorder= neworder (PolyList);
91 IntList output;
92
93 for (VarlistIterator i= reorder; i.hasItem(); i++)
94 output.append (level (i.getItem()));
95
96 return output;
97}

◆ num()

CanonicalForm num ( const CanonicalForm & f)
inline

Definition at line 478 of file factory.h.

478{ return f.num(); }

◆ Off()

void FACTORY_PUBLIC Off ( int sw)

switches

Definition at line 1964 of file canonicalform.cc.

1965{
1966 cf_glob_switches.Off( sw );
1967}

◆ On()

void FACTORY_PUBLIC On ( int sw)

switches

Definition at line 1957 of file canonicalform.cc.

1958{
1959 cf_glob_switches.On( sw );
1960}

◆ operator%()

◆ operator*()

See also
CanonicalForm::operator *=()

Definition at line 524 of file cf_inline.cc.

525{
526 CanonicalForm result( lhs );
527 result *= rhs;
528 return result;
529}

◆ operator+()

CF_INLINE CanonicalForm operator +, -, *, /, % ( const CanonicalForm & lhs, const CanonicalForm & rhs )

operators +, -, *, /, %(), div(), mod() - binary arithmetic operators.

The binary operators have their standard (mathematical) semantics. As explained for the corresponding arithmetic assignment operators, the operators ‘/’ and ‘%’ return the quotient resp. remainder of (polynomial) division with remainder, whereas ‘div()’ and ‘mod()’ may be used for exact division and term-wise remaindering, resp.

It is faster to use the arithmetic assignment operators (e.g., ‘f += g;’) instead of the binary operators (‘f = f+g;’ ).

Type info:

lhs, rhs: CurrentPP

There are weaker preconditions for some cases (e.g., arithmetic operations with elements from Q or Z work in any domain), but type ‘CurrentPP’ is the only one guaranteed to work for all cases.

Developers note:

All binary operators have their corresponding ‘CanonicalForm’ assignment operators (e.g., ‘operator +()’ corresponds to ‘CanonicalForm::operator +=()’, ‘div()’ corresponds to `CanonicalFormdiv()).

And that is how they are implemented, too: Each of the binary operators first creates a copy of ‘lhs’, adds ‘rhs’ to this copy using the assignment operator, and returns the result.

See also
CanonicalForm::operator +=()

Definition at line 503 of file cf_inline.cc.

504{
505 CanonicalForm result( lhs );
506 result += rhs;
507 return result;
508}

◆ operator-()

◆ operator/()

◆ power() [1/2]

exponentiation

Definition at line 1896 of file canonicalform.cc.

1897{
1898 ASSERT( n >= 0, "illegal exponent" );
1899 if ( f.isZero() )
1900 return CanonicalForm(0L);
1901 else if ( f.isOne() )
1902 return f;
1903 else if ( f == -1 )
1904 {
1905 if ( n % 2 == 0 )
1906 return CanonicalForm(1L);
1907 else
1908 return CanonicalForm(-1L);
1909 }
1910 else if ( n == 0 )
1911 return CanonicalForm(1L);
1912
1913 //else if (f.inGF())
1914 //{
1915 //}
1916 else
1917 {
1919 h=f;
1920 while(n%2==0)
1921 {
1922 h*=h;
1923 n/=2;
1924 }
1925 g=h;
1926 while(1)
1927 {
1928 n/=2;
1929 if(n==0)
1930 return g;
1931 h*=h;
1932 if(n%2!=0) g*=h;
1933 }
1934 }
1935}
STATIC_VAR Poly * h
Definition janet.cc:971

◆ power() [2/2]

CanonicalForm FACTORY_PUBLIC power ( const Variable & v,
int n )

exponentiation

Definition at line 1939 of file canonicalform.cc.

1940{
1941 //ASSERT( n >= 0, "illegal exponent" );
1942 if ( n == 0 )
1943 return 1;
1944 else if ( n == 1 )
1945 return v;
1946 else if (( v.level() < 0 ) && (hasMipo(v)))
1947 {
1948 CanonicalForm result( v, n-1 );
1949 return result * v;
1950 }
1951 else
1952 return CanonicalForm( v, n );
1953}
bool hasMipo(const Variable &alpha)
Definition variable.cc:226

◆ pp()

CanonicalForm pp ( const CanonicalForm & f )

pp() - return primitive part of f.

Returns zero if f equals zero, otherwise f / content(f).

Definition at line 676 of file cf_gcd.cc.

677{
678 if ( f.isZero() )
679 return f;
680 else
681 return f / content( f );
682}

◆ Prem()

pseudo remainder of F by G with certain factors of LC (g) cancelled

Definition at line 616 of file cfCharSetsUtil.cc.

617{
618 CanonicalForm f, g, l, test, lu, lv, t, retvalue;
619 int degF, degG, levelF, levelG;
620 bool reord;
621 Variable v, vg= G.mvar();
622
623 if ( (levelF= F.level()) < (levelG= G.level()))
624 return F;
625 else
626 {
627 if ( levelF == levelG )
628 {
629 f= F;
630 g= G;
631 reord= false;
632 v= F.mvar();
633 }
634 else
635 {
636 v= Variable (levelF + 1);
637 f= swapvar (F, vg, v);
638 g= swapvar (G, vg, v);
639 reord= true;
640 }
641 degG= degree (g, v );
642 degF= degree (f, v );
643 if (degG <= degF)
644 {
645 l= LC (g);
646 g= g - l*power (v, degG);
647 }
648 else
649 l= 1;
650 while ((degG <= degF) && (!f.isZero()))
651 {
652 test= gcd (l, LC(f));
653 lu= l / test;
654 lv= LC(f) / test;
655 t= g*lv*power (v, degF - degG);
656
657 if (degF == 0)
658 f= 0;
659 else
660 f= f - LC (f)*power (v, degF);
661
662 f= f*lu - t;
663 degF= degree (f, v);
664 }
665
666 if (reord)
667 retvalue= swapvar (f, vg, v);
668 else
669 retvalue= f;
670
671 return retvalue;
672 }
673}
CanonicalForm LC(const CanonicalForm &f)
CFList swapvar(const CFList &PS, const Variable &x, const Variable &y)
swapvar a whole list of CanonicalForms
CanonicalForm test
Definition cfModGcd.cc:4104
static CanonicalForm * retvalue
Definition readcf.cc:126
int gcd(int a, int b)

◆ probIrredTest()

int FACTORY_PUBLIC probIrredTest ( const CanonicalForm & F,
double error )

given some error probIrredTest detects irreducibility or reducibility of F with confidence level 1-error

Returns
probIrredTest returns 1 for irreducibility, -1 for reducibility or 0 if the test is not applicable
Parameters
[in]Fsome poly over Z/p
[in]error0 < error < 1

Definition at line 63 of file facIrredTest.cc.

64{
65 CFMap N;
67 int n= G.level();
68 int p= getCharacteristic();
69
70 double sqrtTrials= inverseERF (1-2.0*error)*sqrt (2.0);
71
72 double s= sqrtTrials;
73
74 double pn= pow ((double) p, (double) n);
75 double p1= (double) 1/p;
76 p1= p1*(1.0-p1);
77 p1= p1/(double) pn;
78 p1= sqrt (p1);
79 p1 *= s;
80 p1 += (double) 1/p;
81
82 double p2= (double) (2*p-1)/(p*p);
83 p2= p2*(1-p2);
84 p2= p2/(double) pn;
85 p2= sqrt (p2);
86 p2 *= s;
87 p2= (double) (2*p - 1)/(p*p)-p2;
88
89 //no testing possible
90 if (p2 < p1)
91 return 0;
92
93 double den= sqrt (p1*(1-p1))+sqrt (p2*(1-p2));
94 double num= p2-p1;
95
96 sqrtTrials *= den/num;
97
98 int trials= (int) floor (pow (sqrtTrials, 2.0));
99
100 double experimentalNumZeros= numZeros (G, trials);
101
102 double pmiddle= sqrt (p1*p2);
103
104 num= den;
105 den= sqrt (p1*(1.0-p2))+sqrt (p2*(1.0-p1));
106 pmiddle *= (den/num);
107
108 if (experimentalNumZeros < pmiddle)
109 return 1;
110 else
111 return -1;
112}
Rational pow(const Rational &a, int e)
Definition GMPrat.cc:411
double numZeros(const CanonicalForm &F, int k)
evaluate F at k random points in Z/p^n and count the number of zeros that occur
double inverseERF(double d)
#define error(a)

◆ prune()

void FACTORY_PUBLIC prune ( Variable & alpha)

Definition at line 261 of file variable.cc.

262{
263 if (alpha.level()==LEVELBASE) return;
264 int last_var=-alpha.level();
265 if ((last_var <= 0)||(var_names_ext==NULL)) return;
266 int i, n = strlen( var_names_ext );
267 ASSERT (n+1 >= last_var, "wrong variable");
268 if (last_var == 1)
269 {
270 delete [] var_names_ext;
271 delete [] algextensions;
272 var_names_ext= 0;
273 algextensions= 0;
274 alpha= Variable();
275 return;
276 }
277 char * newvarnames = new char [last_var+1];
278 for ( i = 0; i < last_var; i++ )
279 newvarnames[i] = var_names_ext[i];
280 newvarnames[last_var] = 0;
281 delete [] var_names_ext;
282 var_names_ext = newvarnames;
283 ext_entry * newalgext = new ext_entry [last_var];
284 for ( i = 0; i < last_var; i++ )
285 newalgext[i] = algextensions[i];
286 delete [] algextensions;
287 algextensions = newalgext;
288 alpha= Variable();
289}
Definition variable.cc:19

◆ prune1()

void prune1 ( const Variable & alpha)

Definition at line 291 of file variable.cc.

292{
293 int i, n = strlen( var_names_ext );
294 ASSERT (n+1 >= -alpha.level(), "wrong variable");
295
296 char * newvarnames = new char [-alpha.level() + 2];
297 for ( i = 0; i <= -alpha.level(); i++ )
298 newvarnames[i] = var_names_ext[i];
299 newvarnames[-alpha.level()+1] = 0;
300 delete [] var_names_ext;
301 var_names_ext = newvarnames;
302 ext_entry * newalgext = new ext_entry [-alpha.level()+1];
303 for ( i = 0; i <= -alpha.level(); i++ )
304 newalgext[i] = algextensions[i];
305 delete [] algextensions;
306 algextensions = newalgext;
307}

◆ psq()

CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )

psq() - return pseudo quotient of ‘f’ and ‘g’ with respect to ‘x’.

‘g’ must not equal zero.

Type info:

f, g: Current x: Polynomial

Developers note:

This is not an optimal implementation. Better would have been an implementation in ‘InternalPoly’ avoiding the exponentiation of the leading coefficient of ‘g’. It seemed not worth to do so.

See also
psr(), psqr()

Definition at line 172 of file cf_algorithm.cc.

173{
174 ASSERT( x.level() > 0, "type error: polynomial variable expected" );
175 ASSERT( ! g.isZero(), "math error: division by zero" );
176
177 // swap variables such that x's level is larger or equal
178 // than both f's and g's levels.
179 Variable X = tmax( tmax( f.mvar(), g.mvar() ), x );
180 CanonicalForm F = swapvar( f, x, X );
181 CanonicalForm G = swapvar( g, x, X );
182
183 // now, we have to calculate the pseudo remainder of F and G
184 // w.r.t. X
185 int fDegree = degree( F, X );
186 int gDegree = degree( G, X );
187 if ( fDegree < 0 || fDegree < gDegree )
188 return 0;
189 else {
190 CanonicalForm result = (power( LC( G, X ), fDegree-gDegree+1 ) * F) / G;
191 return swapvar( result, x, X );
192 }
193}

◆ psqr()

void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable & x )

psqr() - calculate pseudo quotient and remainder of ‘f’ and ‘g’ with respect to ‘x’.

Returns the pseudo quotient of ‘f’ and ‘g’ in ‘q’, the pseudo remainder in ‘r’. ‘g’ must not equal zero.

See ‘psr()’ for more detailed information.

Type info:

f, g: Current q, r: Anything x: Polynomial

Developers note:

This is not an optimal implementation. Better would have been an implementation in ‘InternalPoly’ avoiding the exponentiation of the leading coefficient of ‘g’. It seemed not worth to do so.

See also
psr(), psq()

Definition at line 223 of file cf_algorithm.cc.

224{
225 ASSERT( x.level() > 0, "type error: polynomial variable expected" );
226 ASSERT( ! g.isZero(), "math error: division by zero" );
227
228 // swap variables such that x's level is larger or equal
229 // than both f's and g's levels.
230 Variable X = tmax( tmax( f.mvar(), g.mvar() ), x );
231 CanonicalForm F = swapvar( f, x, X );
232 CanonicalForm G = swapvar( g, x, X );
233
234 // now, we have to calculate the pseudo remainder of F and G
235 // w.r.t. X
236 int fDegree = degree( F, X );
237 int gDegree = degree( G, X );
238 if ( fDegree < 0 || fDegree < gDegree ) {
239 q = 0; r = f;
240 } else {
241 divrem( power( LC( G, X ), fDegree-gDegree+1 ) * F, G, q, r );
242 q = swapvar( q, x, X );
243 r = swapvar( r, x, X );
244 }
245}

◆ psr()

CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )

psr() - return pseudo remainder of ‘f’ and ‘g’ with respect to ‘x’.

‘g’ must not equal zero.

For f and g in R[x], R an arbitrary ring, g != 0, there is a representation

LC(g)^s*f = g*q + r

with r = 0 or deg(r) < deg(g) and s = 0 if f = 0 or s = max( 0, deg(f)-deg(g)+1 ) otherwise. r = psr(f, g) and q = psq(f, g) are called "pseudo remainder" and "pseudo quotient", resp. They are uniquely determined if LC(g) is not a zero divisor in R.

See H.-J. Reiffen/G. Scheja/U. Vetter - "Algebra", 2nd ed., par. 15, for a reference.

Type info:

f, g: Current x: Polynomial

Polynomials over prime power domains are admissible if lc(LC(‘g’,‘x’)) is not a zero divisor. This is a slightly stronger precondition than mathematically necessary since pseudo remainder and quotient are well-defined if LC(‘g’,‘x’) is not a zero divisor.

For example, psr(y^2, (13*x+1)*y) is well-defined in (Z/13^2[x])[y] since (13*x+1) is not a zero divisor. But calculating it with Factory would fail since 13 is a zero divisor in Z/13^2.

Due to this inconsistency with mathematical notion, we decided not to declare type ‘CurrentPP’ for ‘f’ and ‘g’.

Developers note:

This is not an optimal implementation. Better would have been an implementation in ‘InternalPoly’ avoiding the exponentiation of the leading coefficient of ‘g’. In contrast to ‘psq()’ and ‘psqr()’ it definitely seems worth to implement the pseudo remainder on the internal level.

See also
psq(), psqr()

Definition at line 117 of file cf_algorithm.cc.

118{
119 CanonicalForm r=rr, v=vv, l, test, lu, lv, t, retvalue;
120 int dr, dv, d,n=0;
121
122
123 dr = degree( r, x );
124 if (dr>0)
125 {
126 dv = degree( v, x );
127 if (dv <= dr) {l=LC(v,x); v = v -l*power(x,dv);}
128 else { l = 1; }
129 d= dr-dv+1;
130 //out_cf("psr(",rr," ");
131 //out_cf("",vv," ");
132 //printf(" var=%d\n",x.level());
133 while ( ( dv <= dr ) && ( !r.isZero()) )
134 {
135 test = power(x,dr-dv)*v*LC(r,x);
136 if ( dr == 0 ) { r= CanonicalForm(0); }
137 else { r= r - LC(r,x)*power(x,dr); }
138 r= l*r -test;
139 dr= degree(r,x);
140 n+=1;
141 }
142 r= power(l, d-n)*r;
143 }
144 return r;
145}

◆ reduce()

polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of f are reduced modulo M

Definition at line 660 of file cf_ops.cc.

661{
662 if(f.inBaseDomain() || f.level() < M.level())
663 return f;
664 if(f.level() == M.level())
665 {
666 if(f.degree() < M.degree())
667 return f;
668 CanonicalForm tmp = mod (f, M);
669 return tmp;
670 }
671 // here: f.level() > M.level()
673 for(CFIterator i=f; i.hasTerms(); i++)
674 result += reduce(i.coeff(),M) * power(f.mvar(),i.exp());
675 return result;
676}
CanonicalForm reduce(const CanonicalForm &f, const CanonicalForm &M)
polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of...
Definition cf_ops.cc:660

◆ reorder() [1/3]

CFFList reorder ( const Varlist & betterorder,
const CFFList & PS )

Definition at line 120 of file cfCharSets.cc.

121{
122 int i= 1, n= betterorder.length();
123 Intarray v (1, n);
124 CFFList ps= PS;
125
126 //initalize:
127 for (VarlistIterator j= betterorder; j.hasItem(); j++)
128 {
129 v[i]= level (j.getItem());
130 i++;
131 }
132
133 // reorder:
134 for (i= 1; i <= n; i++)
135 ps= swapvar (ps, Variable (v[i]), Variable (n + i));
136 return ps;
137}
Array< int > Intarray

◆ reorder() [2/3]

CFList reorder ( const Varlist & betterorder,
const CFList & PS )

Definition at line 101 of file cfCharSets.cc.

102{
103 int i= 1, n= betterorder.length();
104 Intarray v (1, n);
105 CFList ps= PS;
106
107 //initalize:
108 for (VarlistIterator j= betterorder; j.hasItem(); j++)
109 {
110 v[i]= level (j.getItem());
111 i++;
112 }
113 // reorder:
114 for (i= 1; i <= n; i++)
115 ps= swapvar (ps, Variable (v[i]), Variable (n + i));
116 return ps;
117}

◆ reorder() [3/3]

ListCFList reorder ( const Varlist & betterorder,
const ListCFList & Q )

Definition at line 140 of file cfCharSets.cc.

141{
142 ListCFList Q1;
143
144 for (ListCFListIterator i= Q; i.hasItem(); i++)
145 Q1.append (reorder (betterorder, i.getItem()));
146 return Q1;
147}
ListIterator< CFList > ListCFListIterator

◆ replaceLc()

Definition at line 90 of file fac_util.cc.

91{
92 if ( f.inCoeffDomain() )
93 return c;
94 else
95 return f + ( c - LC( f ) ) * power( f.mvar(), degree( f ) );
96}

◆ replacevar()

CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )

replacevar() - replace all occurences of x1 in f by x2.

In contrast to swapvar(), x1 may be an algebraic variable, but x2 must be a polynomial variable.

Definition at line 271 of file cf_ops.cc.

272{
273 //ASSERT( x2.level() > 0, "cannot replace with algebraic variable" );
274 if ( f.inBaseDomain() || x1 == x2 || ( x1 > f.mvar() ) )
275 return f;
276 else
277 {
278 sv_x1 = x1;
279 sv_x2 = x2;
280 return replacevar_between( f );
281 }
282}
STATIC_INST_VAR Variable sv_x2
Definition cf_ops.cc:43
static CanonicalForm replacevar_between(const CanonicalForm &f)
replacevar_between() - replace occurences of sv_x1 in f with sv_x2.
Definition cf_ops.cc:233
STATIC_INST_VAR Variable sv_x1
static Variable sv_x1, sv_x2;
Definition cf_ops.cc:43

◆ resultant()

CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )

resultant() - return resultant of f and g with respect to x.

The chain is calculated from f and g with respect to variable x which should not be an algebraic variable. If f or q equals zero, zero is returned. If f is a coefficient with respect to x, f^degree(g, x) is returned, analogously for g.

This algorithm serves as a wrapper around other resultant algorithms which do the real work. Here we use standard properties of resultants only.

Definition at line 173 of file cf_resultant.cc.

174{
175 ASSERT( x.level() > 0, "cannot calculate resultant with respect to algebraic variables" );
176
177 // some checks on triviality. We will not use degree( v )
178 // here because this may involve variable swapping.
179 if ( f.isZero() || g.isZero() )
180 return 0;
181 if ( f.mvar() < x )
182 return power( f, g.degree( x ) );
183 if ( g.mvar() < x )
184 return power( g, f.degree( x ) );
185
186 // make x main variale
187 CanonicalForm F, G;
188 Variable X;
189 if ( f.mvar() > x || g.mvar() > x ) {
190 if ( f.mvar() > g.mvar() )
191 X = f.mvar();
192 else
193 X = g.mvar();
194 F = swapvar( f, X, x );
195 G = swapvar( g, X, x );
196 }
197 else {
198 X = x;
199 F = f;
200 G = g;
201 }
202 // at this point, we have to calculate resultant( F, G, X )
203 // where X is equal to or greater than the main variables
204 // of F and G
205
206 int m = degree( F, X );
207 int n = degree( G, X );
208 // catch trivial cases
209 if ( m+n <= 2 || m == 0 || n == 0 )
210 return swapvar( trivialResultant( F, G, X ), X, x );
211
212 // exchange F and G if necessary
213 int flipFactor;
214 if ( m < n ) {
216 F = G; G = swap;
217 int degswap = m;
218 m = n; n = degswap;
219 if ( m & 1 && n & 1 )
220 flipFactor = -1;
221 else
222 flipFactor = 1;
223 } else
224 flipFactor = 1;
225
226 // this is not an effective way to calculate the resultant!
227 CanonicalForm extFactor;
228 if ( m == n ) {
229 if ( n & 1 )
230 extFactor = -LC( G, X );
231 else
232 extFactor = LC( G, X );
233 } else
234 extFactor = power( LC( F, X ), m-n-1 );
235
237 result = subResChain( F, G, X )[0] / extFactor;
238
239 return swapvar( result, X, x ) * flipFactor;
240}
#define swap(_i, _j)
CFArray subResChain(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
static CanonicalForm trivialResultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
static CanonicalForm trivialResultant ( const CanonicalForm & f, const CanonicalForm & g,...

◆ resultantZ()

CanonicalForm resultantZ ( const CanonicalForm & A,
const CanonicalForm & B,
const Variable & x,
bool prob = true )

modular resultant algorihtm over Z

Returns
resultantZ returns the resultant of A and B wrt. x
Parameters
[in]Asome poly
[in]Bsome poly
[in]xsome polynomial variable
[in]probif true use probabilistic algorithm

Definition at line 560 of file cfModResultant.cc.

562{
563 ASSERT (getCharacteristic() == 0, "characteristic > 0 expected");
564#ifndef NOASSERT
565 bool isRat= isOn (SW_RATIONAL);
566 On (SW_RATIONAL);
567 ASSERT (bCommonDen (A).isOne(), "input A is rational");
568 ASSERT (bCommonDen (B).isOne(), "input B is rational");
569 if (!isRat)
571#endif
572
573 int degAx= degree (A, x);
574 int degBx= degree (B, x);
575 if (A.level() < x.level())
576 return power (A, degBx);
577 if (B.level() < x.level())
578 return power (B, degAx);
579
580 if (degAx == 0)
581 return power (A, degBx);
582 else if (degBx == 0)
583 return power (B, degAx);
584
585 CanonicalForm F= A;
587
588 Variable X= x;
589 if (F.level() != x.level() || G.level() != x.level())
590 {
591 if (F.level() > G.level())
592 X= F.mvar();
593 else
594 X= G.mvar();
595 F= swapvar (F, X, x);
596 G= swapvar (G, X, x);
597 }
598
599 // now X is the main variable
600
601 CanonicalForm d= 0;
602 CanonicalForm dd= 0;
604 for (CFIterator i= F; i.hasTerms(); i++)
605 {
606 buf= oneNorm (i.coeff());
607 d= (buf > d) ? buf : d;
608 }
609 CanonicalForm e= 0, ee= 0;
610 for (CFIterator i= G; i.hasTerms(); i++)
611 {
612 buf= oneNorm (i.coeff());
613 e= (buf > e) ? buf : e;
614 }
615 d= power (d, degBx);
616 e= power (e, degAx);
618 for (int i= degBx + degAx; i > 1; i--)
619 bound *= i;
620 bound *= d*e;
621 bound *= 2;
622
623 bool onRational= isOn (SW_RATIONAL);
624 if (onRational)
626 int i = cf_getNumBigPrimes() - 1;
627 int p;
628 CanonicalForm l= lc (F)*lc(G);
629 CanonicalForm resultModP, q (0), newResult, newQ;
631 int equalCount= 0;
632 CanonicalForm test, newTest;
633 int count= 0;
634 do
635 {
636 p = cf_getBigPrime( i );
637 i--;
638 while ( i >= 0 && mod( l, p ) == 0)
639 {
640 p = cf_getBigPrime( i );
641 i--;
642 }
643
644 if (i <= 0)
645 return resultant (A, B, x);
646
648
649 TIMING_START (fac_resultant_p);
650 resultModP= resultantFp (mapinto (F), mapinto (G), X, prob);
651 TIMING_END_AND_PRINT (fac_resultant_p, "time to compute resultant mod p: ");
652
654
655 count++;
656 if ( q.isZero() )
657 {
658 result= mapinto(resultModP);
659 q= p;
660 }
661 else
662 {
663 chineseRemainder( result, q, mapinto (resultModP), p, newResult, newQ );
664 q= newQ;
665 result= newResult;
667 if (test != newTest)
668 {
669 newTest= test;
670 equalCount= 0;
671 }
672 else
673 equalCount++;
674 if (newQ > bound || (prob && equalCount == 2))
675 {
676 result= test;
677 break;
678 }
679 }
680 } while (1);
681
682 if (onRational)
683 On (SW_RATIONAL);
684 return swapvar (result, X, x);
685}
CanonicalForm lc(const CanonicalForm &f)
static CanonicalForm oneNorm(const CanonicalForm &F)
static CanonicalForm symmetricRemainder(const CanonicalForm &f, const CanonicalForm &q)
CanonicalForm resultantFp(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Fp
CanonicalForm FACTORY_PUBLIC resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
int status int void * buf
Definition si_signals.h:69
#define TIMING_END_AND_PRINT(t, msg)
Definition timing.h:94

◆ rootOf()

Variable FACTORY_PUBLIC rootOf ( const CanonicalForm & mipo,
char name = '@' )

returns a symbolic root of polynomial with name name Use it to define algebraic variables

returns a symbolic root of polynomial with name name.

Note
: algebraic variables have a level < 0

Use it to define algebraic variables

Note
: algebraic variables have a level < 0
: algebraic variables have a level < 0

Definition at line 162 of file variable.cc.

163{
164 ASSERT (mipo.isUnivariate(), "not a legal extension");
165
166 int l;
167 if ( var_names_ext == 0 ) {
168 var_names_ext = new char [3];
169 var_names_ext[0] = '@';
170 var_names_ext[1] = name;
171 var_names_ext[2] = '\0';
172 l = 1;
173 Variable result( -l, true );
174 algextensions = new ext_entry [2];
175 algextensions[1] = ext_entry( 0, false );
176 algextensions[1] = ext_entry( (InternalPoly*)(conv2mipo( mipo, result ).getval()), true );
177 return result;
178 }
179 else {
180 int i, n = strlen( var_names_ext );
181 char * newvarnames = new char [n+2];
182 for ( i = 0; i < n; i++ )
183 newvarnames[i] = var_names_ext[i];
184 newvarnames[n] = name;
185 newvarnames[n+1] = 0;
186 delete [] var_names_ext;
187 var_names_ext = newvarnames;
188 l = n;
189 Variable result( -l, true );
190 ext_entry * newalgext = new ext_entry [n+1];
191 for ( i = 0; i < n; i++ )
192 newalgext[i] = algextensions[i];
193 newalgext[n] = ext_entry( 0, false );
194 delete [] algextensions;
195 algextensions = newalgext;
196 algextensions[n] = ext_entry( (InternalPoly*)(conv2mipo( mipo, result ).getval()), true );
197 return result;
198 }
199}
factory's class for polynomials
Definition int_poly.h:71
CanonicalForm mipo
Definition facAlgExt.cc:57
int name
New type name for int.
static CanonicalForm conv2mipo(const CanonicalForm &mipo, const Variable &alpha)
Definition variable.cc:154

◆ setCharacteristic() [1/3]

void FACTORY_PUBLIC setCharacteristic ( int c)

Definition at line 28 of file cf_char.cc.

29{
30 if ( c == 0 )
31 {
32 theDegree = 0;
35 }
36 else
37 {
38 theDegree = 1;
41 if (c!=theCharacteristic)
42 {
43 if (c > 536870909) factoryError("characteristic is too large(max is 2^29)");
44 ff_setprime( c );
45 }
47 }
48}
#define FiniteFieldDomain
Definition cf_defs.h:19
int cf_getNumSmallPrimes()
Definition cf_primes.cc:34
int cf_getSmallPrime(int i)
Definition cf_primes.cc:28
static void settype(int type)
Definition cf_factory.h:29
VAR bool ff_big
Definition ffops.cc:25
void ff_setprime(const int p)
Definition ffops.cc:28

◆ setCharacteristic() [2/3]

void setCharacteristic ( int c,
int n )

◆ setCharacteristic() [3/3]

void setCharacteristic ( int c,
int n,
char name )

Definition at line 61 of file cf_char.cc.

62{
63 ASSERT( c != 0 && n > 1, "illegal GF(q)" );
66 theDegree = n;
68}
void setCharacteristic(int c)
Definition cf_char.cc:28
void gf_setcharacteristic(int p, int n, char name)
Definition gfops.cc:202

◆ setMipo()

void setMipo ( const Variable & alpha,
const CanonicalForm & mipo )

Definition at line 219 of file variable.cc.

220{
221 ASSERT( alpha.level() < 0 && alpha.level() != LEVELBASE, "illegal extension" );
222 algextensions[-alpha.level()]= ext_entry( 0, false );
223 algextensions[-alpha.level()]= ext_entry((InternalPoly*)(conv2mipo( mipo, alpha ).getval()), true );
224}

◆ setReduce()

void setReduce ( const Variable & alpha,
bool reduce )

Definition at line 238 of file variable.cc.

239{
240 ASSERT( alpha.level() < 0 && alpha.level() != LEVELBASE, "illegal extension" );
241 algextensions[-alpha.level()].reduce() = reduce;
242}
CanonicalForm reduce(const CanonicalForm &f, const CanonicalForm &M)
polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of...
Definition cf_ops.cc:660

◆ sign()

int sign ( const CanonicalForm & a)
inline

Definition at line 484 of file factory.h.

484{ return a.sign(); }

◆ size() [1/2]

int size ( const CanonicalForm & f)

int size ( const CanonicalForm & f )

size() - return number of monomials in f which are in an coefficient domain.

Returns one if f is in an coefficient domain.

Definition at line 627 of file cf_ops.cc.

628{
629 if ( f.inCoeffDomain() )
630 return 1;
631 else
632 {
633 int result = 0;
635 for ( i = f; i.hasTerms(); i++ )
636 result += size( i.coeff() );
637 return result;
638 }
639}
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600

◆ size() [2/2]

int size ( const CanonicalForm & f,
const Variable & v )

int size ( const CanonicalForm & f, const Variable & v )

size() - count number of monomials of f with level higher or equal than level of v.

Returns one if f is in an base domain.

Definition at line 600 of file cf_ops.cc.

601{
602 if ( f.inBaseDomain() )
603 return 1;
604
605 if ( f.mvar() < v )
606 // polynomials with level < v1 are counted as coefficients
607 return 1;
608 else
609 {
611 int result = 0;
612 // polynomials with level > v2 are not counted al all
613 for ( i = f; i.hasTerms(); i++ )
614 result += size( i.coeff(), v );
615 return result;
616 }
617}

◆ size_maxexp()

int size_maxexp ( const CanonicalForm & f,
int & maxexp )

Definition at line 641 of file cf_ops.cc.

642{
643 if ( f.inCoeffDomain() )
644 return 1;
645 else
646 {
647 if (f.degree()>maxexp) maxexp=f.degree();
648 int result = 0;
650 for ( i = f; i.hasTerms(); i++ )
651 result += size_maxexp( i.coeff(), maxexp );
652 return result;
653 }
654}
int size_maxexp(const CanonicalForm &f, int &maxexp)
Definition cf_ops.cc:641

◆ sqrFree()

CFFList FACTORY_PUBLIC sqrFree ( const CanonicalForm & f,
bool sort = false )

squarefree factorization

Definition at line 961 of file cf_factor.cc.

962{
963// ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
965
966 if ( getCharacteristic() == 0 )
967 result = sqrFreeZ( f );
968 else
969 {
971 if (hasFirstAlgVar (f, alpha))
972 result = FqSqrf( f, alpha );
973 else
974 result= FpSqrf (f);
975 }
976 if (sort)
977 {
978 CFFactor buf= result.getFirst();
979 result.removeFirst();
981 result.insert (buf);
982 }
983 return result;
984}
static void sort(int **points, int sizePoints)
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
CFFList sqrFreeZ(const CanonicalForm &a)
CFFList sortCFFList(CFFList &F)

◆ sqrt()

CanonicalForm sqrt ( const CanonicalForm & a)
inline

Definition at line 490 of file factory.h.

490{ return a.sqrt(); }
CanonicalForm sqrt() const
CanonicalForm CanonicalForm::sqrt () const.

◆ subResChain()

CFArray subResChain ( const CanonicalForm & f,
const CanonicalForm & g,
const Variable & x )

CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )

subResChain() - caculate extended subresultant chain.

The chain is calculated from f and g with respect to variable x which should not be an algebraic variable. If f or q equals zero, an array consisting of one zero entry is returned.

Note: this is not the standard subresultant chain but the extended chain!

This algorithm is from the article of R. Loos - 'Generalized Polynomial Remainder Sequences' in B. Buchberger - 'Computer Algebra - Symbolic and Algebraic Computation' with some necessary extensions concerning the calculation of the first step.

Definition at line 42 of file cf_resultant.cc.

43{
44 ASSERT( x.level() > 0, "cannot calculate subresultant sequence with respect to algebraic variables" );
45
46 CFArray trivialResult( 0, 0 );
48 Variable X;
49
50 // some checks on triviality
51 if ( f.isZero() || g.isZero() ) {
52 trivialResult[0] = 0;
53 return trivialResult;
54 }
55
56 // make x main variable
57 if ( f.mvar() > x || g.mvar() > x ) {
58 if ( f.mvar() > g.mvar() )
59 X = f.mvar();
60 else
61 X = g.mvar();
62 F = swapvar( f, X, x );
63 G = swapvar( g, X, x );
64 }
65 else {
66 X = x;
67 F = f;
68 G = g;
69 }
70 // at this point, we have to calculate the sequence of F and
71 // G in respect to X where X is equal to or greater than the
72 // main variables of F and G
73
74 // initialization of chain
75 int m = degree( F, X );
76 int n = degree( G, X );
77
78 int j = (m <= n) ? n : m-1;
79 int r;
80
81 CFArray S( 0, j+1 );
83 S[j+1] = F; S[j] = G;
84
85 // make sure that S[j+1] is regular and j < n
86 if ( m == n && j > 0 ) {
87 S[j-1] = LC( S[j], X ) * psr( S[j+1], S[j], X );
88 j--;
89 } else if ( m < n ) {
90 S[j-1] = LC( S[j], X ) * LC( S[j], X ) * S[j+1];
91 j--;
92 } else if ( m > n && j > 0 ) {
93 // calculate first step
94 r = degree( S[j], X );
95 R = LC( S[j+1], X );
96
97 // if there was a gap calculate similar polynomial
98 if ( j > r && r >= 0 )
99 S[r] = power( LC( S[j], X ), j - r ) * S[j] * power( R, j - r );
100
101 if ( r > 0 ) {
102 // calculate remainder
103 S[r-1] = psr( S[j+1], S[j], X ) * power( -R, j - r );
104 j = r-1;
105 }
106 }
107
108 while ( j > 0 ) {
109 // at this point, 0 < j < n and S[j+1] is regular
110 r = degree( S[j], X );
111 R = LC( S[j+1], X );
112
113 // if there was a gap calculate similar polynomial
114 if ( j > r && r >= 0 )
115 S[r] = (power( LC( S[j], X ), j - r ) * S[j]) / power( R, j - r );
116
117 if ( r <= 0 ) break;
118 // calculate remainder
119 S[r-1] = psr( S[j+1], S[j], X ) / power( -R, j - r + 2 );
120
121 j = r-1;
122 // again 0 <= j < r <= jOld and S[j+1] is regular
123 }
124
125 for ( j = 0; j <= S.max(); j++ ) {
126 // reswap variables if necessary
127 if ( X != x ) {
128 S[j] = swapvar( S[j], X, x );
129 }
130 }
131
132 return S;
133}
CanonicalForm psr(const CanonicalForm &rr, const CanonicalForm &vv, const Variable &x)
CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )

◆ swapvar()

swapvar() - swap variables x1 and x2 in f.

Returns the image of f under the map which maps x1 to x2 and x2 to x1. This is done quite efficiently because it is used really often. x1 and x2 should be polynomial variables.

Definition at line 168 of file cf_ops.cc.

169{
170 ASSERT( x1.level() > 0 && x2.level() > 0, "cannot swap algebraic Variables" );
171 if ( f.inCoeffDomain() || x1 == x2 || ( x1 > f.mvar() && x2 > f.mvar() ) )
172 return f;
173 else
174 {
176 if ( x1 > x2 )
177 {
178 sv_x1 = x2; sv_x2 = x1;
179 }
180 else
181 {
182 sv_x1 = x1; sv_x2 = x2;
183 }
184 if ( f.mvar() < sv_x2 )
185 // we only have to replace sv_x1 by sv_x2
186 swapvar_between( f, result, 1, 0 );
187 else
188 // we really have to swap variables
189 swapvar_rec( f, result, 1 );
190 return result;
191 }
192}
static void swapvar_rec(const CanonicalForm &f, CanonicalForm &result, const CanonicalForm &term)
swapvar_between() - swap occurences of sv_x1 and sv_x2 in f.
Definition cf_ops.cc:113
static void swapvar_between(const CanonicalForm &f, CanonicalForm &result, const CanonicalForm &term, int expx2)
static void swapvar_between ( const CanonicalForm & f, CanonicalForm & result, const CanonicalForm & ...
Definition cf_ops.cc:58

◆ tailcoeff() [1/2]

CanonicalForm tailcoeff ( const CanonicalForm & f)
inline

Definition at line 466 of file factory.h.

466{ return f.tailcoeff(); }

◆ tailcoeff() [2/2]

CanonicalForm tailcoeff ( const CanonicalForm & f,
const Variable & v )
inline

Definition at line 469 of file factory.h.

469{ return f.tailcoeff(v); }

◆ taildegree()

int taildegree ( const CanonicalForm & f)
inline

Definition at line 463 of file factory.h.

463{ return f.taildegree(); }

◆ totaldegree() [1/2]

int totaldegree ( const CanonicalForm & f)

int totaldegree ( const CanonicalForm & f )

totaldegree() - return the total degree of f.

If f is zero, return -1. If f is in a coefficient domain, return 0. Otherwise return the total degree of f in all polynomial variables.

Definition at line 523 of file cf_ops.cc.

524{
525 if ( f.isZero() )
526 return -1;
527 else if ( f.inCoeffDomain() )
528 return 0;
529 else
530 {
532 int cdeg = 0, dummy;
533 // calculate maximum over all coefficients of f, taking
534 // in account our own exponent
535 for ( i = f; i.hasTerms(); i++ )
536 if ( (dummy = totaldegree( i.coeff() ) + i.exp()) > cdeg )
537 cdeg = dummy;
538 return cdeg;
539 }
540}
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition cf_ops.cc:523

◆ totaldegree() [2/2]

int totaldegree ( const CanonicalForm & f,
const Variable & v1,
const Variable & v2 )

int totaldegree ( const CanonicalForm & f, const Variable & v1, const Variable & v2 )

totaldegree() - return the total degree of f as a polynomial in the polynomial variables between v1 and v2 (inclusively).

If f is zero, return -1. If f is in a coefficient domain, return 0. Also, return 0 if v1 > v2. Otherwise, take f to be a polynomial in the polynomial variables between v1 and v2 and return its total degree.

Definition at line 554 of file cf_ops.cc.

555{
556 if ( f.isZero() )
557 return -1;
558 else if ( v1 > v2 )
559 return 0;
560 else if ( f.inCoeffDomain() )
561 return 0;
562 else if ( f.mvar() < v1 )
563 return 0;
564 else if ( f.mvar() == v1 )
565 return f.degree();
566 else if ( f.mvar() > v2 )
567 {
568 // v2's level is larger than f's level, descend down
570 int cdeg = 0, dummy;
571 // calculate maximum over all coefficients of f
572 for ( i = f; i.hasTerms(); i++ )
573 if ( (dummy = totaldegree( i.coeff(), v1, v2 )) > cdeg )
574 cdeg = dummy;
575 return cdeg;
576 }
577 else
578 {
579 // v1 < f.mvar() <= v2
581 int cdeg = 0, dummy;
582 // calculate maximum over all coefficients of f, taking
583 // in account our own exponent
584 for ( i = f; i.hasTerms(); i++ )
585 if ( (dummy = totaldegree( i.coeff(), v1, v2 ) + i.exp()) > cdeg )
586 cdeg = dummy;
587 return cdeg;
588 }
589}

◆ tryFdivides()

bool tryFdivides ( const CanonicalForm & f,
const CanonicalForm & g,
const CanonicalForm & M,
bool & fail )

same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f

Definition at line 456 of file cf_algorithm.cc.

457{
458 fail= false;
459 // trivial cases
460 if ( g.isZero() )
461 return true;
462 else if ( f.isZero() )
463 return false;
464
465 if (f.inCoeffDomain() || g.inCoeffDomain())
466 {
467 // if we are in a field all elements not equal to zero are units
468 if ( f.inCoeffDomain() )
469 {
470 CanonicalForm inv;
471 tryInvert (f, M, inv, fail);
472 return !fail;
473 }
474 else
475 {
476 return false;
477 }
478 }
479
480 // we may assume now that both levels either equal LEVELBASE
481 // or are greater zero
482 int fLevel = f.level();
483 int gLevel = g.level();
484 if ( (gLevel > 0) && (fLevel == gLevel) )
485 {
486 if (degree( f ) > degree( g ))
487 return false;
488 bool dividestail= tryFdivides (f.tailcoeff(), g.tailcoeff(), M, fail);
489
490 if (fail || !dividestail)
491 return false;
492 bool dividesLC= tryFdivides (f.LC(),g.LC(), M, fail);
493 if (fail || !dividesLC)
494 return false;
495 CanonicalForm q,r;
496 bool divides= tryDivremt (g, f, q, r, M, fail);
497 if (fail || !divides)
498 return false;
499 return r.isZero();
500 }
501 else if ( gLevel < fLevel )
502 {
503 // g is a coefficient w.r.t. f
504 return false;
505 }
506 else
507 {
508 // either f is a coefficient w.r.t. polynomial g or both
509 // f and g are from a base domain (should be Z or Z/p^n,
510 // then)
511 CanonicalForm q, r;
512 bool divides= tryDivremt (g, f, q, r, M, fail);
513 if (fail || !divides)
514 return false;
515 return r.isZero();
516 }
517}
bool tryDivremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, const CanonicalForm &M, bool &fail)
same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
bool tryFdivides(const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f

◆ vcontent()

CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )

vcontent() - return content of f with repect to variables >= x.

The content is recursively calculated over all coefficients in f having level less than x. x should be a polynomial variable.

Definition at line 653 of file cf_gcd.cc.

654{
655 ASSERT( x.level() > 0, "cannot calculate vcontent with respect to algebraic variable" );
656
657 if ( f.mvar() <= x )
658 return content( f, x );
659 else {
661 CanonicalForm d = 0;
662 for ( i = f; i.hasTerms() && ! d.isOne(); i++ )
663 d = gcd( d, vcontent( i.coeff(), x ) );
664 return d;
665 }
666}
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition cf_gcd.cc:653

Variable Documentation

◆ factoryConfiguration

const char factoryConfiguration[]
extern

◆ factoryError

EXTERN_VAR void(* factoryError) (const char *s) ( const char * s)

Definition at line 1127 of file factory.h.

◆ singular_homog_flag

EXTERN_VAR int singular_homog_flag

Definition at line 586 of file factory.h.

◆ SW_BERLEKAMP

const int SW_BERLEKAMP =10
static

set to 1 to use Factorys Berlekamp alg.

Definition at line 108 of file factory.h.

◆ SW_FAC_QUADRATICLIFT

const int SW_FAC_QUADRATICLIFT =11
static

Definition at line 110 of file factory.h.

◆ SW_RATIONAL

const int SW_RATIONAL = 0
static

set to 1 for computations over Q

Definition at line 88 of file factory.h.

◆ SW_SYMMETRIC_FF

const int SW_SYMMETRIC_FF = 1
static

set to 1 for symmetric representation over F_q

Definition at line 90 of file factory.h.

◆ SW_USE_CHINREM_GCD

const int SW_USE_CHINREM_GCD =5
static

set to 1 to use modular gcd over Z

Definition at line 98 of file factory.h.

◆ SW_USE_EZGCD

const int SW_USE_EZGCD = 2
static

set to 1 to use EZGCD over Z

Definition at line 92 of file factory.h.

◆ SW_USE_EZGCD_P

const int SW_USE_EZGCD_P = 3
static

set to 1 to use EZGCD over F_q

Definition at line 94 of file factory.h.

◆ SW_USE_FF_MOD_GCD

const int SW_USE_FF_MOD_GCD =7
static

set to 1 to use modular GCD over F_q

Definition at line 102 of file factory.h.

◆ SW_USE_FL_FAC_0

const int SW_USE_FL_FAC_0 =13
static

set to 1 to prefer flints multivariate factorization over Z/p

Definition at line 114 of file factory.h.

◆ SW_USE_FL_FAC_0A

const int SW_USE_FL_FAC_0A =14
static

set to 1 to prefer flints multivariate factorization over Z/p(a)

Definition at line 116 of file factory.h.

◆ SW_USE_FL_FAC_P

const int SW_USE_FL_FAC_P =12
static

set to 1 to prefer flints multivariate factorization over Z/p

Definition at line 112 of file factory.h.

◆ SW_USE_FL_GCD_0

const int SW_USE_FL_GCD_0 =9
static

set to 1 to use Flints gcd over Q/Z

Definition at line 106 of file factory.h.

◆ SW_USE_FL_GCD_P

const int SW_USE_FL_GCD_P =8
static

set to 1 to use Flints gcd over F_p

Definition at line 104 of file factory.h.

◆ SW_USE_NTL_SORT

const int SW_USE_NTL_SORT =4
static

set to 1 to sort factors in a factorization

Definition at line 96 of file factory.h.

◆ SW_USE_QGCD

const int SW_USE_QGCD =6
static

set to 1 to use Encarnacion GCD over Q(a)

Definition at line 100 of file factory.h.