My Project  debian-1:4.1.1-p2+ds-4
Data Structures | Macros | Typedefs | Functions | Variables
factory.h File Reference
#include "factory/factoryconf.h"
#include <stdint.h>
#include "omalloc/omalloc.h"
#include "omalloc/omallocClass.h"
#include "factory/cf_gmp.h"
#include "factory/templates/ftmpl_array.h"
#include "factory/templates/ftmpl_afactor.h"
#include "factory/templates/ftmpl_factor.h"
#include "factory/templates/ftmpl_list.h"
#include "factory/templates/ftmpl_matrix.h"

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 LEVELBASE   -1000000
 
#define LEVELTRANS   -500000
 
#define LEVELQUOT   1000000
 
#define LEVELEXPR   1000001
 
#define UndefinedDomain   32000
 
#define GaloisFieldDomain   4
 
#define FiniteFieldDomain   3
 
#define RationalDomain   2
 
#define IntegerDomain   1
 
#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 cf_getPrime (int i)
 
int cf_getNumPrimes ()
 
int cf_getSmallPrime (int i)
 
int cf_getNumSmallPrimes ()
 
int cf_getBigPrime (int i)
 
int cf_getNumBigPrimes ()
 
Variable rootOf (const CanonicalForm &, char name='@')
 returns a symbolic root of polynomial with name name Use it to define algebraic variables More...
 
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 prune (Variable &alpha)
 
void prune1 (const Variable &alpha)
 
int ExtensionLevel ()
 
int is_imm (const InternalCF *const ptr)
 
CF_INLINE CanonicalForm operator+ (const CanonicalForm &, const CanonicalForm &)
 CF_INLINE CanonicalForm operator +, -, *, /, % ( const CanonicalForm & lhs, const CanonicalForm & rhs ) More...
 
CF_NO_INLINE CanonicalForm operator- (const CanonicalForm &, const CanonicalForm &)
 
CF_INLINE CanonicalForm operator* (const CanonicalForm &, const CanonicalForm &)
 
CF_NO_INLINE CanonicalForm operator/ (const CanonicalForm &, const CanonicalForm &)
 
CF_NO_INLINE CanonicalForm operator% (const CanonicalForm &, const CanonicalForm &)
 
CF_NO_INLINE CanonicalForm div (const CanonicalForm &, const CanonicalForm &)
 CF_INLINE CanonicalForm div, mod ( const CanonicalForm & lhs, const CanonicalForm & rhs ) More...
 
CF_NO_INLINE CanonicalForm mod (const CanonicalForm &, const CanonicalForm &)
 
CanonicalForm blcm (const CanonicalForm &f, const CanonicalForm &g)
 
CanonicalForm power (const CanonicalForm &f, int n)
 exponentiation More...
 
CanonicalForm power (const Variable &v, int n)
 exponentiation More...
 
CanonicalForm gcd (const CanonicalForm &, const CanonicalForm &)
 
CanonicalForm gcd_poly (const CanonicalForm &f, const CanonicalForm &g)
 CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g ) More...
 
CanonicalForm lcm (const CanonicalForm &, const CanonicalForm &)
 CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g ) More...
 
CanonicalForm pp (const CanonicalForm &)
 CanonicalForm pp ( const CanonicalForm & f ) More...
 
CanonicalForm content (const CanonicalForm &)
 CanonicalForm content ( const CanonicalForm & f ) More...
 
CanonicalForm content (const CanonicalForm &, const Variable &)
 CanonicalForm content ( const CanonicalForm & f, const Variable & x ) More...
 
CanonicalForm icontent (const CanonicalForm &f)
 CanonicalForm icontent ( const CanonicalForm & f ) More...
 
CanonicalForm vcontent (const CanonicalForm &f, const Variable &x)
 CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x ) More...
 
CanonicalForm swapvar (const CanonicalForm &, const Variable &, const Variable &)
 swapvar() - swap variables x1 and x2 in f. More...
 
CanonicalForm replacevar (const CanonicalForm &, const Variable &, const Variable &)
 CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ) More...
 
int getNumVars (const CanonicalForm &f)
 int getNumVars ( const CanonicalForm & f ) More...
 
CanonicalForm getVars (const CanonicalForm &f)
 CanonicalForm getVars ( const CanonicalForm & f ) More...
 
CanonicalForm apply (const CanonicalForm &f, void(*mf)(CanonicalForm &, int &))
 CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) ) More...
 
CanonicalForm mapdomain (const CanonicalForm &f, CanonicalForm(*mf)(const CanonicalForm &))
 CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) ) More...
 
int * degrees (const CanonicalForm &f, int *degs=0)
 int * degrees ( const CanonicalForm & f, int * degs ) More...
 
int totaldegree (const CanonicalForm &f)
 int totaldegree ( const CanonicalForm & f ) More...
 
int totaldegree (const CanonicalForm &f, const Variable &v1, const Variable &v2)
 int totaldegree ( const CanonicalForm & f, const Variable & v1, const Variable & v2 ) More...
 
int size (const CanonicalForm &f, const Variable &v)
 int size ( const CanonicalForm & f, const Variable & v ) More...
 
int size (const CanonicalForm &f)
 int size ( const CanonicalForm & f ) More...
 
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 More...
 
bool hasFirstAlgVar (const CanonicalForm &f, Variable &a)
 check if poly f contains an algebraic variable a More...
 
CanonicalForm leftShift (const CanonicalForm &F, int n)
 left shift the main variable of F by n More...
 
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 setCharacteristic (int c)
 
void setCharacteristic (int c, int n)
 
void setCharacteristic (int c, int n, char name)
 
int getCharacteristic ()
 
int getGFDegree ()
 
CanonicalForm getGFGenerator ()
 
void On (int)
 switches More...
 
void Off (int)
 switches More...
 
bool isOn (int)
 switches More...
 
CanonicalForm psr (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
 
CanonicalForm psq (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
 
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 ) More...
 
CanonicalForm bCommonDen (const CanonicalForm &f)
 CanonicalForm bCommonDen ( const CanonicalForm & f ) More...
 
bool fdivides (const CanonicalForm &f, const CanonicalForm &g)
 bool fdivides ( const CanonicalForm & f, const CanonicalForm & g ) More...
 
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 More...
 
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 More...
 
CanonicalForm maxNorm (const CanonicalForm &f)
 CanonicalForm maxNorm ( const CanonicalForm & f ) More...
 
CanonicalForm euclideanNorm (const CanonicalForm &f)
 CanonicalForm euclideanNorm ( const CanonicalForm & f ) More...
 
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, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew ) More...
 
void chineseRemainder (const CFArray &x, const CFArray &q, CanonicalForm &xnew, CanonicalForm &qnew)
 void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew ) More...
 
void chineseRemainderCached (CFArray &a, CFArray &n, CanonicalForm &xnew, CanonicalForm &prod, CFArray &inv)
 
CanonicalForm Farey (const CanonicalForm &f, const CanonicalForm &q)
 Farey rational reconstruction. More...
 
bool isPurePoly (const CanonicalForm &f)
 
bool isPurePoly_m (const CanonicalForm &f)
 
CFFList factorize (const CanonicalForm &f, bool issqrfree=false)
 factorization over $ F_p $ or $ Q $ More...
 
CFFList factorize (const CanonicalForm &f, const Variable &alpha)
 factorization over $ F_p(\alpha) $ or $ Q(\alpha) $ More...
 
CFFList sqrFree (const CanonicalForm &f, bool sort=false)
 squarefree factorization More...
 
CanonicalForm homogenize (const CanonicalForm &f, const Variable &x)
 homogenize homogenizes f with Variable x More...
 
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. More...
 
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. More...
 
bool linearSystemSolve (CFMatrix &M)
 
CanonicalForm 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 ) More...
 
CanonicalForm resultant (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
 
CanonicalForm abs (const CanonicalForm &f)
 inline CanonicalForm abs ( const CanonicalForm & f ) More...
 
int factoryrandom (int n)
 random integers with abs less than n More...
 
void factoryseed (int s)
 random seed initializer More...
 
CanonicalForm replaceLc (const CanonicalForm &f, const CanonicalForm &c)
 
CanonicalForm compress (const CanonicalForm &f, CFMap &m)
 CanonicalForm compress ( const CanonicalForm & f, CFMap & m ) More...
 
void compress (const CFArray &a, CFMap &M, CFMap &N)
 void compress ( const CFArray & a, CFMap & M, CFMap & N ) More...
 
void compress (const CanonicalForm &f, const CanonicalForm &g, CFMap &M, CFMap &N)
 void compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N ) More...
 
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. More...
 
CFMatrixcf_LLL (CFMatrix &A)
 performs LLL reduction. More...
 
void gmp_numerator (const CanonicalForm &f, mpz_ptr result)
 
void gmp_denominator (const CanonicalForm &f, mpz_ptr result)
 
int gf_value (const CanonicalForm &f)
 
CanonicalForm make_cf (const mpz_ptr n)
 
CanonicalForm 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 ipower (int b, int n)
 int ipower ( int b, int m ) More...
 
void factoryError_intern (const char *s)
 
int probIrredTest (const CanonicalForm &F, double error)
 given some error probIrredTest detects irreducibility or reducibility of F with confidence level 1-error More...
 
CFAFList absFactorize (const CanonicalForm &G)
 absolute factorization of a multivariate poly over Q More...
 
CanonicalForm resultantZ (const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob=true)
 modular resultant algorihtm over Z More...
 
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 $. More...
 
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 $. More...
 
CanonicalForm Prem (const CanonicalForm &F, const CanonicalForm &G)
 pseudo remainder of F by G with certain factors of LC (g) cancelled More...
 
CFList basicSet (const CFList &PS)
 basic set in the sense of Wang a.k.a. minimal ascending set in the sense of Greuel/Pfister More...
 
CFList charSet (const CFList &PS)
 characteristic set More...
 
CFList modCharSet (const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true)
 modified medial set More...
 
CFList modCharSet (const CFList &PS, bool removeContents)
 
CFList charSetViaCharSetN (const CFList &PS)
 compute a characteristic set via medial set More...
 
CFList charSetN (const CFList &PS)
 medial set More...
 
CFList charSetViaModCharSet (const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true)
 modified characteristic set, i.e. a characteristic set with certain factors removed More...
 
CFList charSetViaModCharSet (const CFList &PS, bool removeContents=true)
 modified characteristic set, i.e. a characteristic set with certain factors removed More...
 
ListCFList charSeries (const CFList &L)
 characteristic series More...
 
ListCFList irrCharSeries (const CFList &PS)
 irreducible characteristic series More...
 
Varlist neworder (const CFList &PolyList)
 
CFList newordercf (const CFList &PolyList)
 
IntList 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 extgcd (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
 CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b ) More...
 

Variables

const char factoryConfiguration []
 
static const int SW_RATIONAL = 0
 set to 1 for computations over Q More...
 
static const int SW_SYMMETRIC_FF = 1
 set to 1 for symmetric representation over F_q More...
 
static const int SW_USE_EZGCD = 2
 set to 1 to use EZGCD over Z More...
 
static const int SW_USE_EZGCD_P = 3
 set to 1 to use EZGCD over F_q More...
 
static const int SW_USE_NTL_SORT =4
 set to 1 to sort factors in a factorization More...
 
static const int SW_USE_CHINREM_GCD =5
 set to 1 to use modular gcd over Z More...
 
static const int SW_USE_QGCD =6
 set to 1 to use Encarnacion GCD over Q(a) More...
 
static const int SW_USE_FF_MOD_GCD =7
 set to 1 to use modular GCD over F_q More...
 
int singular_homog_flag
 
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 781 of file factory.h.

◆ CF_INLINE [2/2]

#define CF_INLINE

Definition at line 781 of file factory.h.

◆ CF_NO_INLINE [1/2]

#define CF_NO_INLINE

Definition at line 783 of file factory.h.

◆ CF_NO_INLINE [2/2]

#define CF_NO_INLINE

Definition at line 783 of file factory.h.

◆ FiniteFieldDomain

#define FiniteFieldDomain   3

Definition at line 87 of file factory.h.

◆ GaloisFieldDomain

#define GaloisFieldDomain   4

Definition at line 86 of file factory.h.

◆ IntegerDomain

#define IntegerDomain   1

Definition at line 89 of file factory.h.

◆ LEVELBASE

#define LEVELBASE   -1000000

Definition at line 80 of file factory.h.

◆ LEVELEXPR

#define LEVELEXPR   1000001

Definition at line 83 of file factory.h.

◆ LEVELQUOT

#define LEVELQUOT   1000000

Definition at line 82 of file factory.h.

◆ LEVELTRANS

#define LEVELTRANS   -500000

Definition at line 81 of file factory.h.

◆ RationalDomain

#define RationalDomain   2

Definition at line 88 of file factory.h.

◆ UndefinedDomain

#define UndefinedDomain   32000

Definition at line 85 of file factory.h.

Typedef Documentation

◆ CFAFactor

Definition at line 519 of file factory.h.

◆ CFAFList

Definition at line 520 of file factory.h.

◆ CFAFListIterator

Definition at line 521 of file factory.h.

◆ CFArray

Definition at line 527 of file factory.h.

◆ CFFactor

Definition at line 522 of file factory.h.

◆ CFFList

typedef List<CFFactor> CFFList

Definition at line 523 of file factory.h.

◆ CFFListIterator

Definition at line 524 of file factory.h.

◆ CFList

Definition at line 525 of file factory.h.

◆ CFListIterator

Definition at line 526 of file factory.h.

◆ CFMatrix

Definition at line 528 of file factory.h.

◆ Intarray

typedef Array<int> Intarray

Definition at line 535 of file factory.h.

◆ IntList

typedef List<int> IntList

Definition at line 531 of file factory.h.

◆ IntListIterator

Definition at line 532 of file factory.h.

◆ ListCFList

Definition at line 529 of file factory.h.

◆ ListCFListIterator

Definition at line 530 of file factory.h.

◆ MPList

typedef List<MapPair> MPList

Definition at line 974 of file factory.h.

◆ MPListIterator

Definition at line 975 of file factory.h.

◆ termList

typedef term* termList

Definition at line 786 of file factory.h.

◆ Varlist

typedef List<Variable> Varlist

Definition at line 533 of file factory.h.

◆ VarlistIterator

Definition at line 534 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 626 of file factory.h.

627 {
628  // it is not only more general to use `sign()' instead of a
629  // direct comparison `f < 0', it is faster, too
630  if ( sign( f ) < 0 )
631  return -f;
632  else
633  return f;
634 }

◆ absFactorize()

CFAFList absFactorize ( const CanonicalForm G)

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 267 of file facAbsFact.cc.

269 {
270  //TODO handle homogeneous input, is already done in LIB interface but still...
271  ASSERT (getCharacteristic() == 0, "expected poly over Q");
272 
273  CanonicalForm F= G;
274 
275  CanonicalForm LcF= Lc (F);
276  bool isRat= isOn (SW_RATIONAL);
277  if (isRat)
278  F *= bCommonDen (F);
279 
280  Off (SW_RATIONAL);
281  F /= icontent (F);
282  if (isRat)
283  On (SW_RATIONAL);
284 
285  CFFList rationalFactors= factorize (F);
286 
287  CFAFList result, resultBuf;
288 
290  CFFListIterator i= rationalFactors;
291  i++;
292  for (; i.hasItem(); i++)
293  {
294  resultBuf= absFactorizeMain (i.getItem().factor());
295  for (iter= resultBuf; iter.hasItem(); iter++)
296  iter.getItem()= CFAFactor (iter.getItem().factor(),
297  iter.getItem().minpoly(), i.getItem().exp());
298  result= Union (result, resultBuf);
299  }
300 
301  if (isRat)
302  normalize (result);
303  result.insert (CFAFactor (LcF, 1, 1));
304 
305  return result;
306 }

◆ apply()

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

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--;
}

Then apply( f, diff ) is differentation 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;
415  CFIterator i;
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 }

◆ 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 }

◆ bCommonDen()

CanonicalForm bCommonDen ( const CanonicalForm f)

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  // otherwise `bgcd()' returns one
297  Off( SW_RATIONAL );
299  On( SW_RATIONAL );
300  return result;
301  } else
302  return CanonicalForm( 1 );
303 }

◆ blcm()

Definition at line 1757 of file canonicalform.cc.

1758 {
1759  if ( f.isZero() || g.isZero() )
1760  return CanonicalForm( 0L );
1761 /*
1762  else if (f.isOne())
1763  return g;
1764  else if (g.isOne())
1765  return f;
1766 */
1767  else
1768  return (f / bgcd( f, g )) * g;
1769 }

◆ cf_getBigPrime()

int 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 }

◆ cf_getNumBigPrimes()

int cf_getNumBigPrimes ( )

Definition at line 45 of file cf_primes.cc.

46 {
47  return NUMBIGPRIMES;
48 }

◆ cf_getNumPrimes()

int cf_getNumPrimes ( )

Definition at line 23 of file cf_primes.cc.

24 {
25  return NUMPRIMES;
26 }

◆ cf_getNumSmallPrimes()

int cf_getNumSmallPrimes ( )

Definition at line 34 of file cf_primes.cc.

35 {
36  return NUMSMALLPRIMES;
37 }

◆ cf_getPrime()

int 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 )
18  return bigprimes[i-NUMSMALLPRIMES];
19  else
20  return smallprimes[i];
21 }

◆ cf_getSmallPrime()

int 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 38 of file cf_hnf.cc.

39 {
40  mat_ZZ *AA=convertFacCFMatrix2NTLmat_ZZ(A);
41  ZZ DD=convertFacCF2NTLZZ(determinant(A,A.rows()));
42  mat_ZZ WW;
43  HNF(WW,*AA,DD);
44  delete AA;
46 }

◆ 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

Definition at line 48 of file cf_hnf.cc.

49 {
50  mat_ZZ *AA=convertFacCFMatrix2NTLmat_ZZ(A);
51  #if 0
52  LLL_RR(*AA);
53  #else
54  ZZ det2;
55  LLL(det2,*AA,0L);
56  #endif
58  delete AA;
59  return r;
60 }

◆ 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  {
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 }

◆ 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;
191  CanonicalForm r;
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 }

◆ 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;
220  CanonicalForm r;
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 }

◆ 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 
261  CFList result= charSetN (L);
262 
263  if (result.isEmpty() || result.getFirst().inCoeffDomain())
264  return CFList(1);
265 
266  CanonicalForm r;
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 }

◆ 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 
379  CanonicalForm r;
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 }

◆ chineseRemainder() [1/2]

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, 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 52 of file cf_chinese.cc.

53 {
54  DEBINCLEVEL( cerr, "chineseRemainder" );
55 
56  DEBOUTLN( cerr, "log(q1) = " << q1.ilog2() );
57  DEBOUTLN( cerr, "log(q2) = " << q2.ilog2() );
58 
59  // We calculate xnew as follows:
60  // xnew = v1 + v2 * q1
61  // where
62  // v1 = x1 (mod q1)
63  // v2 = (x2-v1)/q1 (mod q2) (*)
64  //
65  // We do one extra test to check whether x2-v1 vanishes (mod
66  // q2) in (*) since it is not costly and may save us
67  // from calculating the inverse of q1 (mod q2).
68  //
69  // u: v1 (mod q2)
70  // d: x2-v1 (mod q2)
71  // s: 1/q1 (mod q2)
72  //
73  CanonicalForm v2, v1;
74  CanonicalForm u, d, s, dummy;
75 
76  v1 = mod( x1, q1 );
77  u = mod( v1, q2 );
78  d = mod( x2-u, q2 );
79  if ( d.isZero() )
80  {
81  xnew = v1;
82  qnew = q1 * q2;
83  DEBDECLEVEL( cerr, "chineseRemainder" );
84  return;
85  }
86  (void)bextgcd( q1, q2, s, dummy );
87  v2 = mod( d*s, q2 );
88  xnew = v1 + v2*q1;
89 
90  // After all, calculate new modulus. It is important that
91  // this is done at the very end of the algorithm, since q1
92  // and qnew may refer to the same object (same is true for x1
93  // and xnew).
94  qnew = q1 * q2;
95 
96  DEBDECLEVEL( cerr, "chineseRemainder" );
97 }

◆ chineseRemainder() [2/2]

void 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 119 of file cf_chinese.cc.

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

◆ chineseRemainderCached()

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

Definition at line 265 of file cf_chinese.cc.

266 {
267  CanonicalForm p, sum=0L; prod=1L;
268  int i;
269  int len=n.size();
270 
271  for (i = 0; i < len; i++) prod *= n[i];
272 
273  for (i = 0; i < len; i++)
274  {
275  p = prod / n[i];
276  sum += a[i] * chin_mul_inv(p, n[i], i, inv) * p;
277  }
278 
279  xnew = mod(sum , prod);
280 }

◆ 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 }

◆ 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 }

◆ 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 }

◆ content() [1/2]

CanonicalForm content ( const CanonicalForm f)

CanonicalForm content ( const CanonicalForm & f )

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

Normalizes result.

Definition at line 180 of file cf_gcd.cc.

181 {
182  if ( f.inPolyDomain() || ( f.inExtension() && ! getReduce( f.mvar() ) ) )
183  {
184  CFIterator i = f;
185  CanonicalForm result = abs( i.coeff() );
186  i++;
187  while ( i.hasTerms() && ! result.isOne() )
188  {
189  result = gcd( i.coeff(), result );
190  i++;
191  }
192  return result;
193  }
194  else
195  return abs( f );
196 }

◆ content() [2/2]

CanonicalForm content ( const CanonicalForm f,
const Variable x 
)

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 206 of file cf_gcd.cc.

207 {
208  if (f.inBaseDomain()) return f;
209  ASSERT( x.level() > 0, "cannot calculate content with respect to algebraic variable" );
210  Variable y = f.mvar();
211 
212  if ( y == x )
213  return cf_content( f, 0 );
214  else if ( y < x )
215  return f;
216  else
217  return swapvar( content( swapvar( f, y, x ), y ), y, x );
218 }

◆ degree() [1/2]

int degree ( const CanonicalForm f)
inline

Definition at line 446 of file factory.h.

446 { return f.degree(); }

◆ degree() [2/2]

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

Definition at line 449 of file factory.h.

449 { return f.degree( v ); }

◆ 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 }

◆ den()

CanonicalForm den ( const CanonicalForm f)
inline

Definition at line 470 of file factory.h.

470 { return f.den(); }

◆ deriv()

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

Definition at line 476 of file factory.h.

476 { return f.deriv( x ); }

◆ determinant()

CanonicalForm 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 );
258  setCharacteristic( p );
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);
268  setCharacteristic( 0 );
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 }

◆ div()

CF_INLINE CanonicalForm div, mod ( const CanonicalForm & lhs, const CanonicalForm & rhs )

See also
mod(), operator/(), CanonicalForm::operator /=()

Definition at line 553 of file cf_inline.cc.

554 {
555  CanonicalForm result( lhs );
556  result.div( rhs );
557  return result;
558 }

◆ 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 563 of file cf_algorithm.cc.

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

◆ 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 }

◆ 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 173 of file cfUnivarGcd.cc.

174 {
175  if (f.isZero())
176  {
177  a= 0;
178  b= 1;
179  return g;
180  }
181  else if (g.isZero())
182  {
183  a= 1;
184  b= 0;
185  return f;
186  }
187 #ifdef HAVE_NTL
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());
202  nmod_poly_clear (F1);
203  nmod_poly_clear (G1);
204  nmod_poly_clear (A);
205  nmod_poly_clear (B);
206  nmod_poly_clear (R);
207  return r;
208  }
209 #else
211  && (f.level()==g.level()) && isPurePoly(f) && isPurePoly(g))
212  {
214  {
216  zz_p::init(getCharacteristic());
217  }
218  zz_pX F1=convertFacCF2NTLzzpX(f);
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 #else
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);
259  CanonicalForm r=convertNTLZZX2CF(R,f.mvar());
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 #endif
305  // may contain bug in the co-factors, see track 107
306  CanonicalForm contf = content( f );
307  CanonicalForm contg = content( g );
308 
309  CanonicalForm p0 = f / contf, p1 = g / contg;
310  CanonicalForm f0 = 1, f1 = 0, g0 = 0, g1 = 1, q, r;
311 
312  while ( ! p1.isZero() )
313  {
314  divrem( p0, p1, q, r );
315  p0 = p1; p1 = r;
316  r = g0 - g1 * q;
317  g0 = g1; g1 = r;
318  r = f0 - f1 * q;
319  f0 = f1; f1 = r;
320  }
321  CanonicalForm contp0 = content( p0 );
322  a = f0 / ( contf * contp0 );
323  b = g0 / ( contg * contp0 );
324  p0 /= contp0;
325  if ( p0.sign() < 0 )
326  {
327  p0 = -p0;
328  a = -a;
329  b = -b;
330  }
331  return p0;
332 }

◆ 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 }

◆ 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();
912  CFFListIterator jj;
913  CFList reduceresult;
914  CFFList result;
915 
916 // F1: [Test trivial cases]
917 // 1) first trivial cases:
918  if (vf.level() <= as.getLast().level())
919  {
920  if (!isRat && getCharacteristic() == 0)
921  Off (SW_RATIONAL);
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)
949  Off (SW_RATIONAL);
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)
977  Off (SW_RATIONAL);
978  return result;
979  }
980 
981  Fgcd= pp (Fgcd);
982  Ggcd= pp (Ggcd);
983  if (!isRat && getCharacteristic() == 0)
984  Off (SW_RATIONAL);
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 }

◆ factorize() [1/2]

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

factorization over $ F_p $ or $ Q $

Definition at line 390 of file cf_factor.cc.

391 {
392  if ( f.inCoeffDomain() )
393  return CFFList( f );
394 #ifndef NOASSERT
395  Variable a;
396  ASSERT (!hasFirstAlgVar (f, a), "f has an algebraic variable use factorize \
397  ( const CanonicalForm & f, const Variable & alpha ) instead");
398 #endif
399  //out_cf("factorize:",f,"==================================\n");
400  if (! f.isUnivariate() )
401  {
402  if ( singular_homog_flag && f.isHomogeneous())
403  {
405  int d_xn = degree(f,xn);
406  CFMap n;
407  CanonicalForm F = compress(f(1,xn),n);
408  CFFList Intermediatelist;
409  Intermediatelist = factorize(F);
410  CFFList Homoglist;
412  for ( j=Intermediatelist; j.hasItem(); j++ )
413  {
414  Homoglist.append(
415  CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
416  }
417  CFFList Unhomoglist;
418  CanonicalForm unhomogelem;
419  for ( j=Homoglist; j.hasItem(); j++ )
420  {
421  unhomogelem= homogenize(j.getItem().factor(),xn);
422  Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
423  d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
424  }
425  if ( d_xn != 0 ) // have to append xn^(d_xn)
426  Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
427  if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF);
428  return Unhomoglist;
429  }
430  }
431  CFFList F;
432  if ( getCharacteristic() > 0 )
433  {
434  if (f.isUnivariate())
435  {
436 #ifdef HAVE_NTL
437 #ifdef HAVE_FLINT
438  if (degree (f) < 300)
439  {
440  nmod_poly_t f1;
442  nmod_poly_factor_t result;
443  nmod_poly_factor_init (result);
444  mp_limb_t leadingCoeff= nmod_poly_factor (result, f1);
445  F= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, f.mvar());
446  nmod_poly_factor_clear (result);
447  nmod_poly_clear (f1);
448  }
449  else
450 #endif
451  {
452  // USE NTL
453  if (getCharacteristic()!=2)
454  {
456  {
458  zz_p::init(getCharacteristic());
459  }
460 
461  // convert to NTL
462  zz_pX f1=convertFacCF2NTLzzpX(f);
463  zz_p leadcoeff = LeadCoeff(f1);
464 
465  //make monic
466  f1=f1 / LeadCoeff(f1);
467  // factorize
468  vec_pair_zz_pX_long factors;
469  CanZass(factors,f1);
470 
471  F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
472  //test_cff(F,f);
473  }
474  else /*getCharacteristic()==2*/
475  {
476  // Specialcase characteristic==2
477  if (fac_NTL_char != 2)
478  {
479  fac_NTL_char = 2;
480  zz_p::init(2);
481  }
482  // convert to NTL using the faster conversion routine for characteristic 2
483  GF2X f1=convertFacCF2NTLGF2X(f);
484  // no make monic necessary in GF2
485  //factorize
486  vec_pair_GF2X_long factors;
487  CanZass(factors,f1);
488 
489  // convert back to factory again using the faster conversion routine for vectors over GF2X
490  F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
491  }
492  }
493 #else
494  // Use Factory without NTL
495  factoryError ("univariate factorization depends on NTL(missing)");
496  return CFFList (CFFactor (f, 1));
497 #endif //HAVE_NTL
498  }
499  else
500  {
501  #ifdef HAVE_NTL
502  if (issqrfree)
503  {
504  CFList factors;
505  Variable alpha;
507  factors= GFSqrfFactorize (f);
508  else
509  factors= FpSqrfFactorize (f);
510  for (CFListIterator i= factors; i.hasItem(); i++)
511  F.append (CFFactor (i.getItem(), 1));
512  }
513  else
514  {
515  Variable alpha;
517  F= GFFactorize (f);
518  else
519  F= FpFactorize (f);
520  }
521  #else
522  ASSERT( f.isUnivariate(), "multivariate factorization depends on NTL(missing)" );
523  factoryError ("multivariate factorization depends on NTL(missing)");
524  return CFFList (CFFactor (f, 1));
525  #endif
526  }
527  }
528  else
529  {
530  bool on_rational = isOn(SW_RATIONAL);
531  On(SW_RATIONAL);
533  CanonicalForm fz = f * cd;
534  Off(SW_RATIONAL);
535  if ( f.isUnivariate() )
536  {
537  #ifdef HAVE_NTL
538  //USE NTL
539  CanonicalForm ic=icontent(fz);
540  fz/=ic;
541  ZZ c;
542  vec_pair_ZZX_long factors;
543  //factorize the converted polynomial
544  factor(c,factors,convertFacCF2NTLZZX(fz));
545 
546  //convert the result back to Factory
548  if ( ! ic.isOne() )
549  {
550  if ( F.getFirst().factor().inCoeffDomain() )
551  {
552  CFFactor new_first( F.getFirst().factor() * ic );
553  F.removeFirst();
554  F.insert( new_first );
555  }
556  else
557  F.insert( CFFactor( ic ) );
558  }
559  else
560  {
561  if ( !F.getFirst().factor().inCoeffDomain() )
562  {
563  CFFactor new_first( 1 );
564  F.insert( new_first );
565  }
566  }
567  #else
568  factoryError ("univariate factorization over Z depends on NTL(missing)");
569  return CFFList (CFFactor (f, 1));
570  #endif
571  }
572  else
573  {
574  #ifdef HAVE_NTL
575  On (SW_RATIONAL);
576  if (issqrfree)
577  {
578  CFList factors;
579  factors= ratSqrfFactorize (fz);
580  for (CFListIterator i= factors; i.hasItem(); i++)
581  F.append (CFFactor (i.getItem(), 1));
582  }
583  else
584  F = ratFactorize (fz);
585  Off (SW_RATIONAL);
586  #else
587  factoryError ("multivariate factorization depends on NTL(missing)");
588  return CFFList (CFFactor (f, 1));
589  #endif
590  }
591 
592  if ( on_rational )
593  On(SW_RATIONAL);
594  if ( ! cd.isOne() )
595  {
596  if ( F.getFirst().factor().inCoeffDomain() )
597  {
598  CFFactor new_first( F.getFirst().factor() / cd );
599  F.removeFirst();
600  F.insert( new_first );
601  }
602  else
603  {
604  F.insert( CFFactor( 1/cd ) );
605  }
606  }
607  }
608 
609  //out_cff(F);
610  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
611  return F;
612 }

◆ factorize() [2/2]

CFFList factorize ( const CanonicalForm f,
const Variable alpha 
)

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

Definition at line 617 of file cf_factor.cc.

618 {
619  if ( f.inCoeffDomain() )
620  return CFFList( f );
621  //out_cf("factorize:",f,"==================================\n");
622  //out_cf("mipo:",getMipo(alpha),"\n");
623 
624  CFFList F;
625  ASSERT( alpha.level() < 0 && getReduce (alpha), "not an algebraic extension" );
626 #ifndef NOASSERT
627  Variable beta;
628  if (hasFirstAlgVar(f, beta))
629  ASSERT (beta == alpha, "f has an algebraic variable that \
630  does not coincide with alpha");
631 #endif
632  int ch=getCharacteristic();
633  if (f.isUnivariate()&& (ch>0))
634  {
635 #ifdef HAVE_NTL
636  //USE NTL
637  if (ch>2)
638  {
639 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
640  nmod_poly_t FLINTmipo, leadingCoeff;
641  fq_nmod_ctx_t fq_con;
642 
643  nmod_poly_init (FLINTmipo, getCharacteristic());
644  nmod_poly_init (leadingCoeff, getCharacteristic());
645  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
646 
647  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
648  fq_nmod_poly_t FLINTF;
650  fq_nmod_poly_factor_t res;
651  fq_nmod_poly_factor_init (res, fq_con);
652  fq_nmod_poly_factor (res, leadingCoeff, FLINTF, fq_con);
654  F.insert (CFFactor (Lc (f), 1));
655 
656  fq_nmod_poly_factor_clear (res, fq_con);
657  fq_nmod_poly_clear (FLINTF, fq_con);
658  nmod_poly_clear (FLINTmipo);
659  nmod_poly_clear (leadingCoeff);
661 #else
662  // First all cases with characteristic !=2
663  // set remainder
665  {
667  zz_p::init(getCharacteristic());
668  }
669 
670  // set minimal polynomial in NTL
671  zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
672  zz_pE::init (minPo);
673 
674  // convert to NTL
675  zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
676  zz_pE leadcoeff= LeadCoeff(f1);
677 
678  //make monic
679  f1=f1 / leadcoeff;
680 
681  // factorize using NTL
682  vec_pair_zz_pEX_long factors;
683  CanZass(factors,f1);
684 
685  // return converted result
686  F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
687 #endif
688  }
689  else if (/*getCharacteristic()*/ch==2)
690  {
691  // special case : GF2
692 
693  // remainder is two ==> nothing to do
694 
695  // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
696  GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
697  GF2E::init (minPo);
698 
699  // convert to NTL again using the faster conversion routines
700  GF2EX f1;
701  if (isPurePoly(f))
702  {
703  GF2X f_tmp=convertFacCF2NTLGF2X(f);
704  f1=to_GF2EX(f_tmp);
705  }
706  else
707  f1=convertFacCF2NTLGF2EX(f,minPo);
708 
709  // make monic (in Z/2(a))
710  GF2E f1_coef=LeadCoeff(f1);
711  MakeMonic(f1);
712 
713  // factorize using NTL
714  vec_pair_GF2EX_long factors;
715  CanZass(factors,f1);
716 
717  // return converted result
718  F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
719  }
720 #else
721  factoryError ("univariate factorization depends on NTL(missing)");
722  return CFFList (CFFactor (f, 1));
723 #endif //HAVE_NTL
724  }
725  else if (ch>0)
726  {
727  #ifdef HAVE_NTL
728  F= FqFactorize (f, alpha);
729  #else
730  ASSERT( f.isUnivariate(), "multivariate factorization depends on NTL(missing)" );
731  factoryError ("multivariate factorization depends on NTL(missing)");
732  return CFFList (CFFactor (f, 1));
733  #endif
734 
735  }
736  else if (f.isUnivariate() && (ch == 0)) // Q(a)[x]
737  {
738  F= AlgExtFactorize (f, alpha);
739  }
740  else //Q(a)[x1,...,xn]
741  {
742 #ifdef HAVE_NTL
743  F= ratFactorize (f, alpha);
744 #else
745  ASSERT( f.isUnivariate(), "multivariate factorization depends on NTL(missing)" );
746  factoryError ("multivariate factorization depends on NTL(missing)");
747  return CFFList (CFFactor (f, 1));
748 #endif
749  }
750  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
751  return F;
752 }

◆ factoryError_intern()

void factoryError_intern ( const char *  s)

Definition at line 70 of file cf_util.cc.

71 {
72  fputs(s,stderr);
73  abort();
74 }

◆ factoryrandom()

int factoryrandom ( int  n)

random integers with abs less than n

Definition at line 168 of file cf_random.cc.

169 {
170  if ( n == 0 )
171  return (int)ranGen.generate();
172  else
173  return ranGen.generate() % n;
174 }

◆ factoryseed()

void factoryseed ( int  s)

random seed initializer

Definition at line 176 of file cf_random.cc.

177 {
178  ranGen.seed( s );
179 }

◆ Farey()

Farey rational reconstruction.

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

Definition at line 197 of file cf_chinese.cc.

198 {
199  int is_rat=isOn(SW_RATIONAL);
200  Off(SW_RATIONAL);
201  Variable x = f.mvar();
202  CanonicalForm result = 0;
203  CanonicalForm c;
204  CFIterator i;
205 #ifdef HAVE_NTL
206  ZZ NTLq= convertFacCF2NTLZZ (q);
207  ZZ bound;
208  SqrRoot (bound, NTLq/2);
209 #endif
210  for ( i = f; i.hasTerms(); i++ )
211  {
212  c = i.coeff();
213  if ( c.inCoeffDomain())
214  {
215 #ifdef HAVE_NTL
216  if (c.inZ())
217  {
218  ZZ NTLc= convertFacCF2NTLZZ (c);
219  bool lessZero= (sign (NTLc) == -1);
220  if (lessZero)
221  NTL::negate (NTLc, NTLc);
222  ZZ NTLnum, NTLden;
223  if (ReconstructRational (NTLnum, NTLden, NTLc, NTLq, bound, bound))
224  {
225  if (lessZero)
226  NTL::negate (NTLnum, NTLnum);
227  CanonicalForm num= convertNTLZZX2CF (to_ZZX (NTLnum), Variable (1));
228  CanonicalForm den= convertNTLZZX2CF (to_ZZX (NTLden), Variable (1));
229  On (SW_RATIONAL);
230  result += power (x, i.exp())*(num/den);
231  Off (SW_RATIONAL);
232  }
233  }
234  else
235  result += power( x, i.exp() ) * Farey(c,q);
236 #else
237  if (c.inZ())
238  result += power( x, i.exp() ) * Farey_n(c,q);
239  else
240  result += power( x, i.exp() ) * Farey(c,q);
241 #endif
242  }
243  else
244  result += power( x, i.exp() ) * Farey(c,q);
245  }
246  if (is_rat) On(SW_RATIONAL);
247  return result;
248 }

◆ 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 338 of file cf_algorithm.cc.

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

◆ 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 388 of file cf_algorithm.cc.

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

◆ gcd()

Definition at line 262 of file cf_gcd.cc.

263 {
264  bool b = f.isZero();
265  if ( b || g.isZero() )
266  {
267  if ( b )
268  return abs( g );
269  else
270  return abs( f );
271  }
272  if ( f.inPolyDomain() || g.inPolyDomain() )
273  {
274  if ( f.mvar() != g.mvar() )
275  {
276  if ( f.mvar() > g.mvar() )
277  return cf_content( f, g );
278  else
279  return cf_content( g, f );
280  }
281  if (isOn(SW_USE_QGCD))
282  {
283  Variable m;
284  if (
285  (getCharacteristic() == 0) &&
287  )
288  {
289  bool on_rational = isOn(SW_RATIONAL);
290  CanonicalForm r=QGCD(f,g);
291  On(SW_RATIONAL);
292  CanonicalForm cdF = bCommonDen( r );
293  if (!on_rational) Off(SW_RATIONAL);
294  return cdF*r;
295  }
296  }
297 
298  if ( f.inExtension() && getReduce( f.mvar() ) )
299  return CanonicalForm(1);
300  else
301  {
302  if ( fdivides( f, g ) )
303  return abs( f );
304  else if ( fdivides( g, f ) )
305  return abs( g );
306  if ( !( getCharacteristic() == 0 && isOn( SW_RATIONAL ) ) )
307  {
308  CanonicalForm d;
309  d = gcd_poly( f, g );
310  return abs( d );
311  }
312  else
313  {
314  CanonicalForm cdF = bCommonDen( f );
315  CanonicalForm cdG = bCommonDen( g );
316  Off( SW_RATIONAL );
317  CanonicalForm l = lcm( cdF, cdG );
318  On( SW_RATIONAL );
319  CanonicalForm F = f * l, G = g * l;
320  Off( SW_RATIONAL );
321  l = gcd_poly( F, G );
322  On( SW_RATIONAL );
323  return abs( l );
324  }
325  }
326  }
327  if ( f.inBaseDomain() && g.inBaseDomain() )
328  return bgcd( f, g );
329  else
330  return 1;
331 }

◆ gcd_poly()

CanonicalForm gcd_poly ( const CanonicalForm f,
const CanonicalForm g 
)

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 94 of file cf_gcd.cc.

95 {
96  CanonicalForm fc, gc, d1;
97  bool fc_isUnivariate=f.isUnivariate();
98  bool gc_isUnivariate=g.isUnivariate();
99  bool fc_and_gc_Univariate=fc_isUnivariate && gc_isUnivariate;
100  fc = f;
101  gc = g;
102  if ( getCharacteristic() != 0 )
103  {
104  #ifdef HAVE_NTL
105  if ((!fc_and_gc_Univariate) && (isOn( SW_USE_EZGCD_P )))
106  {
107  fc= EZGCD_P (fc, gc);
108  }
109  else if (isOn(SW_USE_FF_MOD_GCD) && !fc_and_gc_Univariate)
110  {
111  Variable a;
112  if (hasFirstAlgVar (fc, a) || hasFirstAlgVar (gc, a))
113  fc=modGCDFq (fc, gc, a);
115  fc=modGCDGF (fc, gc);
116  else
117  fc=modGCDFp (fc, gc);
118  }
119  else
120  #endif
121  fc = subResGCD_p( fc, gc );
122  }
123  else if (!fc_and_gc_Univariate)
124  {
125  if ( isOn( SW_USE_EZGCD ) )
126  fc= ezgcd (fc, gc);
127 #ifdef HAVE_NTL
128  else if (isOn(SW_USE_CHINREM_GCD))
129  fc = modGCDZ( fc, gc);
130 #endif
131  else
132  {
133  fc = subResGCD_0( fc, gc );
134  }
135  }
136  else
137  {
138  fc = subResGCD_0( fc, gc );
139  }
140  if ( d1.degree() > 0 )
141  fc *= d1;
142  return fc;
143 }

◆ 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 245 of file cf_factor.cc.

246 {
247  ASSERT( ( ! f.inCoeffDomain() ), "no constants" );
248  int max=0, maxlevel=0, n=level(f);
249  for ( int i=1; i<=n; i++ )
250  {
251  if (degree(f,Variable(i)) >= max)
252  {
253  max= degree(f,Variable(i)); maxlevel= i;
254  }
255  }
256  return Variable(maxlevel);
257 }

◆ get_Terms()

CFList get_Terms ( const CanonicalForm f)

Definition at line 274 of file cf_factor.cc.

274  {
275  CFList result,dummy,dummy2;
276  CFIterator i;
278 
279  if ( getNumVars(f) == 0 ) result.append(f);
280  else{
281  Variable _x(level(f));
282  for ( i=f; i.hasTerms(); i++ ){
283  getTerms(i.coeff(), 1, dummy);
284  for ( j=dummy; j.hasItem(); j++ )
285  result.append(j.getItem() * power(_x, i.exp()));
286 
287  dummy= dummy2; // have to initalize new
288  }
289  }
290  return result;
291 }

◆ getCharacteristic()

int getCharacteristic ( )

Definition at line 51 of file cf_char.cc.

52 {
53  return theCharacteristic;
54 }

◆ getDefaultExtName()

char getDefaultExtName ( )

Definition at line 249 of file variable.cc.

250 {
251  return default_name_ext;
252 }

◆ getDefaultVarName()

char getDefaultVarName ( )

Definition at line 244 of file variable.cc.

245 {
246  return default_name;
247 }

◆ getGFDegree()

int getGFDegree ( )

Definition at line 56 of file cf_char.cc.

57 {
58  //ASSERT( theDegree > 0, "not in GF(q)" );
59  return theDegree;
60 }

◆ getGFGenerator()

CanonicalForm getGFGenerator ( )

Definition at line 62 of file cf_char.cc.

63 {
64  ASSERT( theDegree > 1, "not in GF(q)" );
65  return int2imm_gf( 1 );
66 }

◆ 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" );
211 }

◆ 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 }

◆ 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 264 of file cf_factor.cc.

265 {
266  if ( getNumVars(f) == 0 ) result.append(f*t);
267  else{
268  Variable x(level(f));
269  for ( CFIterator i=f; i.hasTerms(); i++ )
270  getTerms( i.coeff(), t*power(x,i.exp()), result);
271  }
272 }

◆ getVars()

CanonicalForm getVars ( const CanonicalForm f)

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
368  CanonicalForm result = 1;
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 248 of file gfops.cc.

249 {
250  if ( gf_iszero( a ) )
251  return 0;
252  else
253  {
254  // starting from z^0=1, step through the table
255  // counting the steps until we hit z^a or z^0
256  // again. since we are working in char(p), the
257  // latter is guaranteed to be fulfilled.
258  int i = 0, ff = 1;
259  do
260  {
261  if ( i == a )
262  return ff;
263  ff++;
264  i = gf_table[i];
265  } while ( i != 0 );
266  return -1;
267  }
268 }

◆ gf_gf2ff() [2/2]

long gf_gf2ff ( long  a)

Definition at line 226 of file gfops.cc.

227 {
228  if ( gf_iszero( a ) )
229  return 0;
230  else
231  {
232  // starting from z^0=1, step through the table
233  // counting the steps until we hit z^a or z^0
234  // again. since we are working in char(p), the
235  // latter is guaranteed to be fulfilled.
236  long i = 0, ff = 1;
237  do
238  {
239  if ( i == a )
240  return ff;
241  ff++;
242  i = gf_table[i];
243  } while ( i != 0 );
244  return -1;
245  }
246 }

◆ gf_isff() [1/2]

bool gf_isff ( int  a)

Definition at line 281 of file gfops.cc.

282 {
283  if ( gf_iszero( a ) )
284  return true;
285  else
286  {
287  // z^a in GF(p) iff (z^a)^p-1=1
288  return gf_isone( gf_power( a, gf_p - 1 ) );
289  }
290 }

◆ gf_isff() [2/2]

bool gf_isff ( long  a)

Definition at line 270 of file gfops.cc.

271 {
272  if ( gf_iszero( a ) )
273  return true;
274  else
275  {
276  // z^a in GF(p) iff (z^a)^p-1=1
277  return gf_isone( gf_power( a, gf_p - 1 ) );
278  }
279 }

◆ 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 }

◆ gmp_denominator()

void 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 }

◆ gmp_numerator()

void 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 }

◆ hasFirstAlgVar()

bool hasFirstAlgVar ( const CanonicalForm f,
Variable a 
)

check if poly f contains an algebraic variable a

Definition at line 665 of file cf_ops.cc.

666 {
667  if( f.inBaseDomain() ) // f has NO alg. variable
668  return false;
669  if( f.level()<0 ) // f has only alg. vars, so take the first one
670  {
671  a = f.mvar();
672  return true;
673  }
674  for(CFIterator i=f; i.hasTerms(); i++)
675  if( hasFirstAlgVar( i.coeff(), a ))
676  return true; // 'a' is already set
677  return false;
678 }

◆ 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 490 of file factory.h.

491 {
492  if ( f.level() > 0 )
493  return power( f.mvar(), f.degree() ) * f.LC();
494  else
495  return f;
496 }

◆ headdegree()

int headdegree ( const CanonicalForm f)
inline

Definition at line 499 of file factory.h.

499 { return totaldegree( head( f ) ); }

◆ homogenize() [1/2]

CanonicalForm homogenize ( const CanonicalForm f,
const Variable x 
)

homogenize homogenizes f with Variable x

Definition at line 298 of file cf_factor.cc.

299 {
300 #if 0
301  int maxdeg=totaldegree(f), deg;
302  CFIterator i;
303  CanonicalForm elem, result(0);
304 
305  for (i=f; i.hasTerms(); i++)
306  {
307  elem= i.coeff()*power(f.mvar(),i.exp());
308  deg = totaldegree(elem);
309  if ( deg < maxdeg )
310  result += elem * power(x,maxdeg-deg);
311  else
312  result+=elem;
313  }
314  return result;
315 #else
316  CFList Newlist, Termlist= get_Terms(f);
317  int maxdeg=totaldegree(f), deg;
319  CanonicalForm elem, result(0);
320 
321  for (i=Termlist; i.hasItem(); i++)
322  {
323  elem= i.getItem();
324  deg = totaldegree(elem);
325  if ( deg < maxdeg )
326  Newlist.append(elem * power(x,maxdeg-deg));
327  else
328  Newlist.append(elem);
329  }
330  for (i=Newlist; i.hasItem(); i++) // rebuild
331  result += i.getItem();
332 
333  return result;
334 #endif
335 }

◆ homogenize() [2/2]

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

Definition at line 338 of file cf_factor.cc.

339 {
340 #if 0
341  int maxdeg=totaldegree(f), deg;
342  CFIterator i;
343  CanonicalForm elem, result(0);
344 
345  for (i=f; i.hasTerms(); i++)
346  {
347  elem= i.coeff()*power(f.mvar(),i.exp());
348  deg = totaldegree(elem);
349  if ( deg < maxdeg )
350  result += elem * power(x,maxdeg-deg);
351  else
352  result+=elem;
353  }
354  return result;
355 #else
356  CFList Newlist, Termlist= get_Terms(f);
357  int maxdeg=totaldegree(f), deg;
359  CanonicalForm elem, result(0);
360 
361  for (i=Termlist; i.hasItem(); i++)
362  {
363  elem= i.getItem();
364  deg = totaldegree(elem,v1,v2);
365  if ( deg < maxdeg )
366  Newlist.append(elem * power(x,maxdeg-deg));
367  else
368  Newlist.append(elem);
369  }
370  for (i=Newlist; i.hasItem(); i++) // rebuild
371  result += i.getItem();
372 
373  return result;
374 #endif
375 }

◆ icontent()

CanonicalForm icontent ( const CanonicalForm f)

CanonicalForm icontent ( const CanonicalForm & f )

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

Definition at line 71 of file cf_gcd.cc.

72 {
73  return icontent( f, 0 );
74 }

◆ igcd()

int igcd ( int  a,
int  b 
)

Definition at line 51 of file cf_util.cc.

52 {
53  if ( a < 0 ) a = -a;
54  if ( b < 0 ) b = -b;
55 
56  int c;
57 
58  while ( b != 0 )
59  {
60  c = a % b;
61  a = b;
62  b = c;
63  }
64  return a;
65 }

◆ ilog2()

int ilog2 ( const CanonicalForm a)
inline

Definition at line 482 of file factory.h.

482 { return a.ilog2(); }

◆ ipower()

int 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 25 of file cf_util.cc.

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

◆ irrCharSeries()

ListCFList 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 }

◆ is_imm()

int is_imm ( const InternalCF *const  ptr)
inline

Definition at line 206 of file factory.h.

207 {
208  // returns 0 if ptr is not immediate
209  return ( ((int)((intptr_t)ptr)) & 3 );
210 }

◆ isOn()

bool isOn ( int  )

switches

Definition at line 1912 of file canonicalform.cc.

1913 {
1914  return cf_glob_switches.isOn( sw );
1915 }

◆ isPurePoly()

bool isPurePoly ( const CanonicalForm f)

Definition at line 229 of file cf_factor.cc.

230 {
231  if (f.level()<=0) return false;
232  for (CFIterator i=f;i.hasTerms();i++)
233  {
234  if (!(i.coeff().inBaseDomain())) return false;
235  }
236  return true;
237 }

◆ isPurePoly_m()

bool isPurePoly_m ( const CanonicalForm f)

Definition at line 219 of file cf_factor.cc.

220 {
221  if (f.inBaseDomain()) return true;
222  if (f.level()<0) return false;
223  for (CFIterator i=f;i.hasTerms();i++)
224  {
225  if (!isPurePoly_m(i.coeff())) return false;
226  }
227  return true;
228 }

◆ lc()

CanonicalForm lc ( const CanonicalForm f)
inline

Definition at line 434 of file factory.h.

434 { return f.lc(); }

◆ Lc()

CanonicalForm Lc ( const CanonicalForm f)
inline

Definition at line 437 of file factory.h.

437 { return f.Lc(); }

◆ LC() [1/2]

CanonicalForm LC ( const CanonicalForm f)
inline

Definition at line 440 of file factory.h.

440 { return f.LC(); }

◆ LC() [2/2]

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

Definition at line 443 of file factory.h.

443 { return f.LC( v ); }

◆ 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 343 of file cf_gcd.cc.

344 {
345  if ( f.isZero() || g.isZero() )
346  return 0;
347  else
348  return ( f / gcd( f, g ) ) * g;
349 }

◆ 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 683 of file cf_ops.cc.

684 {
685  ASSERT (n >= 0, "cannot left shift by negative number");
686  if (F.inBaseDomain())
687  return F;
688  if (n == 0)
689  return F;
690  Variable x=F.mvar();
692  for (CFIterator i= F; i.hasTerms(); i++)
693  result += i.coeff()*power (x, i.exp()*n);
694  return result;
695 }

◆ level() [1/2]

int level ( const CanonicalForm f)
inline

Definition at line 461 of file factory.h.

461 { return f.level(); }

◆ level() [2/2]

int level ( const Variable v)
inline

Definition at line 179 of file factory.h.

179 { 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 );
139  setCharacteristic( p );
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
150  setCharacteristic( 0 );
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 );
164  setCharacteristic( p );
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
174  setCharacteristic( 0 );
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 }

◆ make_cf() [1/2]

CanonicalForm make_cf ( const mpz_ptr  n)

Definition at line 66 of file singext.cc.

67 {
68  return CanonicalForm( CFFactory::basic( n ) );
69 }

◆ make_cf() [2/2]

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

Definition at line 71 of file singext.cc.

72 {
73  return CanonicalForm( CFFactory::rational( n, d, normalize ) );
74 }

◆ 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  {
446  CanonicalForm result = 0;
447  CFIterator i;
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 }

◆ mapinto()

CanonicalForm mapinto ( const CanonicalForm f)
inline

Definition at line 485 of file factory.h.

485 { return f.mapinto(); }

◆ maxNorm()

CanonicalForm maxNorm ( const CanonicalForm f)

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 534 of file cf_algorithm.cc.

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

◆ mod()

See also
div(), operator%(), CanonicalForm::operator %=()

Definition at line 564 of file cf_inline.cc.

565 {
566  CanonicalForm result( lhs );
567  result.mod( rhs );
568  return result;
569 }

◆ 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 
299  initial= factorsOfInitials (CSet);
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 }

◆ mvar()

Variable mvar ( const CanonicalForm f)
inline

Definition at line 464 of file factory.h.

464 { return f.mvar(); }

◆ name()

char name ( const Variable v)
inline

Definition at line 180 of file factory.h.

180 { 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 }

◆ neworderint()

IntList 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 467 of file factory.h.

467 { return f.num(); }

◆ Off()

void Off ( int  )

switches

Definition at line 1905 of file canonicalform.cc.

1906 {
1907  cf_glob_switches.Off( sw );
1908 }

◆ On()

void On ( int  )

switches

Definition at line 1898 of file canonicalform.cc.

1899 {
1900  cf_glob_switches.On( sw );
1901 }

◆ operator%()

See also
CanonicalForm::operator %=()

Definition at line 540 of file cf_inline.cc.

541 {
542  CanonicalForm result( lhs );
543  result %= rhs;
544  return result;
545 }

◆ operator*()

CF_INLINE CanonicalForm operator* ( const CanonicalForm lhs,
const CanonicalForm rhs 
)
See also
CanonicalForm::operator *=()

Definition at line 517 of file cf_inline.cc.

518 {
519  CanonicalForm result( lhs );
520  result *= rhs;
521  return result;
522 }

◆ operator+()

CF_INLINE CanonicalForm operator+ ( const CanonicalForm lhs,
const CanonicalForm rhs 
)

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 496 of file cf_inline.cc.

497 {
498  CanonicalForm result( lhs );
499  result += rhs;
500  return result;
501 }

◆ operator-()

Definition at line 505 of file cf_inline.cc.

506 {
507  CanonicalForm result( lhs );
508  result -= rhs;
509  return result;
510 }

◆ operator/()

See also
CanonicalForm::operator /=()

Definition at line 529 of file cf_inline.cc.

530 {
531  CanonicalForm result( lhs );
532  result /= rhs;
533  return result;
534 }

◆ power() [1/2]

CanonicalForm power ( const CanonicalForm f,
int  n 
)

exponentiation

Definition at line 1837 of file canonicalform.cc.

1838 {
1839  ASSERT( n >= 0, "illegal exponent" );
1840  if ( f.isZero() )
1841  return CanonicalForm(0L);
1842  else if ( f.isOne() )
1843  return f;
1844  else if ( f == -1 )
1845  {
1846  if ( n % 2 == 0 )
1847  return CanonicalForm(1L);
1848  else
1849  return CanonicalForm(-1L);
1850  }
1851  else if ( n == 0 )
1852  return CanonicalForm(1L);
1853 
1854  //else if (f.inGF())
1855  //{
1856  //}
1857  else
1858  {
1859  CanonicalForm g,h;
1860  h=f;
1861  while(n%2==0)
1862  {
1863  h*=h;
1864  n/=2;
1865  }
1866  g=h;
1867  while(1)
1868  {
1869  n/=2;
1870  if(n==0)
1871  return g;
1872  h*=h;
1873  if(n%2!=0) g*=h;
1874  }
1875  }
1876 }

◆ power() [2/2]

CanonicalForm power ( const Variable v,
int  n 
)

exponentiation

Definition at line 1880 of file canonicalform.cc.

1881 {
1882  //ASSERT( n >= 0, "illegal exponent" );
1883  if ( n == 0 )
1884  return 1;
1885  else if ( n == 1 )
1886  return v;
1887  else if (( v.level() < 0 ) && (hasMipo(v)))
1888  {
1889  CanonicalForm result( v, n-1 );
1890  return result * v;
1891  }
1892  else
1893  return CanonicalForm( v, n );
1894 }

◆ 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 253 of file cf_gcd.cc.

254 {
255  if ( f.isZero() )
256  return f;
257  else
258  return f / content( f );
259 }

◆ 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 }

◆ probIrredTest()

int 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;
66  CanonicalForm G= compress (F, 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 }

◆ prune()

void prune ( Variable alpha)

Definition at line 261 of file variable.cc.

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

◆ prune1()

void prune1 ( const Variable alpha)

Definition at line 289 of file variable.cc.

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

◆ 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 
)

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 646 of file cf_ops.cc.

647 {
648  if(f.inBaseDomain() || f.level() < M.level())
649  return f;
650  if(f.level() == M.level())
651  {
652  if(f.degree() < M.degree())
653  return f;
654  CanonicalForm tmp = mod (f, M);
655  return tmp;
656  }
657  // here: f.level() > M.level()
658  CanonicalForm result = 0;
659  for(CFIterator i=f; i.hasTerms(); i++)
660  result += reduce(i.coeff(),M) * power(f.mvar(),i.exp());
661  return result;
662 }

◆ 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 }

◆ 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 }

◆ replaceLc()

CanonicalForm replaceLc ( const CanonicalForm f,
const CanonicalForm c 
)

Definition at line 89 of file fac_util.cc.

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

◆ replacevar()

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

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 }

◆ resultant()

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

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 ) {
215  CanonicalForm swap = F;
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 }

◆ 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)
570  Off (SW_RATIONAL);
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;
586  CanonicalForm G= B;
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);
617  CanonicalForm bound= 1;
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)
625  Off (SW_RATIONAL);
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 
653  setCharacteristic (0);
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 }

◆ rootOf()

Variable 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 }

◆ setCharacteristic() [1/3]

void setCharacteristic ( int  c)

Definition at line 23 of file cf_char.cc.

24 {
25  if ( c == 0 )
26  {
27  theDegree = 0;
30  }
31  else
32  {
33  theDegree = 1;
37  if (c > 536870909) factoryError("characteristic is too large(max is 2^29)");
38  ff_setprime( c );
39  }
40 }

◆ setCharacteristic() [2/3]

void setCharacteristic ( int  c,
int  n 
)

◆ setCharacteristic() [3/3]

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

Definition at line 42 of file cf_char.cc.

43 {
44  ASSERT( c != 0 && n > 1, "illegal GF(q)" );
45  setCharacteristic( c );
46  gf_setcharacteristic( c, n, name );
47  theDegree = n;
49 }

◆ 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" );
242 }

◆ sign()

int sign ( const CanonicalForm a)
inline

Definition at line 473 of file factory.h.

473 { 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 628 of file cf_ops.cc.

629 {
630  if ( f.inCoeffDomain() )
631  return 1;
632  else
633  {
634  int result = 0;
635  CFIterator i;
636  for ( i = f; i.hasTerms(); i++ )
637  result += size( i.coeff() );
638  return result;
639  }
640 }

◆ 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  {
610  CFIterator i;
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 }

◆ sqrFree()

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

squarefree factorization

Definition at line 757 of file cf_factor.cc.

758 {
759 // ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
760  CFFList result;
761 
762  if ( getCharacteristic() == 0 )
763  result = sqrFreeZ( f );
764  else
765  {
766  Variable alpha;
767  if (hasFirstAlgVar (f, alpha))
768  result = FqSqrf( f, alpha );
769  else
770  result= FpSqrf (f);
771  }
772  if (sort)
773  {
774  CFFactor buf= result.getFirst();
775  result.removeFirst();
777  result.insert (buf);
778  }
779  return result;
780 }

◆ sqrt()

CanonicalForm sqrt ( const CanonicalForm a)
inline

Definition at line 479 of file factory.h.

479 { return a.sqrt(); }

◆ 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 );
47  CanonicalForm F, G;
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 }

◆ swapvar()

CanonicalForm swapvar ( const CanonicalForm f,
const Variable x1,
const Variable x2 
)

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  {
175  CanonicalForm result = 0;
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 }

◆ tailcoeff() [1/2]

CanonicalForm tailcoeff ( const CanonicalForm f)
inline

Definition at line 455 of file factory.h.

455 { return f.tailcoeff(); }

◆ tailcoeff() [2/2]

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

Definition at line 458 of file factory.h.

458 { return f.tailcoeff(v); }

◆ taildegree()

int taildegree ( const CanonicalForm f)
inline

Definition at line 452 of file factory.h.

452 { 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  {
531  CFIterator i;
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 }

◆ 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
569  CFIterator i;
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
580  CFIterator i;
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 454 of file cf_algorithm.cc.

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

◆ vcontent()

CanonicalForm vcontent ( const CanonicalForm f,
const Variable x 
)

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 230 of file cf_gcd.cc.

231 {
232  ASSERT( x.level() > 0, "cannot calculate vcontent with respect to algebraic variable" );
233 
234  if ( f.mvar() <= x )
235  return content( f, x );
236  else {
237  CFIterator i;
238  CanonicalForm d = 0;
239  for ( i = f; i.hasTerms() && ! d.isOne(); i++ )
240  d = gcd( d, vcontent( i.coeff(), x ) );
241  return d;
242  }
243 }

Variable Documentation

◆ factoryConfiguration

const char factoryConfiguration[]

◆ factoryError

void(* factoryError) (const char *s)

Definition at line 75 of file cf_util.cc.

◆ singular_homog_flag

int singular_homog_flag

Definition at line 377 of file cf_factor.cc.

◆ SW_RATIONAL

const int SW_RATIONAL = 0
static

set to 1 for computations over Q

Definition at line 92 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 94 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 102 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 96 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 98 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 106 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 100 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 104 of file factory.h.

test
CanonicalForm test
Definition: cfModGcd.cc:4037
hasMipo
bool hasMipo(const Variable &alpha)
Definition: variable.cc:226
nrows
int nrows
Definition: cf_linsys.cc:32
Matrix
Definition: ftmpl_matrix.h:20
ranGen
RandomGenerator ranGen
Definition: cf_random.cc:54
symmetricRemainder
static CanonicalForm symmetricRemainder(const CanonicalForm &f, const CanonicalForm &q)
Definition: cfModResultant.cc:545
fac_NTL_char
long fac_NTL_char
Definition: NTLconvert.cc:41
error
void error(const char *fmt,...)
Definition: emacs.cc:54
convertZZ2CF
CanonicalForm convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
Definition: NTLconvert.cc:489
convertnmod_poly_t2FacCF
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
Definition: FLINTconvert.cc:137
FpSqrf
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
Definition: facFqSquarefree.h:38
StoreFactors::FS2
CFList FS2
candidate factors that might get removed
Definition: cfCharSetsUtil.h:32
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
ncols
int int ncols
Definition: cf_linsys.cc:32
cmpCF
int cmpCF(const CFFactor &f, const CFFactor &g)
Definition: cf_factor.cc:379
gf_isone
bool gf_isone(int a)
Definition: gfops.h:53
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:100
isOn
bool isOn(int sw)
switches
Definition: canonicalform.cc:1912
isZero
bool isZero(const CFArray &A)
checks if entries of A are zero
Definition: facSparseHensel.h:468
lcm
CanonicalForm lcm(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:343
convertNTLvec_pair_ZZX_long2FacCFFList
CFFList convertNTLvec_pair_ZZX_long2FacCFFList(const vec_pair_ZZX_long &e, const ZZ &multi, const Variable &x)
NAME: convertNTLvec_pair_ZZX_long2FacCFFList.
Definition: NTLconvert.cc:747
j
int j
Definition: facHensel.cc:105
psr
CanonicalForm psr(const CanonicalForm &rr, const CanonicalForm &vv, const Variable &x)
CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
Definition: cf_algorithm.cc:117
contract
ListCFList contract(const ListCFList &cs)
Definition: cfCharSetsUtil.cc:925
f
FILE * f
Definition: checklibs.c:9
singular_homog_flag
int singular_homog_flag
Definition: cf_factor.cc:377
isPurePoly
bool isPurePoly(const CanonicalForm &f)
Definition: cf_factor.cc:229
k
int k
Definition: cfEzgcd.cc:92
default_name
static char default_name
Definition: variable.cc:44
icontent
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:71
getTerms
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
Definition: cf_factor.cc:264
numZeros
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
Definition: facIrredTest.cc:24
CFIterator
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
x
Variable x
Definition: cfModGcd.cc:4023
CFSwitches::Off
void Off(int s)
switch 's' off
Definition: cf_switches.h:53
DEBOUTLN
#define DEBOUTLN(stream, objects)
Definition: debug.h:49
Prem
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
Definition: cfCharSetsUtil.cc:616
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
convertNTLvec_pair_zzpX_long2FacCFFList
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p multi, const Variable &x)
Definition: NTLconvert.cc:392
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
gf_power
int gf_power(int a, int n)
Definition: gfops.h:222
diff
static gmp_float * diff
Definition: mpr_complex.cc:45
result
return result
Definition: facAbsBiFact.cc:76
factorize
CFFList factorize(const CanonicalForm &f, bool issqrfree)
factorization over or
Definition: cf_factor.cc:390
isInseparable
bool isInseparable(const CFList &Astar)
Definition: facAlgFuncUtil.cc:522
subResGCD_0
CanonicalForm subResGCD_0(const CanonicalForm &f, const CanonicalForm &g)
subresultant GCD over Z.
Definition: cfSubResGcd.cc:165
theCharacteristic
static int theCharacteristic
Definition: cf_char.cc:20
RationalDomain
#define RationalDomain
Definition: cf_defs.h:24
nmod_poly_clear
nmod_poly_clear(FLINTmipo)
StoreFactors
class to store factors that get removed during char set computation
Definition: cfCharSetsUtil.h:28
CanonicalForm::inBaseDomain
bool inBaseDomain() const
Definition: canonicalform.cc:101
swapvar_rec
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
FqFactorize
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFqFactorize.h:184
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: cfCharSets.cc:150
icontent
static CanonicalForm icontent(const CanonicalForm &f, const CanonicalForm &c)
static CanonicalForm icontent ( const CanonicalForm & f, const CanonicalForm & c )
Definition: cf_gcd.cc:46
degrees
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:493
FqSqrf
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
Definition: facFqSquarefree.h:77
irredAS
static CFList irredAS(CFList &AS, int &indexRed, CanonicalForm &reducible)
Definition: cfCharSets.cc:507
DELETE_ARRAY
#define DELETE_ARRAY(P)
Definition: cf_defs.h:49
homogenize
CanonicalForm homogenize(const CanonicalForm &f, const Variable &x)
homogenize homogenizes f with Variable x
Definition: cf_factor.cc:298
ListCFList
List< CFList > ListCFList
Definition: canonicalform.h:392
fq_con
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
num
CanonicalForm num(const CanonicalForm &f)
Definition: canonicalform.h:330
prod
fq_nmod_poly_t prod
Definition: facHensel.cc:95
vcontent
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:230
CFFactory::gettype
static int gettype()
Definition: cf_factory.h:28
FpSqrfFactorize
CFList FpSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over
Definition: facFqFactorize.h:47
varsInAs
Varlist varsInAs(const Varlist &uord, const CFList &Astar)
Definition: facAlgFuncUtil.cc:66
ezgcd
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
Definition: cfEzgcd.cc:441
TIMING_END
#define TIMING_END(t)
Definition: timing.h:93
CFMap
class CFMap
Definition: cf_map.h:84
swapvar
CFList swapvar(const CFList &PS, const Variable &x, const Variable &y)
swapvar a whole list of CanonicalForms
Definition: cfCharSetsUtil.cc:304
DEBOUTSL
#define DEBOUTSL(stream)
Definition: debug.h:46
reduce
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:646
ratFactorize
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFactorize.h:77
internalBCommonDen
static CanonicalForm internalBCommonDen(const CanonicalForm &f)
static CanonicalForm internalBCommonDen ( const CanonicalForm & f )
Definition: cf_algorithm.cc:262
CFFList
List< CFFactor > CFFList
Definition: canonicalform.h:386
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
neworder
Varlist neworder(const CFList &PolyList)
G
const CanonicalForm & G
Definition: cfModResultant.cc:45
modCharSet
CFList modCharSet(const CFList &L, StoreFactors &StoredFactors, bool removeContents)
modified medial set
Definition: cfCharSets.cc:284
g
g
Definition: cfModGcd.cc:4031
factorsOfInitials
CFList factorsOfInitials(const CFList &L)
Definition: cfCharSetsUtil.cc:754
sign
static int sign(int x)
Definition: ring.cc:3327
level
int level(const CanonicalForm &f)
Definition: canonicalform.h:324
chin_mul_inv
static CanonicalForm chin_mul_inv(CanonicalForm a, CanonicalForm b, int ind, CFArray &inv)
Definition: cf_chinese.cc:251
get_max_degree_Variable
Variable get_max_degree_Variable(const CanonicalForm &f)
get_max_degree_Variable returns Variable with highest degree.
Definition: cf_factor.cc:245
mod
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
rootOf
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
sqrt
gmp_float sqrt(const gmp_float &a)
Definition: mpr_complex.cc:327
amp::floor
const signed long floor(const ampf< Precision > &x)
Definition: amp.h:774
CanonicalForm::sign
int sign() const
int CanonicalForm::sign () const
Definition: canonicalform.cc:1295
N
const CanonicalForm CFMap CFMap & N
Definition: cfEzgcd.cc:48
alg_gcd
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
Definition: facAlgFunc.cc:61
InternalCF
virtual class for internal CanonicalForm's
Definition: int_cf.h:41
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: cf_algorithm.cc:454
oneNorm
static CanonicalForm oneNorm(const CanonicalForm &F)
Definition: cfModResultant.cc:242
initial
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
isPurePoly
bool isPurePoly(const CanonicalForm &f)
Definition: cf_factor.cc:229
charSetViaCharSetN
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
Definition: cfCharSets.cc:246
iter
CFFListIterator iter
Definition: facAbsBiFact.cc:54
ext_entry::mipo
InternalPoly * mipo()
Definition: variable.cc:36
cf_getBigPrime
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
NUMPRIMES
#define NUMPRIMES
Definition: cf_primetab.h:10
QGCD
CanonicalForm QGCD(const CanonicalForm &F, const CanonicalForm &G)
gcd over Q(a)
Definition: cfGcdAlgExt.cc:715
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
Premb
CanonicalForm Premb(const CanonicalForm &f, const CFList &L)
pseudo remainder of f by L with faster test for remainder being zero
Definition: cfCharSetsUtil.cc:677
CanonicalForm::ilog2
int ilog2() const
int CanonicalForm::ilog2 () const
Definition: canonicalform.cc:1352
b
CanonicalForm b
Definition: cfModGcd.cc:4044
sqrFreeZ
CFFList sqrFreeZ(const CanonicalForm &a)
Definition: fac_sqrfree.cc:45
Trager
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.
Definition: facAlgFunc.cc:430
gf_table
unsigned short * gf_table
Definition: gfops.cc:54
gcd_poly
CanonicalForm gcd_poly(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:94
InternalRational::MPQNUM
static mpz_ptr MPQNUM(const InternalCF *const c)
Definition: int_rat.h:119
cf_getNumBigPrimes
int cf_getNumBigPrimes()
Definition: cf_primes.cc:45
CanonicalForm
factory's main class
Definition: canonicalform.h:77
xn
int xn
Definition: walk.cc:4448
maxNorm
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
Definition: cf_algorithm.cc:534
isSubset
bool isSubset(const CFList &PS, const CFList &Cset)
is PS a subset of Cset ?
Definition: cfCharSetsUtil.cc:461
sortCFListByLevel
void sortCFListByLevel(CFList &list)
sort in descending order of level of elements
Definition: cfCharSetsUtil.cc:428
CanonicalForm::intval
long intval() const
conversion functions
Definition: canonicalform.cc:197
degsg
int * degsg
Definition: cfEzgcd.cc:53
fillVarsRec
static void fillVarsRec(const CanonicalForm &f, int *vars)
static void fillVarsRec ( const CanonicalForm & f, int * vars )
Definition: cf_ops.cc:296
SW_USE_EZGCD
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
Definition: cf_defs.h:32
pi
#define pi
Definition: libparse.cc:1142
divrem
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
Definition: canonicalform.cc:967
InternalCF::copyObject
InternalCF * copyObject()
Definition: int_cf.h:62
convertFacCF2Fq_nmod_poly_t
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
Definition: FLINTconvert.cc:385
SW_USE_NTL_SORT
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition: cf_defs.h:36
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
GaloisFieldDomain
#define GaloisFieldDomain
Definition: cf_defs.h:22
convertNTLvec_pair_GF2X_long2FacCFFList
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
Definition: NTLconvert.cc:439
Array::min
int min() const
Definition: ftmpl_array.cc:98
i
int i
Definition: cfEzgcd.cc:125
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition: canonicalform.h:300
swapvar
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
Array
Definition: ftmpl_array.h:17
convertFacCF2nmod_poly_t
convertFacCF2nmod_poly_t(FLINTmipo, M)
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
optvalues
static void optvalues(const int *df, const int *dg, const int n, int &p1, int &pe)
Definition: cf_map.cc:296
InternalCF::levelcoeff
virtual int levelcoeff() const
Definition: int_cf.h:68
res
CanonicalForm res
Definition: facAbsFact.cc:64
convertFacCF2NTLzz_pEX
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1063
ratSqrfFactorize
CFList ratSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree multivariate polynomial over
Definition: facFactorize.h:53
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
fq_nmod_ctx_clear
fq_nmod_ctx_clear(fq_con)
Difference
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
abs
Rational abs(const Rational &a)
Definition: GMPrat.cc:439
subResChain
CFArray subResChain(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
Definition: cf_resultant.cc:42
M
#define M
Definition: sirandom.c:24
buf
int status int void * buf
Definition: si_signals.h:58
select
void select(const ListCFList &ppi, int length, ListCFList &ppi1, ListCFList &ppi2)
Definition: cfCharSetsUtil.cc:570
content
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
convertFLINTFq_nmod_poly_factor2FacCFFList
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
Definition: FLINTconvert.cc:275
Array::max
int max() const
Definition: ftmpl_array.cc:104
cd
CanonicalForm cd(bCommonDen(FF))
Definition: cfModGcd.cc:4030
absFactorizeMain
CFAFList absFactorizeMain(const CanonicalForm &G)
main absolute factorization routine, expects poly which is irreducible over Q
Definition: facAbsFact.cc:308
Array::size
int size() const
Definition: ftmpl_array.cc:92
reorder
CFList reorder(const Varlist &betterorder, const CFList &PS)
Definition: cfCharSets.cc:101
TIMING_START
TIMING_START(fac_alg_resultant)
sign
int sign(const CanonicalForm &a)
Definition: factory.h:473
lc
CanonicalForm lc(const CanonicalForm &f)
Definition: canonicalform.h:297
AlgExtFactorize
CFFList AlgExtFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a univariate polynomial over algebraic extension of Q
Definition: facAlgExt.cc:370
trivialResultant
static CanonicalForm trivialResultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
static CanonicalForm trivialResultant ( const CanonicalForm & f, const CanonicalForm & g,...
Definition: cf_resultant.cc:146
betterpivot
bool betterpivot(const CanonicalForm &oldpivot, const CanonicalForm &newpivot)
Definition: cf_linsys.cc:61
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
List::isEmpty
int isEmpty() const
Definition: ftmpl_list.cc:267
InternalPoly
factory's class for polynomials
Definition: int_poly.h:71
CFFactory::basic
static InternalCF * basic(long value)
Definition: cf_factory.cc:30
nmod_poly_init
nmod_poly_init(FLINTmipo, getCharacteristic())
chineseRemainder
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:52
degreesRec
static void degreesRec(const CanonicalForm &f, int *degs)
static void degreesRec ( const CanonicalForm & f, int * degs )
Definition: cf_ops.cc:463
h
static Poly * h
Definition: janet.cc:972
tryDivremt
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
Definition: canonicalform.cc:1043
setCharacteristic
void setCharacteristic(int c)
Definition: cf_char.cc:23
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
detbound
CanonicalForm detbound(const CFMatrix &M, int rows)
Definition: cf_linsys.cc:486
LcF
CanonicalForm LcF
Definition: facAbsBiFact.cc:51
max
static int max(int a, int b)
Definition: fast_mult.cc:264
modGCDFq
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:467
StoreFactors::FS1
CFList FS1
factors that were removed
Definition: cfCharSetsUtil.h:31
convertNTLvec_pair_zzpEX_long2FacCFFList
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &multi, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:865
smallprimes
static const int smallprimes[]
Definition: cf_primetab.h:12
AFactor
Definition: ftmpl_afactor.h:17
DEBINCLEVEL
#define DEBINCLEVEL(stream, msg)
Definition: debug.h:44
prune
void prune(Variable &alpha)
Definition: variable.cc:261
EZGCD_P
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:815
removeFactors
void removeFactors(CanonicalForm &r, StoreFactors &StoredFactors, CFList &removedFactors)
Definition: cfCharSetsUtil.cc:822
chineseRemainder
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:52
pivot
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].
Definition: linearAlgebra.cc:68
DEBDECLEVEL
#define DEBDECLEVEL(stream, msg)
Definition: debug.h:45
convertFacCFMatrix2NTLmat_ZZ
mat_ZZ * convertFacCFMatrix2NTLmat_ZZ(const CFMatrix &m)
Definition: NTLconvert.cc:1137
SW_USE_CHINREM_GCD
static const int SW_USE_CHINREM_GCD
set to 1 to use modular gcd over Z
Definition: cf_defs.h:38
determinant
CanonicalForm determinant(const CFMatrix &M, int n)
Definition: cf_linsys.cc:222
adjoin
ListCFList adjoin(const CFList &is, const CFList &qs, const ListCFList &qh)
Definition: cfCharSetsUtil.cc:495
CFAFactor
AFactor< CanonicalForm > CFAFactor
Definition: canonicalform.h:382
FiniteFieldDomain
#define FiniteFieldDomain
Definition: cf_defs.h:23
gf_p
int gf_p
Definition: gfops.cc:48
Variable::level
int level() const
Definition: factory.h:134
pp
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:253
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition: facAlgFuncUtil.cc:32
factorize
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
get_Terms
CFList get_Terms(const CanonicalForm &f)
Definition: cf_factor.cc:274
CanonicalForm::sqrt
CanonicalForm sqrt() const
CanonicalForm CanonicalForm::sqrt () const.
Definition: canonicalform.cc:1318
SW_USE_FF_MOD_GCD
static const int SW_USE_FF_MOD_GCD
set to 1 to use modular GCD over F_q
Definition: cf_defs.h:42
gf_setcharacteristic
void gf_setcharacteristic(int p, int n, char name)
Definition: gfops.cc:219
CFFactory::rational
static InternalCF * rational(long num, long den)
Definition: cf_factory.cc:222
den
CanonicalForm den(const CanonicalForm &f)
Definition: canonicalform.h:333
sortCFFList
CFFList sortCFFList(CFFList &F)
Definition: fac_sqrfree.cc:21
convertFacCF2NTLZZX
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:685
var_names_ext
static char * var_names_ext
Definition: variable.cc:43
ext_entry
Definition: variable.cc:18
convertFLINTnmod_poly_factor2FacCFFList
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
Definition: FLINTconvert.cc:255
content
CanonicalForm content(const CanonicalForm &f)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
inverseERF
double inverseERF(double d)
Definition: facIrredTest.cc:42
sort
void sort(CFArray &A, int l=0)
quick sort A
Definition: facSparseHensel.h:114
ListIterator::hasItem
int hasItem()
Definition: ftmpl_list.cc:439
head
CanonicalForm head(const CanonicalForm &f)
Definition: factory.h:490
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_algorithm.cc:338
beta
Variable beta
Definition: facAbsFact.cc:99
CFFactory::settype
static void settype(int type)
Definition: cf_factory.h:29
sv_x2
static Variable sv_x2
Definition: cf_ops.cc:43
theDegree
static int theDegree
Definition: cf_char.cc:21
subResGCD_p
CanonicalForm subResGCD_p(const CanonicalForm &f, const CanonicalForm &g)
subresultant GCD over finite fields. In case things become too dense we switch to a modular algorithm
Definition: cfSubResGcd.cc:12
gf_iszero
bool gf_iszero(int a)
Definition: gfops.h:43
Off
void Off(int sw)
switches
Definition: canonicalform.cc:1905
conv2mipo
static CanonicalForm conv2mipo(const CanonicalForm &mipo, const Variable &alpha)
Definition: variable.cc:154
List::removeFirst
void removeFirst()
Definition: ftmpl_list.cc:287
divremt
bool divremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
Definition: canonicalform.cc:1001
fq_nmod_ctx_init_modulus
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
bigprimes
static const int bigprimes[]
Definition: cf_primetab.h:601
exp
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
Factor
Definition: ftmpl_factor.h:18
CanonicalForm::inZ
bool inZ() const
predicates
Definition: canonicalform.cc:66
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
sortListCFList
void sortListCFList(ListCFList &list)
sort in descending order of length of elements
Definition: cfCharSetsUtil.cc:396
convertFacCF2Fmpq_poly_t
void convertFacCF2Fmpq_poly_t(fmpq_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomials over Q to fmpq_poly_t
Definition: FLINTconvert.cc:238
InternalCF::deleteObject
int deleteObject()
Definition: int_cf.h:61
LEVELBASE
#define LEVELBASE
Definition: cf_defs.h:16
modGCDFp
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition: cfModGcd.cc:1206
SteelTrager
CFFList SteelTrager(const CanonicalForm &f, const CFList &AS)
algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate...
Definition: facAlgFunc.cc:759
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
Definition: cf_algorithm.cc:293
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
factoryError
void(* factoryError)(const char *s)
Definition: cf_util.cc:75
divide
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
Definition: facAlgFuncUtil.cc:500
List::length
int length() const
Definition: ftmpl_list.cc:273
factor
CanonicalForm factor
Definition: facAbsFact.cc:101
convertNTLmat_ZZ2FacCFMatrix
CFMatrix * convertNTLmat_ZZ2FacCFMatrix(const mat_ZZ &m)
Definition: NTLconvert.cc:1152
convertFacCF2NTLGF2EX
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
Definition: NTLconvert.cc:1006
uniGcd
CFList uniGcd(const CFList &L)
Definition: cfCharSetsUtil.cc:720
setCharacteristic
void setCharacteristic(int c)
Definition: cf_char.cc:23
InternalInteger::MPI
static mpz_ptr MPI(const InternalCF *const c)
MPI() - return underlying mpz_t of ā€˜c’.
Definition: int_int.h:232
TIMING_END_AND_PRINT
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
normalize
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition: syz3.cc:1026
degsf
int * degsf
Definition: cfEzgcd.cc:52
FpFactorize
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFqFactorize.h:101
Variable
factory's class for variables
Definition: factory.h:117
ListIterator::getItem
T & getItem() const
Definition: ftmpl_list.cc:431
CanonicalForm::degree
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
Definition: canonicalform.cc:381
convertFmpq_poly_t2FacCF
CanonicalForm convertFmpq_poly_t2FacCF(const fmpq_poly_t p, const Variable &x)
conversion of a FLINT poly over Q to CanonicalForm
Definition: FLINTconvert.cc:212
SW_USE_EZGCD_P
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition: cf_defs.h:34
bound
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
cf_getSmallPrime
int cf_getSmallPrime(int i)
Definition: cf_primes.cc:28
NUMBIGPRIMES
#define NUMBIGPRIMES
Definition: cf_primetab.h:9
B
b *CanonicalForm B
Definition: facBivar.cc:52
is_imm
int is_imm(const InternalCF *const ptr)
Definition: canonicalform.h:62
adjoinb
ListCFList adjoinb(const CFList &is, const CFList &qs, const ListCFList &qh, const CFList &cs)
Definition: cfCharSetsUtil.cc:533
getNumVars
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition: canonicalform.cc:560
cf_glob_switches
CFSwitches cf_glob_switches
CFSwitches cf_glob_switches;.
Definition: cf_switches.cc:41
totaldegree
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
Farey
CanonicalForm Farey(const CanonicalForm &f, const CanonicalForm &q)
Farey rational reconstruction.
Definition: cf_chinese.cc:197
RandomGenerator::seed
void seed(int ss)
Definition: cf_random.cc:29
LC
CanonicalForm LC(const CanonicalForm &f)
Definition: canonicalform.h:303
mapinto
CanonicalForm mapinto(const CanonicalForm &f)
Definition: canonicalform.h:348
matrix_in_Z
bool matrix_in_Z(const CFMatrix &M, int rows)
Definition: cf_linsys.cc:39
name
char name(const Variable &v)
Definition: factory.h:180
charSetViaModCharSet
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents)
characteristic set via modified medial set
Definition: cfCharSets.cc:356
gcd
CanonicalForm gcd(const CanonicalForm &f, const CanonicalForm &g)
Definition: cf_gcd.cc:262
solve
bool solve(int **extmat, int nrows, int ncols)
Definition: cf_linsys.cc:504
getDegOfExt
int getDegOfExt(IntList &degreelist, int n)
Definition: facAlgFuncUtil.cc:543
facAlgFunc2
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...
Definition: facAlgFunc.cc:905
cf_content
static CanonicalForm cf_content(const CanonicalForm &f, const CanonicalForm &g)
static CanonicalForm cf_content ( const CanonicalForm & f, const CanonicalForm & g )
Definition: cf_gcd.cc:155
pow
Rational pow(const Rational &a, int e)
Definition: GMPrat.cc:414
charSetN
CFList charSetN(const CFList &PS)
medial set
Definition: cfCharSets.cc:216
resultant
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
Definition: cf_resultant.cc:173
m
int m
Definition: cfEzgcd.cc:121
GFSqrfFactorize
CFList GFSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over GF
Definition: facFqFactorize.h:82
Variable::name
char name() const
Definition: variable.cc:122
lowestRank
CanonicalForm lowestRank(const CFList &L)
Definition: cfCharSetsUtil.cc:357
sqrFree
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:757
find
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
NULL
#define NULL
Definition: omList.c:9
determinant
int determinant(int **extmat, int n)
Definition: cf_linsys.cc:556
l
int l
Definition: cfEzgcd.cc:93
ff_big
bool ff_big
Definition: ffops.cc:16
DEBOUTENDL
#define DEBOUTENDL(stream)
Definition: debug.h:48
algextensions
static ext_entry * algextensions
Definition: variable.cc:41
ext_entry::reduce
bool & reduce()
Definition: variable.cc:38
bgcd
CanonicalForm bgcd(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g )
Definition: canonicalform.cc:1589
R
#define R
Definition: sirandom.c:26
GFFactorize
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
Definition: facFqFactorize.h:267
CanonicalForm::isUnivariate
bool isUnivariate() const
Definition: canonicalform.cc:152
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
x
const CanonicalForm CFMap CFMap const Variable & x
Definition: cfModResultant.cc:47
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
convertNTLZZX2CF
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition: NTLconvert.cc:278
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
resultantFp
CanonicalForm resultantFp(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Fp
Definition: cfModResultant.cc:349
p
int p
Definition: cfModGcd.cc:4019
mipo
CanonicalForm mipo
Definition: facAlgExt.cc:57
List
Definition: ftmpl_list.h:20
iter
CFListIterator iter
Definition: facAbsFact.cc:65
swap
#define swap(_i, _j)
swapvar_between
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
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
totaldegree
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
CFList
List< CanonicalForm > CFList
Definition: canonicalform.h:388
DEBOUT
#define DEBOUT(stream, objects)
Definition: debug.h:47
tryInvert
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
Definition: cfGcdAlgExt.cc:221
count
int status int void size_t count
Definition: si_signals.h:58
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
fuzzy_result
bool fuzzy_result
Definition: cf_linsys.cc:75
int2imm_gf
InternalCF * int2imm_gf(long i)
Definition: imm.h:106
cf_getNumSmallPrimes
int cf_getNumSmallPrimes()
Definition: cf_primes.cc:34
SW_USE_QGCD
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition: cf_defs.h:40
multiplicity
static int * multiplicity
Definition: interpolation.cc:86
Q
#define Q
Definition: sirandom.c:25
int_ptr
int * int_ptr
Definition: structs.h:56
modGCDZ
CanonicalForm modGCDZ(const CanonicalForm &FF, const CanonicalForm &GG)
modular GCD over Z
fq_nmod_poly_clear
fq_nmod_poly_clear(prod, fq_con)
convertFacCF2NTLGF2X
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Definition: NTLconvert.cc:177
getReduce
bool getReduce(const Variable &alpha)
Definition: variable.cc:232
tmp2
CFList tmp2
Definition: facFqBivar.cc:70
factorPSet
CFList factorPSet(const CFList &PS)
Definition: cfCharSetsUtil.cc:804
NUMSMALLPRIMES
#define NUMSMALLPRIMES
Definition: cf_primetab.h:8
G
static TreeM * G
Definition: janet.cc:32
default_name_ext
static char default_name_ext
Definition: variable.cc:45
CFSwitches::On
void On(int s)
switch 's' on
Definition: cf_switches.h:51
mapdomain
CanonicalForm mapdomain(const CanonicalForm &f, CanonicalForm(*mf)(const CanonicalForm &))
CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) )
Definition: cf_ops.cc:440
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
isPurePoly_m
bool isPurePoly_m(const CanonicalForm &f)
Definition: cf_factor.cc:219
CFFactor
Factor< CanonicalForm > CFFactor
Definition: canonicalform.h:385
convertFacCF2NTLZZ
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Definition: NTLconvert.cc:664
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
removeContent
void removeContent(CanonicalForm &F, CanonicalForm &cF)
Definition: cfCharSetsUtil.cc:775
convertNTLvec_pair_GF2EX_long2FacCFFList
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &multi, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
Definition: NTLconvert.cc:954
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition: cf_ops.cc:600
bextgcd
CanonicalForm bextgcd(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
CanonicalForm bextgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a,...
Definition: canonicalform.cc:1663
A
#define A
Definition: sirandom.c:23
IntegerDomain
#define IntegerDomain
Definition: cf_defs.h:25
reduce
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:646
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
merge
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
Definition: cfNewtonPolygon.cc:230
List::insert
void insert(const T &)
Definition: ftmpl_list.cc:193
InternalRational::MPQDEN
static mpz_ptr MPQDEN(const InternalCF *const c)
Definition: int_rat.h:124
On
void On(int sw)
switches
Definition: canonicalform.cc:1898
RandomGenerator::generate
int generate()
Definition: cf_random.cc:43
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition: NTLconvert.cc:248
List::sort
void sort(int(*)(const T &, const T &))
Definition: ftmpl_list.cc:339
List::getLast
T getLast() const
Definition: ftmpl_list.cc:309
fill_int_mat
static bool fill_int_mat(const CFMatrix &M, int **m, int rows)
Definition: cf_linsys.cc:203
inplaceUnion
void inplaceUnion(const ListCFList &a, ListCFList &b)
Union of a and b stored in b.
Definition: cfCharSetsUtil.cc:473
totaldegree
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
CFSwitches::isOn
bool isOn(int s) const
check if 's' is on
Definition: cf_switches.h:55
modGCDGF
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 for Computer Algebra" by Gedde...
Definition: cfModGcd.cc:860
replacevar_between
static CanonicalForm replacevar_between(const CanonicalForm &f)
replacevar_between() - replace occurences of sv_x1 in f with sv_x2.
Definition: cf_ops.cc:233
NEW_ARRAY
#define NEW_ARRAY(T, N)
Definition: cf_defs.h:48
generateMipo
CanonicalForm generateMipo(int degOfExt)
Definition: facAlgFuncUtil.cc:90
ff_setprime
void ff_setprime(const int p)
Definition: ffops.cc:19
ListIterator
Definition: ftmpl_list.h:17
sv_x1
static Variable sv_x1
static Variable sv_x1, sv_x2;
Definition: cf_ops.cc:43