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

factory.h' is the user interface to Factory. More...

`#include "factory/factoryconf.h"`
`#include "factory/globaldefs.h"`
`#include <stdint.h>`
`#include "factory/si_log2.h"`
`#include "omalloc/omalloc.h"`
`#include "omalloc/omallocClass.h"`
`#include <iostream>`
`#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 | OSTREAM std::ostream
#define | ISTREAM std::istream
#define | LEVELBASE -1000000
#define | LEVELTRANS -500000
#define | LEVELQUOT 1000000
#define | LEVELEXPR 1000001
#define | CF_INLINE
#define | CF_NO_INLINE
#define | CF_INLINE
#define | CF_NO_INLINE

## Typedefs

typedef AFactor< CanonicalForm > | CFAFactor
typedef List< CFAFactor > | CFAFList
typedef ListIterator< CFAFactor > | CFAFListIterator
typedef Factor< CanonicalForm > | CFFactor
typedef List< CFFactor > | CFFList
typedef ListIterator< CFFactor > | CFFListIterator
typedef List< CanonicalForm > | CFList
typedef ListIterator< CanonicalForm > | CFListIterator
typedef Array< CanonicalForm > | CFArray
typedef Matrix< CanonicalForm > | CFMatrix
typedef List< CFList > | ListCFList
typedef ListIterator< CFList > | ListCFListIterator
typedef List< int > | IntList
typedef ListIterator< int > | IntListIterator
typedef List< Variable > | Varlist
typedef ListIterator< Variable > | VarlistIterator
typedef Array< int > | Intarray
typedef term * | termList
typedef List< MapPair > | MPList
typedef ListIterator< MapPair > | MPListIterator

## Functions

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

## Variables

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

## Detailed Description

factory.h' is the user interface to Factory.

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

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

**/

# define OSTREAM

# define ISTREAM

/* ! NOSTREAMIO

Definition in file factory.h.

## Macro Definition Documentation

## CF_INLINE [1/2]

#define CF_INLINE

Definition at line 208 of file factory.h.

## CF_INLINE [2/2]

#define CF_INLINE

Definition at line 208 of file factory.h.

## CF_NO_INLINE [1/2]

#define CF_NO_INLINE

Definition at line 210 of file factory.h.

## CF_NO_INLINE [2/2]

#define CF_NO_INLINE

Definition at line 210 of file factory.h.

## ISTREAM

#define ISTREAM std::istream

## LEVELBASE

#define LEVELBASE -1000000

Definition at line 82 of file factory.h.

## LEVELEXPR

#define LEVELEXPR 1000001

Definition at line 85 of file factory.h.

## LEVELQUOT

#define LEVELQUOT 1000000

Definition at line 84 of file factory.h.

## LEVELTRANS

#define LEVELTRANS -500000

Definition at line 83 of file factory.h.

## OSTREAM

#define OSTREAM std::ostream

## Typedef Documentation

## CFAFactor

typedef AFactor<CanonicalForm> CFAFactor

Definition at line 530 of file factory.h.

## CFAFList

typedef List<CFAFactor> CFAFList

Definition at line 531 of file factory.h.

## CFAFListIterator

typedef ListIterator<CFAFactor> CFAFListIterator

Definition at line 532 of file factory.h.

## CFArray

typedef Array<CanonicalForm> CFArray

Definition at line 538 of file factory.h.

## CFFactor

typedef Factor<CanonicalForm> CFFactor

Definition at line 533 of file factory.h.

## CFFList

typedef List<CFFactor> CFFList

Definition at line 534 of file factory.h.

## CFFListIterator

typedef ListIterator<CFFactor> CFFListIterator

Definition at line 535 of file factory.h.

## CFList

typedef List<CanonicalForm> CFList

Definition at line 536 of file factory.h.

## CFListIterator

typedef ListIterator<CanonicalForm> CFListIterator

Definition at line 537 of file factory.h.

## CFMatrix

typedef Matrix<CanonicalForm> CFMatrix

Definition at line 539 of file factory.h.

## Intarray

typedef Array<int> Intarray

Definition at line 546 of file factory.h.

## IntList

typedef List<int> IntList

Definition at line 542 of file factory.h.

## IntListIterator

typedef ListIterator<int> IntListIterator

Definition at line 543 of file factory.h.

## ListCFList

typedef List<CFList> ListCFList

Definition at line 540 of file factory.h.

## ListCFListIterator

typedef ListIterator<CFList> ListCFListIterator

Definition at line 541 of file factory.h.

## MPList

typedef List<MapPair> MPList

Definition at line 986 of file factory.h.

## MPListIterator

typedef ListIterator<MapPair> MPListIterator

Definition at line 987 of file factory.h.

## termList

typedef term* termList

Definition at line 799 of file factory.h.

## Varlist

typedef List<Variable> Varlist

Definition at line 544 of file factory.h.

## VarlistIterator

typedef ListIterator<Variable> VarlistIterator

Definition at line 545 of file factory.h.

## Function Documentation

## absFactorize()

CFAFList FACTORY_PUBLIC 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] | G | poly over Q

Definition at line 262 of file facAbsFact.cc.

{
//TODO handle homogeneous input, is already done in LIB interface but still...
ASSERT (getCharacteristic() == 0, "expected poly over Q");
CanonicalForm F= G;
CanonicalForm LcF= Lc (F);
bool isRat= isOn (SW_RATIONAL);
if (isRat)
F *= bCommonDen (F);
Off (SW_RATIONAL);
F /= icontent (F);
if (isRat)
On (SW_RATIONAL);
CFFList rationalFactors= factorize (F);
CFAFList result, resultBuf;
CFAFListIterator iter;
CFFListIterator i= rationalFactors;
i++;
for (; i.hasItem(); i++)
{
resultBuf= absFactorizeMain (i.getItem().factor());
for (iter= resultBuf; iter.hasItem(); iter++)
iter.getItem()= CFAFactor (iter.getItem().factor(),
iter.getItem().minpoly(), i.getItem().exp());
result= Union (result, resultBuf);
}
if (isRat)
normalize (result);
result.insert (CFAFactor (LcF, 1, 1));
return result;
}
isOn
bool isOn(int sw)
switches
Definition canonicalform.cc:1971
On
void On(int sw)
switches
Definition canonicalform.cc:1957
Off
void Off(int sw)
switches
Definition canonicalform.cc:1964
CFAFactor
AFactor< CanonicalForm > CFAFactor
Definition canonicalform.h:389
icontent
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f ).
Definition cf_gcd.cc:74
CFAFListIterator
ListIterator< CFAFactor > CFAFListIterator
Definition canonicalform.h:391
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition canonicalform.h:307
CFAFList
List< CFAFactor > CFAFList
Definition canonicalform.h:390
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
i
int i
Definition cfEzgcd.cc:132
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r,...
Definition cf_algorithm.cc:293
factorize
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition cf_defs.h:31
CanonicalForm
factory's main class
Definition canonicalform.h:86
iter
CFFListIterator iter
Definition facAbsBiFact.cc:54
LcF
CanonicalForm LcF
Definition facAbsBiFact.cc:51
result
return result
Definition facAbsBiFact.cc:76
absFactorizeMain
CFAFList absFactorizeMain(const CanonicalForm &G)
main absolute factorization routine, expects poly which is irreducible over Q
Definition facAbsFact.cc:303
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
G
STATIC_VAR TreeM * G
Definition janet.cc:31
normalize
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition syz3.cc:1027

## apply()

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

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

apply() - apply mf to terms of f.

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

An example:

void
diff( CanonicalForm & f, int & i )
{
f = f * i;
if ( i > 0 ) i--;
}
f
FILE * f
Definition checklibs.c:9
diff
STATIC_VAR gmp_float * diff
Definition mpr_complex.cc:45

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

Definition at line 402 of file cf_ops.cc.

{
if ( f.inCoeffDomain() )
{
int exp = 0;
CanonicalForm result = f;
mf( result, exp );
ASSERT( exp == 0, "illegal result, do not know what variable to use" );
return result;
}
else
{
CanonicalForm result, coeff;
CFIterator i;
int exp;
Variable x = f.mvar();
for ( i = f; i.hasTerms(); i++ )
{
coeff = i.coeff();
exp = i.exp();
mf( coeff, exp );
if ( ! coeff.isZero() )
result += power( x, exp ) * coeff;
}
return result;
}
}
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
x
Variable x
Definition cfModGcd.cc:4090
CFIterator
class to iterate through CanonicalForm's
Definition cf_iter.h:44
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Variable
factory's class for variables
Definition factory.h:127
exp
gmp_float exp(const gmp_float &a)
Definition mpr_complex.cc:349

## 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.

{
CFList QS= PS, BS, RS;
CanonicalForm b;
int cb, degb;
if (PS.length() < 2)
return PS;
CFListIterator i;
while (!QS.isEmpty())
{
b= lowestRank (QS);
cb= b.level();
BS= Union(CFList (b), BS);
if (cb <= 0)
return CFList();
else
{
degb= degree (b);
RS= CFList();
for (i= QS; i.hasItem(); i++)
{
if (degree (i.getItem(), cb) < degb)
RS= Union (CFList (i.getItem()), RS);
}
QS= RS;
}
}
return BS;
}
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
lowestRank
CanonicalForm lowestRank(const CFList &L)
Definition cfCharSetsUtil.cc:357
b
CanonicalForm b
Definition cfModGcd.cc:4111
List::length
int length() const
Definition ftmpl_list.cc:273
List::isEmpty
int isEmpty() const
Definition ftmpl_list.cc:267

## bCommonDen()

CanonicalForm FACTORY_PUBLIC bCommonDen | ( | const CanonicalForm & | f | ) |

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

**/ void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable& x ) { ASSERT( x.level() > 0, "type error: polynomial variable expected" ); ASSERT( ! g.isZero(), "math error: division by zero" );

swap variables such that x's level is larger or equal than both f's and g's levels. Variable X = tmax( tmax( f.mvar(), g.mvar() ), x ); CanonicalForm F = swapvar( f, x, X ); CanonicalForm G = swapvar( g, x, X );

now, we have to calculate the pseudo remainder of F and G w.r.t. X int fDegree = degree( F, X ); int gDegree = degree( G, X ); if ( fDegree < 0 || fDegree < gDegree ) { q = 0; r = f; } else { divrem( power( LC( G, X ), fDegree-gDegree+1 ) * F, G, q, r ); q = swapvar( q, x, X ); r = swapvar( r, x, X ); } }

/** static CanonicalForm internalBCommonDen ( const CanonicalForm & f )

internalBCommonDen() - recursively calculate multivariate common denominator of coefficients of `f'.

Used by: bCommonDen()

## Type info:

f: Poly( Q ) Switches: isOff( SW_RATIONAL )

**/ static CanonicalForm internalBCommonDen ( const CanonicalForm & f ) { if ( f.inBaseDomain() ) return f.den(); else { CanonicalForm result = 1; for ( CFIterator i = f; i.hasTerms(); i++ ) result = blcm( result, internalBCommonDen( i.coeff() ) ); return result; } }

/** 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.

{
if ( getCharacteristic() == 0 && isOn( SW_RATIONAL ) )
{
// otherwise `bgcd()' returns one
Off( SW_RATIONAL );
CanonicalForm result = internalBCommonDen( f );
On( SW_RATIONAL );
return result;
}
else
return CanonicalForm( 1 );
}

## blcm()

CanonicalForm FACTORY_PUBLIC blcm | ( | const CanonicalForm & | f,
|  | const CanonicalForm & | g )

Definition at line 1816 of file canonicalform.cc.

{
if ( f.isZero() || g.isZero() )
return CanonicalForm( 0L );
/*
else if (f.isOne())
return g;
else if (g.isOne())
return f;
*/
else
return (f / bgcd( f, g )) * g;
}
bgcd
CanonicalForm bgcd(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm bgcd ( const CanonicalForm & f, const CanonicalForm & g ).
Definition canonicalform.cc:1648
g
g
Definition cfModGcd.cc:4098

## cf_getBigPrime()

int FACTORY_PUBLIC cf_getBigPrime | ( | int | i | ) |

Definition at line 39 of file cf_primes.cc.

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

## cf_getNumBigPrimes()

int FACTORY_PUBLIC cf_getNumBigPrimes | ( |  | ) |

Definition at line 45 of file cf_primes.cc.

{
return NUMBIGPRIMES;
}

## cf_getNumPrimes()

int FACTORY_PUBLIC cf_getNumPrimes | ( |  | ) |

Definition at line 23 of file cf_primes.cc.

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

## cf_getNumSmallPrimes()

int FACTORY_PUBLIC cf_getNumSmallPrimes | ( |  | ) |

Definition at line 34 of file cf_primes.cc.

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

## cf_getPrime()

int FACTORY_PUBLIC cf_getPrime | ( | int | i | ) |

Definition at line 14 of file cf_primes.cc.

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

## cf_getSmallPrime()

int FACTORY_PUBLIC cf_getSmallPrime | ( | int | i | ) |

Definition at line 28 of file cf_primes.cc.

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

## cf_HNF()

CFMatrix * cf_HNF | ( | CFMatrix & | A | ) |

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

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

Note
  : uses NTL

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

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

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

Definition at line 44 of file cf_hnf.cc.

{
#ifdef HAVE_FLINT
fmpz_mat_t FLINTM;
convertFacCFMatrix2Fmpz_mat_t(FLINTM,A);
fmpz_mat_hnf(FLINTM,FLINTM);
CFMatrix *r=convertFmpz_mat_t2FacCFMatrix(FLINTM);
fmpz_mat_clear(FLINTM);
return r;
#elif defined(HAVE_NTL)
mat_ZZ *AA=convertFacCFMatrix2NTLmat_ZZ(A);
ZZ DD=convertFacCF2NTLZZ(determinant(A,A.rows()));
mat_ZZ WW;
HNF(WW,*AA,DD);
delete AA;
return convertNTLmat_ZZ2FacCFMatrix(WW);
#else
factoryError("NTL/FLINT missing: cf_HNF");
return NULL; // avoid warning
#endif
}
convertFacCFMatrix2Fmpz_mat_t
void convertFacCFMatrix2Fmpz_mat_t(fmpz_mat_t M, const CFMatrix &m)
conversion of a factory matrix over Z to a fmpz_mat_t
Definition FLINTconvert.cc:585
convertFmpz_mat_t2FacCFMatrix
CFMatrix * convertFmpz_mat_t2FacCFMatrix(const fmpz_mat_t m)
conversion of a FLINT matrix over Z to a factory matrix
Definition FLINTconvert.cc:598
convertFacCFMatrix2NTLmat_ZZ
mat_ZZ * convertFacCFMatrix2NTLmat_ZZ(const CFMatrix &m)
Definition NTLconvert.cc:1138
convertNTLmat_ZZ2FacCFMatrix
CFMatrix * convertNTLmat_ZZ2FacCFMatrix(const mat_ZZ &m)
Definition NTLconvert.cc:1153
convertFacCF2NTLZZ
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Definition NTLconvert.cc:670
CFMatrix
Matrix< CanonicalForm > CFMatrix
Definition canonicalform.h:398
determinant
CanonicalForm FACTORY_PUBLIC determinant(const CFMatrix &M, int n)
Definition cf_linsys.cc:222
factoryError
VAR void(* factoryError)(const char *s)
Definition cf_util.cc:80
NULL
#define NULL
Definition omList.c:12
A
#define A
Definition sirandom.c:24

## cf_LLL()

CFMatrix * cf_LLL | ( | CFMatrix & | A | ) |

performs LLL reduction.

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

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

Note
  : uses NTL or FLINT

Definition at line 66 of file cf_hnf.cc.

{
#ifdef HAVE_FLINT
fmpz_mat_t FLINTM;
convertFacCFMatrix2Fmpz_mat_t(FLINTM,A);
fmpq_t delta,eta;
fmpq_init(delta); fmpq_set_si(delta,1,1);
fmpq_init(eta); fmpq_set_si(eta,3,4);
fmpz_mat_lll_storjohann(FLINTM,delta,eta);
CFMatrix *r=convertFmpz_mat_t2FacCFMatrix(FLINTM);
fmpz_mat_clear(FLINTM);
return r;
#elif defined(HAVE_NTL)
mat_ZZ *AA=convertFacCFMatrix2NTLmat_ZZ(A);
ZZ det2;
LLL(det2,*AA,0L);
CFMatrix *r= convertNTLmat_ZZ2FacCFMatrix(*AA);
delete AA;
return r;
#else
factoryError("NTL/FLINT missing: cf_LLL");
return NULL; // avoid warning
#endif
}
CxxTest::delta
bool delta(X x, Y y, D d)
Definition TestSuite.h:160

## charSeries()

ListCFList charSeries | ( | const CFList & | L | ) |

characteristic series

Definition at line 411 of file cfCharSets.cc.

{
ListCFList tmp, result, tmp2, ppi1, ppi2, qqi, ppi, alreadyConsidered;
CFList l, charset, ini;
int count= 0;
int highestLevel= 1;
CFListIterator iter;
StoreFactors StoredFactors;
l= L;
for (iter= l; iter.hasItem(); iter++)
{
iter.getItem()= normalize (iter.getItem());
if (highestLevel < iter.getItem().level())
highestLevel= iter.getItem().level();
}
tmp= ListCFList (l);
while (!tmp.isEmpty())
{
sortListCFList (tmp);
l= tmp.getFirst();
tmp= Difference (tmp, l);
select (ppi, l.length(), ppi1, ppi2);
inplaceUnion (ppi2, qqi);
if (count > 0)
ppi= Union (ppi1, ListCFList (l));
else
ppi= ListCFList();
if (l.length() - 3 < highestLevel)
charset= charSetViaModCharSet (l, StoredFactors);
else
charset= charSetViaCharSetN (l);
if (charset.length() > 0 && charset.getFirst().level() > 0)
{
result= Union (ListCFList (charset), result);
ini= factorsOfInitials (charset);
ini= Union (ini, factorPSet (StoredFactors.FS1));
sortCFListByLevel (ini);
}
else
{
ini= factorPSet (StoredFactors.FS1);
sortCFListByLevel (ini);
}
tmp2= adjoin (ini, l, qqi);
tmp= Union (tmp2, tmp);
StoredFactors.FS1= CFList();
StoredFactors.FS2= CFList();
ppi1= ListCFList();
ppi2= ListCFList();
count++;
}
//TODO need to remove superflous components
return result;
}
ListCFList
List< CFList > ListCFList
Definition canonicalform.h:399
inplaceUnion
void inplaceUnion(const ListCFList &a, ListCFList &b)
Union of a and b stored in b.
Definition cfCharSetsUtil.cc:473
factorsOfInitials
CFList factorsOfInitials(const CFList &L)
Definition cfCharSetsUtil.cc:755
select
void select(const ListCFList &ppi, int length, ListCFList &ppi1, ListCFList &ppi2)
Definition cfCharSetsUtil.cc:570
sortListCFList
void sortListCFList(ListCFList &list)
sort in descending order of length of elements
Definition cfCharSetsUtil.cc:396
sortCFListByLevel
void sortCFListByLevel(CFList &list)
sort in descending order of level of elements
Definition cfCharSetsUtil.cc:428
factorPSet
CFList factorPSet(const CFList &PS)
Definition cfCharSetsUtil.cc:805
adjoin
ListCFList adjoin(const CFList &is, const CFList &qs, const ListCFList &qh)
Definition cfCharSetsUtil.cc:495
charSetViaCharSetN
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
Definition cfCharSets.cc:246
charSetViaModCharSet
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents)
characteristic set via modified medial set
Definition cfCharSets.cc:356
l
int l
Definition cfEzgcd.cc:100
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
List::getFirst
T getFirst() const
Definition ftmpl_list.cc:279
StoreFactors
class to store factors that get removed during char set computation
Definition cfCharSetsUtil.h:29
StoreFactors::FS2
CFList FS2
candidate factors that might get removed
Definition cfCharSetsUtil.h:32
StoreFactors::FS1
CFList FS1
factors that were removed
Definition cfCharSetsUtil.h:31
tmp2
CFList tmp2
Definition facFqBivar.cc:75
Difference
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
count
int status int void size_t count
Definition si_signals.h:69

## charSet()

CFList charSet | ( | const CFList & | PS | ) |

characteristic set

Definition at line 187 of file cfCharSets.cc.

{
CFList QS= PS, RS= PS, CSet, tmp;
CFListIterator i;
CanonicalForm r;
while (!RS.isEmpty())
{
CSet= basicSet (QS);
RS= CFList();
if (CSet.length() > 0 && CSet.getFirst().level() > 0)
{
tmp= Difference (QS, CSet);
for (i= tmp; i.hasItem(); i++)
{
r= Prem (i.getItem(), CSet);
if (r != 0)
RS= Union (RS, CFList (r));
}
QS= Union (QS, RS);
}
}
return CSet;
}
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
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

## charSetN()

CFList charSetN | ( | const CFList & | PS | ) |

medial set

Definition at line 216 of file cfCharSets.cc.

{
CFList QS= PS, RS= PS, CSet, tmp;
CFListIterator i;
CanonicalForm r;
while (!RS.isEmpty())
{
QS= uniGcd (QS);
CSet= basicSet (QS);
RS= CFList();
if (CSet.length() > 0 && CSet.getFirst().level() > 0)
{
tmp= Difference (QS, CSet);
for (i= tmp; i.hasItem(); i++)
{
r= Prem (i.getItem(), CSet);
if (!r.isZero())
RS= Union (RS, CFList (r));
}
QS= Union (CSet, RS);
}
}
return CSet;
}
uniGcd
CFList uniGcd(const CFList &L)
Definition cfCharSetsUtil.cc:721

## charSetViaCharSetN()

CFList charSetViaCharSetN | ( | const CFList & | PS | ) |

compute a characteristic set via medial set

Definition at line 246 of file cfCharSets.cc.

{
CFList L;
CFFList sqrfFactors;
CanonicalForm sqrf;
CFFListIterator iter2;
for (CFListIterator iter= PS; iter.hasItem(); iter++)
{
sqrf= 1;
sqrfFactors= sqrFree (iter.getItem());
for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
sqrf *= iter2.getItem().factor();
L= Union (L, CFList (normalize (sqrf)));
}
CFList result= charSetN (L);
if (result.isEmpty() || result.getFirst().inCoeffDomain())
return CFList(1);
CanonicalForm r;
CFList RS;
CFList tmp= Difference (L, result);
for (CFListIterator i= tmp; i.hasItem(); i++)
{
r= Premb (i.getItem(), result);
if (!r.isZero())
RS= Union (RS, CFList (r));
}
if (RS.isEmpty())
return result;
return charSetViaCharSetN (Union (L, Union (RS, result)));
}
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
charSetN
CFList charSetN(const CFList &PS)
medial set
Definition cfCharSets.cc:216
sqrFree
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition cf_factor.cc:961
Factor::factor
T factor() const
Definition ftmpl_factor.h:30
ListIterator::hasItem
int hasItem()
Definition ftmpl_list.cc:439
ListIterator::getItem
T & getItem() const
Definition ftmpl_list.cc:431

## 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.

{
StoreFactors tmp;
return charSetViaModCharSet (PS, tmp, removeContents);
}

## 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.

{
CFList L;
CFFList sqrfFactors;
CanonicalForm sqrf;
CFFListIterator iter2;
for (CFListIterator iter= PS; iter.hasItem(); iter++)
{
sqrf= 1;
sqrfFactors= sqrFree (iter.getItem());
for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
sqrf *= iter2.getItem().factor();
L= Union (L, CFList (normalize (sqrf)));
}
L= uniGcd (L);
CFList result= modCharSet (L, StoredFactors, removeContents);
if (result.isEmpty() || result.getFirst().inCoeffDomain())
return CFList(1);
CanonicalForm r;
CFList RS;
CFList tmp= Difference (L, result);
for (CFListIterator i= tmp; i.hasItem(); i++)
{
r= Premb (i.getItem(), result);
if (!r.isZero())
RS= Union (RS, CFList (r));
}
if (RS.isEmpty())
return result;
return charSetViaModCharSet (Union (L, Union (RS, result)), StoredFactors,
removeContents);
}
modCharSet
CFList modCharSet(const CFList &L, StoreFactors &StoredFactors, bool removeContents)
modified medial set
Definition cfCharSets.cc:284

## chineseRemainder() [1/2]

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

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

chineseRemainder - integer chinese remaindering.

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

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

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

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

Definition at line 57 of file cf_chinese.cc.

{
DEBINCLEVEL( cerr, "chineseRemainder" );
DEBOUTLN( cerr, "log(q1) = " << q1.ilog2() );
DEBOUTLN( cerr, "log(q2) = " << q2.ilog2() );
// We calculate xnew as follows:
// xnew = v1 + v2 * q1
// where
// v1 = x1 (mod q1)
// v2 = (x2-v1)/q1 (mod q2) (*)
//
// We do one extra test to check whether x2-v1 vanishes (mod
// q2) in (*) since it is not costly and may save us
// from calculating the inverse of q1 (mod q2).
//
// u: v1 (mod q2)
// d: x2-v1 (mod q2)
// s: 1/q1 (mod q2)
//
CanonicalForm v2, v1;
CanonicalForm u, d, s, dummy;
v1 = mod( x1, q1 );
u = mod( v1, q2 );
d = mod( x2-u, q2 );
if ( d.isZero() )
{
xnew = v1;
qnew = q1 * q2;
DEBDECLEVEL( cerr, "chineseRemainder" );
return;
}
(void)bextgcd( q1, q2, s, dummy );
v2 = mod( d*s, q2 );
xnew = v1 + v2*q1;
// After all, calculate new modulus. It is important that
// this is done at the very end of the algorithm, since q1
// and qnew may refer to the same object (same is true for x1
// and xnew).
qnew = q1 * q2;
DEBDECLEVEL( cerr, "chineseRemainder" );
}
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:1722
mod
CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
CanonicalForm::ilog2
int ilog2() const
int CanonicalForm::ilog2 () const
Definition canonicalform.cc:1417
DEBINCLEVEL
#define DEBINCLEVEL(stream, msg)
Definition debug.h:44
DEBOUTLN
#define DEBOUTLN(stream, objects)
Definition debug.h:49
DEBDECLEVEL
#define DEBDECLEVEL(stream, msg)
Definition debug.h:45
s
const CanonicalForm int s
Definition facAbsFact.cc:51

## chineseRemainder() [2/2]

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

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

chineseRemainder - integer chinese remaindering.

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

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

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

Definition at line 124 of file cf_chinese.cc.

{
DEBINCLEVEL( cerr, "chineseRemainder( ... CFArray ... )" );
ASSERT( x.min() == q.min() && x.size() == q.size(), "incompatible arrays" );
CFArray X(x), Q(q);
int i, j, n = x.size(), start = x.min();
DEBOUTLN( cerr, "array size = " << n );
while ( n != 1 )
{
i = j = start;
while ( i < start + n - 1 )
{
// This is a little bit dangerous: X[i] and X[j] (and
// Q[i] and Q[j]) may refer to the same object. But
// xnew and qnew in the above function are modified
// at the very end of the function, so we do not
// modify x1 and q1, resp., by accident.
chineseRemainder( X[i], Q[i], X[i+1], Q[i+1], X[j], Q[j] );
i += 2;
j++;
}
if ( n & 1 )
{
X[j] = X[i];
Q[j] = Q[i];
}
// Maybe we would get some memory back at this point if
// we would set X[j+1, ..., n] and Q[j+1, ..., n] to zero
// at this point?
n = ( n + 1) / 2;
}
xnew = X[start];
qnew = Q[q.min()];
DEBDECLEVEL( cerr, "chineseRemainder( ... CFArray ... )" );
}
CFArray
Array< CanonicalForm > CFArray
Definition canonicalform.h:397
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:57
Array::size
int size() const
Definition ftmpl_array.cc:92
Array::min
int min() const
Definition ftmpl_array.cc:98
j
int j
Definition facHensel.cc:110
Q
#define Q
Definition sirandom.c:26

## chineseRemainderCached() [1/2]

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

Definition at line 308 of file cf_chinese.cc.

{
CFArray A(2); A[0]=a; A[1]=b;
CFArray Q(2); Q[0]=q1; Q[1]=q2;
chineseRemainderCached(A,Q,xnew,qnew,inv);
}
chineseRemainderCached
void chineseRemainderCached(const CFArray &a, const CFArray &n, CanonicalForm &xnew, CanonicalForm &prod, CFArray &inv)
Definition cf_chinese.cc:290

## chineseRemainderCached() [2/2]

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

Definition at line 290 of file cf_chinese.cc.

{
CanonicalForm p, sum=0L; prod=1L;
int i;
int len=n.size();
for (i = 0; i < len; i++) prod *= n[i];
for (i = 0; i < len; i++)
{
p = prod / n[i];
sum += a[i] * chin_mul_inv(p, n[i], i, inv) * p;
}
xnew = mod(sum , prod);
}
p
int p
Definition cfModGcd.cc:4086
chin_mul_inv
static CanonicalForm chin_mul_inv(const CanonicalForm a, const CanonicalForm b, int ind, CFArray &inv)
Definition cf_chinese.cc:276
prod
fq_nmod_poly_t prod
Definition facHensel.cc:100

## compress() [1/3]

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

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

compress() - compress the canonical form f.

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

Definition at line 210 of file cf_map.cc.

{
CanonicalForm result = f;
int i, n;
int * degs = degrees( f );
m = CFMap();
n = i = 1;
while ( i <= level( f ) ) {
while( degs[i] == 0 ) i++;
if ( i != n ) {
// swap variables and remember the swap in the map
m.newpair( Variable( n ), Variable( i ) );
result = swapvar( result, Variable( i ), Variable( n ) );
}
n++; i++;
}
DELETE_ARRAY(degs);
return result;
}
degrees
int * degrees(const CanonicalForm &f, int *degs=0)
int * degrees ( const CanonicalForm & f, int * degs )
Definition cf_ops.cc:493
swapvar
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
level
int level(const CanonicalForm &f)
Definition canonicalform.h:331
m
int m
Definition cfEzgcd.cc:128
DELETE_ARRAY
#define DELETE_ARRAY(P)
Definition cf_defs.h:65
CFMap
class CFMap
Definition cf_map.h:85

## compress() [2/3]

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

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

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

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

Definition at line 349 of file cf_map.cc.

{
int n = tmax( f.level(), g.level() );
int i, k, p1, pe;
int * degsf = NEW_ARRAY(int,n+1);
int * degsg = NEW_ARRAY(int,n+1);
for ( i = 0; i <= n; i++ )
{
degsf[i] = degsg[i] = 0;
}
degsf = degrees( f, degsf );
degsg = degrees( g, degsg );
optvalues( degsf, degsg, n, p1, pe );
i = 1; k = 1;
if ( pe > 1 )
{
M.newpair( Variable(pe), Variable(k) );
N.newpair( Variable(k), Variable(pe) );
k++;
}
while ( i <= n )
{
if ( degsf[i] > 0 && degsg[i] > 0 )
{
if ( ( i != k ) && ( i != pe ) && ( i != p1 ) )
{
M.newpair( Variable(i), Variable(k) );
N.newpair( Variable(k), Variable(i) );
}
k++;
}
i++;
}
if ( p1 != pe )
{
M.newpair( Variable(p1), Variable(k) );
N.newpair( Variable(k), Variable(p1) );
k++;
}
i = 1;
while ( i <= n )
{
if ( degsf[i] > 0 && degsg[i] == 0 ) {
if ( i != k )
{
M.newpair( Variable(i), Variable(k) );
k++;
}
}
else if ( degsf[i] == 0 && degsg[i] > 0 )
{
if ( i != k )
{
M.newpair( Variable(i), Variable(k) );
k++;
}
}
i++;
}
DELETE_ARRAY(degsf);
DELETE_ARRAY(degsg);
}
N
const CanonicalForm CFMap CFMap & N
Definition cfEzgcd.cc:56
degsf
int * degsf
Definition cfEzgcd.cc:59
k
int k
Definition cfEzgcd.cc:99
degsg
int * degsg
Definition cfEzgcd.cc:60
NEW_ARRAY
#define NEW_ARRAY(T, N)
Definition cf_defs.h:64
optvalues
static void optvalues(const int *df, const int *dg, const int n, int &p1, int &pe)
Definition cf_map.cc:296
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
M
#define M
Definition sirandom.c:25

## compress() [3/3]

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

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

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

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

Definition at line 245 of file cf_map.cc.

{
M = N = CFMap();
if ( a.size() == 0 )
return;
int maxlevel = level( a[a.min()] );
int i, j;
// get the maximum of levels in a
for ( i = a.min() + 1; i <= a.max(); i++ )
if ( level( a[i] ) > maxlevel )
maxlevel = level( a[i] );
if ( maxlevel <= 0 )
return;
int * degs = NEW_ARRAY(int,maxlevel+1);
int * tmp = NEW_ARRAY(int,maxlevel+1);
for ( i = maxlevel; i >= 1; i-- )
degs[i] = 0;
// calculate the union of all levels occuring in a
for ( i = a.min(); i <= a.max(); i++ )
{
tmp = degrees( a[i], tmp );
for ( j = 1; j <= level( a[i] ); j++ )
if ( tmp[j] != 0 )
degs[j] = 1;
}
// create the maps
i = 1; j = 1;
while ( i <= maxlevel )
{
if ( degs[i] != 0 )
{
M.newpair( Variable(i), Variable(j) );
N.newpair( Variable(j), Variable(i) );
j++;
}
i++;
}
DELETE_ARRAY(degs);
DELETE_ARRAY(tmp);
}
Array::max
int max() const
Definition ftmpl_array.cc:104

## content() [1/2]

CanonicalForm FACTORY_PUBLIC content | ( | const CanonicalForm & | f | ) |

CanonicalForm content ( const CanonicalForm & f ).

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

Normalizes result.

Definition at line 603 of file cf_gcd.cc.

{
if ( f.inPolyDomain() || ( f.inExtension() && ! getReduce( f.mvar() ) ) )
{
CFIterator i = f;
CanonicalForm result = abs( i.coeff() );
i++;
while ( i.hasTerms() && ! result.isOne() )
{
result = gcd( i.coeff(), result );
i++;
}
return result;
}
else
return abs( f );
}
abs
Rational abs(const Rational &a)
Definition GMPrat.cc:436
gcd
CanonicalForm gcd(const CanonicalForm &f, const CanonicalForm &g)
Definition cf_gcd.cc:685
getReduce
bool getReduce(const Variable &alpha)
Definition variable.cc:232

## content() [2/2]

CanonicalForm FACTORY_PUBLIC 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 629 of file cf_gcd.cc.

{
if (f.inBaseDomain()) return f;
ASSERT( x.level() > 0, "cannot calculate content with respect to algebraic variable" );
Variable y = f.mvar();
if ( y == x )
return cf_content( f, 0 );
else if ( y < x )
return f;
else
return swapvar( content( swapvar( f, y, x ), y ), y, x );
}
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:578
content
CanonicalForm content(const CanonicalForm &f)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
y
const CanonicalForm int const CFList const Variable & y
Definition facAbsFact.cc:53

## degree() [1/2]

int degree | ( | const CanonicalForm & | f | ) |

inline

Definition at line 457 of file factory.h.

{ return f.degree(); }

## degree() [2/2]

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

inline

Definition at line 460 of file factory.h.

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

## degrees()

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

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

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

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

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

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

Definition at line 493 of file cf_ops.cc.

{
if ( f.inCoeffDomain() )
{
if (degs != 0)
return degs;
else
return 0;
}
else
{
int level = f.level();
if ( degs == NULL )
degs = NEW_ARRAY(int,level+1);
for ( int i = level; i >= 0; i-- )
degs[i] = 0;
degreesRec( f, degs );
return degs;
}
}
degreesRec
static void degreesRec(const CanonicalForm &f, int *degs)
static void degreesRec ( const CanonicalForm & f, int * degs )
Definition cf_ops.cc:463

## den()

CanonicalForm den | ( | const CanonicalForm & | f | ) |

inline

Definition at line 481 of file factory.h.

{ return f.den(); }

## deriv()

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

inline

Definition at line 487 of file factory.h.

{ return f.deriv( x ); }

## determinant()

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

Definition at line 222 of file cf_linsys.cc.

{
typedef int* int_ptr;
ASSERT( rows <= M.rows() && rows <= M.columns() && rows > 0, "undefined determinant" );
if ( rows == 1 )
return M(1,1);
else if ( rows == 2 )
return M(1,1)*M(2,2)-M(2,1)*M(1,2);
else if ( matrix_in_Z( M, rows ) )
{
int ** mm = new int_ptr[rows];
CanonicalForm x, q, Qhalf, B;
int n, i, intdet, p, pno;
for ( i = 0; i < rows; i++ )
{
mm[i] = new int[rows];
}
pno = 0; n = 0;
TIMING_START(det_bound);
B = detbound( M, rows );
TIMING_END(det_bound);
q = 1;
TIMING_START(det_numprimes);
while ( B > q && n < cf_getNumBigPrimes() )
{
q *= cf_getBigPrime( n );
n++;
}
TIMING_END(det_numprimes);
CFArray X(1,n), Q(1,n);
while ( pno < n )
{
p = cf_getBigPrime( pno );
setCharacteristic( p );
// map matrix into char p
TIMING_START(det_mapping);
fill_int_mat( M, mm, rows );
TIMING_END(det_mapping);
pno++;
DEBOUT( cerr, "." );
TIMING_START(det_determinant);
intdet = determinant( mm, rows );
TIMING_END(det_determinant);
setCharacteristic( 0 );
X[pno] = intdet;
Q[pno] = p;
}
TIMING_START(det_chinese);
chineseRemainder( X, Q, x, q );
TIMING_END(det_chinese);
Qhalf = q / 2;
if ( x > Qhalf )
x = x - q;
for ( i = 0; i < rows; i++ )
delete [] mm[i];
delete [] mm;
return x;
}
else
{
CFMatrix m( M );
CanonicalForm divisor = 1, pivot, mji;
int i, j, k, sign = 1;
for ( i = 1; i <= rows; i++ ) {
pivot = m(i,i); k = i;
for ( j = i+1; j <= rows; j++ ) {
if ( betterpivot( pivot, m(j,i) ) ) {
pivot = m(j,i);
k = j;
}
}
if ( pivot.isZero() )
return 0;
if ( i != k )
{
m.swapRow( i, k );
sign = -sign;
}
for ( j = i+1; j <= rows; j++ )
{
if ( ! m(j,i).isZero() )
{
divisor *= pivot;
mji = m(j,i);
m(j,i) = 0;
for ( k = i+1; k <= rows; k++ )
m(j,k) = m(j,k) * pivot - m(i,k)*mji;
}
}
}
pivot = sign;
for ( i = 1; i <= rows; i++ )
pivot *= m(i,i);
return pivot / divisor;
}
}
setCharacteristic
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
chineseRemainder
void FACTORY_PUBLIC chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2,...
Definition cf_chinese.cc:57
matrix_in_Z
bool matrix_in_Z(const CFMatrix &M, int rows)
Definition cf_linsys.cc:39
betterpivot
bool betterpivot(const CanonicalForm &oldpivot, const CanonicalForm &newpivot)
Definition cf_linsys.cc:61
detbound
CanonicalForm detbound(const CFMatrix &M, int rows)
Definition cf_linsys.cc:486
determinant
int determinant(int **extmat, int n)
Definition cf_linsys.cc:556
fill_int_mat
static bool fill_int_mat(const CFMatrix &M, int **m, int rows)
Definition cf_linsys.cc:203
cf_getBigPrime
int cf_getBigPrime(int i)
Definition cf_primes.cc:39
cf_getNumBigPrimes
int cf_getNumBigPrimes()
Definition cf_primes.cc:45
DEBOUT
#define DEBOUT(stream, objects)
Definition debug.h:47
B
b *CanonicalForm B
Definition facBivar.cc:52
isZero
bool isZero(const CFArray &A)
checks if entries of A are zero
Definition facSparseHensel.h:468
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
sign
static int sign(int x)
Definition ring.cc:3504
int_ptr
int * int_ptr
Definition structs.h:50
TIMING_END
#define TIMING_END(t)
Definition timing.h:93
TIMING_START
#define TIMING_START(t)
Definition timing.h:92

## div()

CF_NO_INLINE FACTORY_PUBLIC CanonicalForm div | ( | const CanonicalForm & | ,
|  | const CanonicalForm & | )

## euclideanNorm()

CanonicalForm euclideanNorm | ( | const CanonicalForm & | f | ) |

## ExtensionLevel()

int ExtensionLevel | ( |  | ) |

Definition at line 254 of file variable.cc.

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

## extgcd()

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

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

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

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

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

Definition at line 174 of file cfUnivarGcd.cc.

{
if (f.isZero())
{
a= 0;
b= 1;
return g;
}
else if (g.isZero())
{
a= 1;
b= 0;
return f;
}
#ifdef HAVE_FLINT
if (( getCharacteristic() > 0 ) && (CFFactory::gettype() != GaloisFieldDomain)
&& (f.level()==g.level()) && isPurePoly(f) && isPurePoly(g))
{
nmod_poly_t F1, G1, A, B, R;
convertFacCF2nmod_poly_t (F1, f);
convertFacCF2nmod_poly_t (G1, g);
nmod_poly_init (R, getCharacteristic());
nmod_poly_init (A, getCharacteristic());
nmod_poly_init (B, getCharacteristic());
nmod_poly_xgcd (R, A, B, F1, G1);
a= convertnmod_poly_t2FacCF (A, f.mvar());
b= convertnmod_poly_t2FacCF (B, f.mvar());
CanonicalForm r= convertnmod_poly_t2FacCF (R, f.mvar());
nmod_poly_clear (F1);
nmod_poly_clear (G1);
nmod_poly_clear (A);
nmod_poly_clear (B);
nmod_poly_clear (R);
return r;
}
#elif defined(HAVE_NTL)
if (( getCharacteristic() > 0 ) && (CFFactory::gettype() != GaloisFieldDomain)
&& (f.level()==g.level()) && isPurePoly(f) && isPurePoly(g))
{
if (fac_NTL_char!=getCharacteristic())
{
fac_NTL_char=getCharacteristic();
zz_p::init(getCharacteristic());
}
zz_pX F1=convertFacCF2NTLzzpX(f);
zz_pX G1=convertFacCF2NTLzzpX(g);
zz_pX R;
zz_pX A,B;
XGCD(R,A,B,F1,G1);
a=convertNTLzzpX2CF(A,f.mvar());
b=convertNTLzzpX2CF(B,f.mvar());
return convertNTLzzpX2CF(R,f.mvar());
}
#endif
#ifdef HAVE_FLINT
if (( getCharacteristic() ==0) && (f.level()==g.level())
&& isPurePoly(f) && isPurePoly(g))
{
fmpq_poly_t F1, G1;
convertFacCF2Fmpq_poly_t (F1, f);
convertFacCF2Fmpq_poly_t (G1, g);
fmpq_poly_t R, A, B;
fmpq_poly_init (R);
fmpq_poly_init (A);
fmpq_poly_init (B);
fmpq_poly_xgcd (R, A, B, F1, G1);
a= convertFmpq_poly_t2FacCF (A, f.mvar());
b= convertFmpq_poly_t2FacCF (B, f.mvar());
CanonicalForm r= convertFmpq_poly_t2FacCF (R, f.mvar());
fmpq_poly_clear (F1);
fmpq_poly_clear (G1);
fmpq_poly_clear (A);
fmpq_poly_clear (B);
fmpq_poly_clear (R);
return r;
}
#elif defined(HAVE_NTL)
if (( getCharacteristic() ==0)
&& (f.level()==g.level()) && isPurePoly(f) && isPurePoly(g))
{
CanonicalForm fc=bCommonDen(f);
CanonicalForm gc=bCommonDen(g);
ZZX F1=convertFacCF2NTLZZX(f*fc);
ZZX G1=convertFacCF2NTLZZX(g*gc);
ZZX R=GCD(F1,G1);
CanonicalForm r=convertNTLZZX2CF(R,f.mvar());
ZZ RR;
ZZX A,B;
if (r.inCoeffDomain())
{
XGCD(RR,A,B,F1,G1,1);
CanonicalForm rr=convertZZ2CF(RR);
if(!rr.isZero())
{
a=convertNTLZZX2CF(A,f.mvar())*fc/rr;
b=convertNTLZZX2CF(B,f.mvar())*gc/rr;
return CanonicalForm(1);
}
else
{
F1 /= R;
G1 /= R;
XGCD (RR, A,B,F1,G1,1);
rr=convertZZ2CF(RR);
a=convertNTLZZX2CF(A,f.mvar())*(fc/rr);
b=convertNTLZZX2CF(B,f.mvar())*(gc/rr);
}
}
else
{
XGCD(RR,A,B,F1,G1,1);
CanonicalForm rr=convertZZ2CF(RR);
if (!rr.isZero())
{
a=convertNTLZZX2CF(A,f.mvar())*fc;
b=convertNTLZZX2CF(B,f.mvar())*gc;
}
else
{
F1 /= R;
G1 /= R;
XGCD (RR, A,B,F1,G1,1);
rr=convertZZ2CF(RR);
a=convertNTLZZX2CF(A,f.mvar())*(fc/rr);
b=convertNTLZZX2CF(B,f.mvar())*(gc/rr);
}
return r;
}
}
#endif
// may contain bug in the co-factors, see track 107
CanonicalForm contf = content( f );
CanonicalForm contg = content( g );
CanonicalForm p0 = f / contf, p1 = g / contg;
CanonicalForm f0 = 1, f1 = 0, g0 = 0, g1 = 1, q, r;
while ( ! p1.isZero() )
{
divrem( p0, p1, q, r );
p0 = p1; p1 = r;
r = g0 - g1 * q;
g0 = g1; g1 = r;
r = f0 - f1 * q;
f0 = f1; f1 = r;
}
CanonicalForm contp0 = content( p0 );
a = f0 / ( contf * contp0 );
b = g0 / ( contg * contp0 );
p0 /= contp0;
if ( p0.sign() < 0 )
{
p0 = -p0;
a = -a;
b = -b;
}
return p0;
}
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:294
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:208
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:320
convertZZ2CF
CanonicalForm convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
Definition NTLconvert.cc:495
convertFacCF2NTLZZX
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition NTLconvert.cc:691
convertNTLzzpX2CF
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
Definition NTLconvert.cc:255
convertNTLZZX2CF
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition NTLconvert.cc:285
convertFacCF2NTLzzpX
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition NTLconvert.cc:105
fac_NTL_char
VAR long fac_NTL_char
Definition NTLconvert.cc:46
divrem
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
Definition canonicalform.cc:1032
content
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f ).
Definition cf_gcd.cc:603
isPurePoly
bool isPurePoly(const CanonicalForm &f)
Definition cf_factor.cc:248
GaloisFieldDomain
#define GaloisFieldDomain
Definition cf_defs.h:18
CFFactory::gettype
static int gettype()
Definition cf_factory.h:28
CanonicalForm::sign
int sign() const
int CanonicalForm::sign () const
Definition canonicalform.cc:1360
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
nmod_poly_init
nmod_poly_init(FLINTmipo, getCharacteristic())
convertFacCF2nmod_poly_t
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear
nmod_poly_clear(FLINTmipo)
R
#define R
Definition sirandom.c:27

## 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. , and each element of as is assumed to be integral as well. must be either or .

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. , and each element of as is assumed to be integral as well. must be either or .

Parameters

  [in] | f | univariate poly
  [in] | as | irreducible characteristic set

Definition at line 1043 of file facAlgFunc.cc.

{
bool isRat= isOn (SW_RATIONAL);
if (!isRat && getCharacteristic() == 0)
On (SW_RATIONAL);
CFFList Output, output, Factors= factorize(f);
if (Factors.getFirst().factor().inCoeffDomain())
Factors.removeFirst();
if (as.length() == 0)
{
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
return Factors;
}
if (f.level() <= as.getLast().level())
{
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
return Factors;
}
for (CFFListIterator i=Factors; i.hasItem(); i++)
{
if (i.getItem().factor().level() > as.getLast().level())
{
output= facAlgFunc2 (i.getItem().factor(), as);
for (CFFListIterator j= output; j.hasItem(); j++)
Output= append (Output, CFFactor (j.getItem().factor(),
j.getItem().exp()*i.getItem().exp()));
}
}
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
return Output;
}
CFFactor
Factor< CanonicalForm > CFFactor
Definition canonicalform.h:392
List::removeFirst
void removeFirst()
Definition ftmpl_list.cc:287
List::getLast
T getLast() const
Definition ftmpl_list.cc:309
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition facAlgFuncUtil.cc:32
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

## 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. , and each element of as is assumed to be integral as well. must be either or .

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. , and each element of as is assumed to be integral as well. must be either or .

Parameters

  [in] | f | univariate poly
  [in] | as | irreducible characteristic set

Definition at line 905 of file facAlgFunc.cc.

{
bool isRat= isOn (SW_RATIONAL);
if (!isRat && getCharacteristic() == 0)
On (SW_RATIONAL);
Variable vf=f.mvar();
CFListIterator i;
CFFListIterator jj;
CFList reduceresult;
CFFList result;
// F1: [Test trivial cases]
// 1) first trivial cases:
if (vf.level() <= as.getLast().level())
{
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
return CFFList(CFFactor(f,1));
}
// 2) Setup list of those polys in AS having degree > 1
CFList Astar;
Variable x;
CanonicalForm elem;
Varlist ord, uord;
for (int ii= 1; ii < level (vf); ii++)
uord.append (Variable (ii));
for (i= as; i.hasItem(); i++)
{
elem= i.getItem();
x= elem.mvar();
if (degree (elem, x) > 1) // otherwise it's not an extension
{
Astar.append (elem);
ord.append (x);
}
}
uord= Difference (uord, ord);
// 3) second trivial cases: we already proved irr. of f over no extensions
if (Astar.length() == 0)
{
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
return CFFList (CFFactor (f, 1));
}
// 4) Look if elements in uord actually occur in any of the minimal
// polynomials. If no element of uord occures in any of the minimal
// polynomials the field is an alg. number field not an alg. function field
Varlist newuord= varsInAs (uord, Astar);
CFFList Factorlist;
Varlist gcdord= Union (ord, newuord);
gcdord.append (f.mvar());
bool isFunctionField= (newuord.length() > 0);
// TODO alg_sqrfree?
CanonicalForm Fgcd= 0;
if (isFunctionField)
Fgcd= alg_gcd (f, f.deriv(), Astar);
bool derivZero= f.deriv().isZero();
if (isFunctionField && (degree (Fgcd, f.mvar()) > 0) && !derivZero)
{
CanonicalForm Ggcd= divide(f, Fgcd,Astar);
if (getCharacteristic() == 0)
{
CFFList result= facAlgFunc2 (Ggcd, as); //Ggcd is the squarefree part of f
multiplicity (result, f, Astar);
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
return result;
}
Fgcd= pp (Fgcd);
Ggcd= pp (Ggcd);
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
return merge (facAlgFunc2 (Fgcd, as), facAlgFunc2 (Ggcd, as));
}
if (getCharacteristic() > 0)
{
IntList degreelist;
Variable vminpoly;
for (i= Astar; i.hasItem(); i++)
degreelist.append (degree (i.getItem()));
int extdeg= getDegOfExt (degreelist, degree (f));
if (newuord.length() == 0) // no parameters
{
if (extdeg > 1)
{
CanonicalForm MIPO= generateMipo (extdeg);
vminpoly= rootOf(MIPO);
}
Factorlist= Trager(f, Astar, vminpoly, as, isFunctionField);
if (extdeg > 1)
prune (vminpoly);
return Factorlist;
}
else if (isInseparable(Astar) || derivZero) // inseparable case
{
Factorlist= SteelTrager (f, Astar);
return Factorlist;
}
else // separable case
{
if (extdeg > 1)
{
CanonicalForm MIPO=generateMipo (extdeg);
vminpoly= rootOf (MIPO);
}
Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
if (extdeg > 1)
prune (vminpoly);
return Factorlist;
}
}
else // char 0
{
Variable vminpoly;
Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
if (!isRat && getCharacteristic() == 0)
Off (SW_RATIONAL);
return Factorlist;
}
return CFFList (CFFactor(f,1));
}
pp
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f ).
Definition cf_gcd.cc:676
IntList
List< int > IntList
Definition canonicalform.h:401
Varlist
List< Variable > Varlist
Definition canonicalform.h:403
merge
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
Definition cfNewtonPolygon.cc:230
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition canonicalform.cc:593
List::append
void append(const T &)
Definition ftmpl_list.cc:256
Variable::level
int level() const
Definition factory.h:143
varsInAs
Varlist varsInAs(const Varlist &uord, const CFList &Astar)
Definition facAlgFuncUtil.cc:66
divide
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
Definition facAlgFuncUtil.cc:496
getDegOfExt
int getDegOfExt(IntList &degreelist, int n)
Definition facAlgFuncUtil.cc:539
isInseparable
bool isInseparable(const CFList &Astar)
Definition facAlgFuncUtil.cc:518
generateMipo
CanonicalForm generateMipo(int degOfExt)
Definition facAlgFuncUtil.cc:90
alg_gcd
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
Definition facAlgFunc.cc:61
SteelTrager
CFFList SteelTrager(const CanonicalForm &f, const CFList &AS)
algorithm of A. Steel described in "Conquering Inseparability: Primarydecomposition and multivariate ...
Definition facAlgFunc.cc:759
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
rootOf
Variable FACTORY_PUBLIC rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition variable.cc:162
prune
void FACTORY_PUBLIC prune(Variable &alpha)
Definition variable.cc:261
multiplicity
STATIC_VAR int * multiplicity
Definition interpolation.cc:86

## factorize() [1/2]

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

factorization over or

Definition at line 409 of file cf_factor.cc.

{
if ( f.inCoeffDomain() )
return CFFList( f );
#ifndef NOASSERT
Variable a;
ASSERT (!hasFirstAlgVar (f, a), "f has an algebraic variable use factorize \
( const CanonicalForm & f, const Variable & alpha ) instead");
#endif
//out_cf("factorize:",f,"==================================\n");
if (! f.isUnivariate() ) // preprocess homog. polys
{
if ( singular_homog_flag && f.isHomogeneous())
{
Variable xn = get_max_degree_Variable(f);
int d_xn = degree(f,xn);
CFMap n;
CanonicalForm F = compress(f(1,xn),n);
CFFList Intermediatelist;
Intermediatelist = factorize(F);
CFFList Homoglist;
CFFListIterator j;
for ( j=Intermediatelist; j.hasItem(); j++ )
{
Homoglist.append(
CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
}
CFFList Unhomoglist;
CanonicalForm unhomogelem;
for ( j=Homoglist; j.hasItem(); j++ )
{
unhomogelem= homogenize(j.getItem().factor(),xn);
Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
}
if ( d_xn != 0 ) // have to append xn^(d_xn)
Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF);
return Unhomoglist;
}
}
CFFList F;
if ( getCharacteristic() > 0 )
{
if (f.isUnivariate())
{
#ifdef HAVE_FLINT
#ifdef HAVE_NTL
if (degree (f) < 300)
#endif
{
// use FLINT: char p, univariate
nmod_poly_t f1;
convertFacCF2nmod_poly_t (f1, f);
nmod_poly_factor_t result;
nmod_poly_factor_init (result);
mp_limb_t leadingCoeff= nmod_poly_factor (result, f1);
F= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, f.mvar());
nmod_poly_factor_clear (result);
nmod_poly_clear (f1);
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
}
#endif
#ifdef HAVE_NTL
{ // NTL char 2, univariate
if (getCharacteristic()==2)
{
// Specialcase characteristic==2
if (fac_NTL_char != 2)
{
fac_NTL_char = 2;
zz_p::init(2);
}
// convert to NTL using the faster conversion routine for characteristic 2
GF2X f1=convertFacCF2NTLGF2X(f);
// no make monic necessary in GF2
//factorize
vec_pair_GF2X_long factors;
CanZass(factors,f1);
// convert back to factory again using the faster conversion routine for vectors over GF2X
F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
}
}
#endif
#ifdef HAVE_NTL
{
// use NTL char p, univariate
if (fac_NTL_char != getCharacteristic())
{
fac_NTL_char = getCharacteristic();
zz_p::init(getCharacteristic());
}
// convert to NTL
zz_pX f1=convertFacCF2NTLzzpX(f);
zz_p leadcoeff = LeadCoeff(f1);
//make monic
f1=f1 / LeadCoeff(f1);
// factorize
vec_pair_zz_pX_long factors;
CanZass(factors,f1);
F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
//test_cff(F,f);
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
}
#endif
#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
// Use Factory without NTL and without FLINT: char p, univariate
{
if ( isOn( SW_BERLEKAMP ) )
F=FpFactorizeUnivariateB( f, issqrfree );
else
F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() );
return F;
}
#endif
}
else // char p, multivariate
{
if (CFFactory::gettype() == GaloisFieldDomain)
{
#if defined(HAVE_NTL)
if (issqrfree)
{
CFList factors;
Variable alpha;
factors= GFSqrfFactorize (f);
for (CFListIterator i= factors; i.hasItem(); i++)
F.append (CFFactor (i.getItem(), 1));
}
else
{
Variable alpha;
F= GFFactorize (f);
}
#else
factoryError ("multivariate factorization over GF depends on NTL(missing)");
return CFFList (CFFactor (f, 1));
#endif
}
else
{
#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
if (!isOn(SW_USE_FL_FAC_P))
{
#endif
#if defined(HAVE_NTL)
if (issqrfree)
{
CFList factors;
Variable alpha;
factors= FpSqrfFactorize (f);
for (CFListIterator i= factors; i.hasItem(); i++)
F.append (CFFactor (i.getItem(), 1));
goto end_charp;
}
else
{
Variable alpha;
F= FpFactorize (f);
goto end_charp;
}
#endif
#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
}
#endif
#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
nmod_mpoly_ctx_t ctx;
nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,getCharacteristic());
nmod_mpoly_t Flint_f;
nmod_mpoly_init(Flint_f,ctx);
convFactoryPFlintMP(f,Flint_f,ctx,f.level());
nmod_mpoly_factor_t factors;
nmod_mpoly_factor_init(factors,ctx);
int okay;
if (issqrfree) okay=nmod_mpoly_factor_squarefree(factors,Flint_f,ctx);
else okay=nmod_mpoly_factor(factors,Flint_f,ctx);
nmod_mpoly_t fac;
nmod_mpoly_init(fac,ctx);
CanonicalForm cf_fac;
int cf_exp;
cf_fac=nmod_mpoly_factor_get_constant_ui(factors,ctx);
F.append(CFFactor(cf_fac,1));
for(int i=nmod_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
{
nmod_mpoly_factor_get_base(fac,factors,i,ctx);
cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
cf_exp=nmod_mpoly_factor_get_exp_si(factors,i,ctx);
F.append(CFFactor(cf_fac,cf_exp));
}
nmod_mpoly_factor_clear(factors,ctx);
nmod_mpoly_clear(Flint_f,ctx);
nmod_mpoly_ctx_clear(ctx);
if (okay==0)
{
Off(SW_USE_FL_GCD_P);
Off(SW_USE_FL_FAC_P);
F=factorize(f,issqrfree);
On(SW_USE_FL_GCD_P);
On(SW_USE_FL_FAC_P);
}
#endif
#if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
#ifndef HAVE_NTL
factoryError ("multivariate factorization depends on NTL/FLINT(missing)");
return CFFList (CFFactor (f, 1));
#endif
#endif
}
}
}
else // char 0
{
bool on_rational = isOn(SW_RATIONAL);
On(SW_RATIONAL);
CanonicalForm cd = bCommonDen( f );
CanonicalForm fz = f * cd;
Off(SW_RATIONAL);
if ( f.isUnivariate() )
{
CanonicalForm ic=icontent(fz);
fz/=ic;
if (fz.degree()==1)
{
F=CFFList(CFFactor(fz,1));
F.insert(CFFactor(ic,1));
}
else
#if defined(HAVE_FLINT) && (__FLINT_RELEASE>=20503) && (__FLINT_RELEASE!= 20600)
{
// FLINT 2.6.0 has a bug:
// factorize x^12-13*x^10-13*x^8+13*x^4+13*x^2-1 runs forever
// use FLINT: char 0, univariate
fmpz_poly_t f1;
convertFacCF2Fmpz_poly_t (f1, fz);
fmpz_poly_factor_t result;
fmpz_poly_factor_init (result);
fmpz_poly_factor(result, f1);
F= convertFLINTfmpz_poly_factor2FacCFFList (result, fz.mvar());
fmpz_poly_factor_clear (result);
fmpz_poly_clear (f1);
if ( ! ic.isOne() )
{
// according to convertFLINTfmpz_polyfactor2FcaCFFlist,
// first entry is in CoeffDomain
CFFactor new_first( F.getFirst().factor() * ic );
F.removeFirst();
F.insert( new_first );
}
}
goto end_char0;
#elif defined(HAVE_NTL)
{
//use NTL
ZZ c;
vec_pair_ZZX_long factors;
//factorize the converted polynomial
factor(c,factors,convertFacCF2NTLZZX(fz));
//convert the result back to Factory
F=convertNTLvec_pair_ZZX_long2FacCFFList(factors,c,fz.mvar());
if ( ! ic.isOne() )
{
// according to convertNTLvec_pair_ZZX_long2FacCFFList
// first entry is in CoeffDomain
CFFactor new_first( F.getFirst().factor() * ic );
F.removeFirst();
F.insert( new_first );
}
}
goto end_char0;
#else
{
//Use Factory without NTL: char 0, univariate
F = ZFactorizeUnivariate( fz, issqrfree );
goto end_char0;
}
#endif
}
else // multivariate, char 0
{
#if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
if (isOn(SW_USE_FL_FAC_0))
{
On (SW_RATIONAL);
fmpz_mpoly_ctx_t ctx;
fmpz_mpoly_ctx_init(ctx,f.level(),ORD_LEX);
fmpz_mpoly_t Flint_f;
fmpz_mpoly_init(Flint_f,ctx);
convFactoryPFlintMP(fz,Flint_f,ctx,fz.level());
fmpz_mpoly_factor_t factors;
fmpz_mpoly_factor_init(factors,ctx);
int rr;
if (issqrfree) rr=fmpz_mpoly_factor_squarefree(factors,Flint_f,ctx);
else rr=fmpz_mpoly_factor(factors,Flint_f,ctx);
if (rr==0) printf("fail\n");
fmpz_mpoly_t fac;
fmpz_mpoly_init(fac,ctx);
CanonicalForm cf_fac;
int cf_exp;
fmpz_t c;
fmpz_init(c);
fmpz_mpoly_factor_get_constant_fmpz(c,factors,ctx);
cf_fac=convertFmpz2CF(c);
fmpz_clear(c);
F.append(CFFactor(cf_fac,1));
for(int i=fmpz_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
{
fmpz_mpoly_factor_get_base(fac,factors,i,ctx);
cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
cf_exp=fmpz_mpoly_factor_get_exp_si(factors,i,ctx);
F.append(CFFactor(cf_fac,cf_exp));
}
fmpz_mpoly_factor_clear(factors,ctx);
fmpz_mpoly_clear(Flint_f,ctx);
fmpz_mpoly_ctx_clear(ctx);
goto end_char0;
}
#endif
#if defined(HAVE_NTL)
On (SW_RATIONAL);
if (issqrfree)
{
CFList factors= ratSqrfFactorize (fz);
for (CFListIterator i= factors; i.hasItem(); i++)
F.append (CFFactor (i.getItem(), 1));
}
else
{
F = ratFactorize (fz);
}
#endif
#if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
#ifndef HAVE_NTL
F=ZFactorizeMultivariate(fz, issqrfree);
#endif
#endif
}
end_char0:
if ( on_rational )
On(SW_RATIONAL);
else
Off(SW_RATIONAL);
if ( ! cd.isOne() )
{
CFFactor new_first( F.getFirst().factor() / cd );
F.removeFirst();
F.insert( new_first );
}
}
#if defined(HAVE_NTL)
end_charp:
#endif
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
}
convertFmpz2CF
CanonicalForm convertFmpz2CF(const fmpz_t coefficient)
conversion of a FLINT integer to CanonicalForm
Definition FLINTconvert.cc:154
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:337
convertFacCF2Fmpz_poly_t
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
Definition FLINTconvert.cc:146
convertFLINTfmpz_poly_factor2FacCFFList
CFFList convertFLINTfmpz_poly_factor2FacCFFList(const fmpz_poly_factor_t fac, const Variable &x)
conversion of a FLINT factorization over Z to a CFFList
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:446
convertNTLvec_pair_zzpX_long2FacCFFList
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p cont, const Variable &x)
Definition NTLconvert.cc:399
convertFacCF2NTLGF2X
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Definition NTLconvert.cc:184
convertNTLvec_pair_ZZX_long2FacCFFList
CFFList convertNTLvec_pair_ZZX_long2FacCFFList(const vec_pair_ZZX_long &e, const ZZ &cont, const Variable &x)
NAME: convertNTLvec_pair_ZZX_long2FacCFFList.
Definition NTLconvert.cc:753
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition cf_ops.cc:679
cd
CanonicalForm cd(bCommonDen(FF))
Definition cfModGcd.cc:4097
singular_homog_flag
EXTERN_VAR int singular_homog_flag
Definition cf_algorithm.h:65
SW_USE_FL_GCD_P
static const int SW_USE_FL_GCD_P
set to 1 to use Flints gcd over F_p
Definition cf_defs.h:47
SW_USE_NTL_SORT
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition cf_defs.h:39
SW_USE_FL_FAC_0
static const int SW_USE_FL_FAC_0
set to 1 to prefer flints multivariate factorization over Z/p
Definition cf_defs.h:57
SW_USE_FL_FAC_P
static const int SW_USE_FL_FAC_P
set to 1 to prefer flints multivariate factorization over Z/p
Definition cf_defs.h:55
SW_BERLEKAMP
static const int SW_BERLEKAMP
set to 1 to use Factorys Berlekamp alg.
Definition cf_defs.h:51
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:264
cmpCF
int cmpCF(const CFFactor &f, const CFFactor &g)
Definition cf_factor.cc:398
homogenize
CanonicalForm homogenize(const CanonicalForm &f, const Variable &x)
homogenize homogenizes f with Variable x
Definition cf_factor.cc:317
factorize
CFFList factorize(const CanonicalForm &f, bool issqrfree)
factorization over or
Definition cf_factor.cc:409
compress
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m ).
Definition cf_map.cc:210
CanonicalForm::degree
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
Definition canonicalform.cc:414
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
List::sort
void sort(int(*)(const T &, const T &))
Definition ftmpl_list.cc:339
List::insert
void insert(const T &)
Definition ftmpl_list.cc:193
alpha
Variable alpha
Definition facAbsBiFact.cc:52
factor
CanonicalForm factor
Definition facAbsFact.cc:97
ratFactorize
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
Definition facFactorize.h:79
ratSqrfFactorize
CFList ratSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree multivariate polynomial over
Definition facFactorize.h:53
FpSqrfFactorize
CFList FpSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over
Definition facFqFactorize.h:47
FpFactorize
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
Definition facFqFactorize.h:101
GFFactorize
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
Definition facFqFactorize.h:267
GFSqrfFactorize
CFList GFSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over GF
Definition facFqFactorize.h:82
FpFactorizeUnivariateB
CFFList FpFactorizeUnivariateB(const CanonicalForm &f, bool issqrfree=false)
FpFactorizeUnivariateCZ
CFFList FpFactorizeUnivariateCZ(const CanonicalForm &f, bool issqrfree, int numext, const Variable alpha, const Variable beta)
ZFactorizeMultivariate
CFFList ZFactorizeMultivariate(const CanonicalForm &f, bool issqrfree)
ZFactorizeUnivariate
CFFList ZFactorizeUnivariate(const CanonicalForm &ff, bool issqrfree=false)
xn
VAR int xn
Definition walk.cc:4509

## factorize() [2/2]

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

factorization over or

Definition at line 778 of file cf_factor.cc.

{
if ( f.inCoeffDomain() )
return CFFList( f );
//out_cf("factorize:",f,"==================================\n");
//out_cf("mipo:",getMipo(alpha),"\n");
CFFList F;
ASSERT( alpha.level() < 0 && getReduce (alpha), "not an algebraic extension" );
#ifndef NOASSERT
Variable beta;
if (hasFirstAlgVar(f, beta))
ASSERT (beta == alpha, "f has an algebraic variable that \
does not coincide with alpha");
#endif
int ch=getCharacteristic();
if (ch>0)
{
if (f.isUnivariate())
{
#ifdef HAVE_NTL
if (/*getCharacteristic()*/ch==2)
{
// special case : GF2
// remainder is two ==> nothing to do
// set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
GF2E::init (minPo);
// convert to NTL again using the faster conversion routines
GF2EX f1;
if (isPurePoly(f))
{
GF2X f_tmp=convertFacCF2NTLGF2X(f);
f1=to_GF2EX(f_tmp);
}
else
f1=convertFacCF2NTLGF2EX(f,minPo);
// make monic (in Z/2(a))
GF2E f1_coef=LeadCoeff(f1);
MakeMonic(f1);
// factorize using NTL
vec_pair_GF2EX_long factors;
CanZass(factors,f1);
// return converted result
F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
}
#endif
#if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
{
// use FLINT
nmod_poly_t FLINTmipo, leadingCoeff;
fq_nmod_ctx_t fq_con;
nmod_poly_init (FLINTmipo, ch);
nmod_poly_init (leadingCoeff, ch);
convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
fq_nmod_poly_t FLINTF;
convertFacCF2Fq_nmod_poly_t (FLINTF, f, fq_con);
fq_nmod_poly_factor_t res;
fq_nmod_poly_factor_init (res, fq_con);
fq_nmod_poly_factor (res, leadingCoeff, FLINTF, fq_con);
F= convertFLINTFq_nmod_poly_factor2FacCFFList (res, f.mvar(), alpha, fq_con);
F.insert (CFFactor (Lc (f), 1));
fq_nmod_poly_factor_clear (res, fq_con);
fq_nmod_poly_clear (FLINTF, fq_con);
nmod_poly_clear (FLINTmipo);
nmod_poly_clear (leadingCoeff);
fq_nmod_ctx_clear (fq_con);
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
}
#endif
#ifdef HAVE_NTL
{
// use NTL
if (fac_NTL_char != ch)
{
fac_NTL_char = ch;
zz_p::init(ch);
}
// set minimal polynomial in NTL
zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
zz_pE::init (minPo);
// convert to NTL
zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
zz_pE leadcoeff= LeadCoeff(f1);
//make monic
f1=f1 / leadcoeff; //leadcoeff==LeadCoeff(f1);
// factorize
vec_pair_zz_pEX_long factors;
CanZass(factors,f1);
// return converted result
F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
//test_cff(F,f);
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
}
#endif
#if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
// char p, extension, univariate
CanonicalForm c=Lc(f);
CanonicalForm fc=f/c;
F=FpFactorizeUnivariateCZ( fc, false, 1, alpha, Variable() );
F.insert (CFFactor (c, 1));
#endif
}
else // char p, multivariate
{
#if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
// use FLINT
nmod_poly_t FLINTmipo;
fq_nmod_ctx_t fq_con;
fq_nmod_mpoly_ctx_t ctx;
nmod_poly_init (FLINTmipo, ch);
convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
fq_nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,fq_con);
fq_nmod_mpoly_t FLINTF;
fq_nmod_mpoly_init(FLINTF,ctx);
convertFacCF2Fq_nmod_mpoly_t(FLINTF,f,ctx,f.level(),fq_con);
fq_nmod_mpoly_factor_t res;
fq_nmod_mpoly_factor_init (res, ctx);
fq_nmod_mpoly_factor (res, FLINTF, ctx);
F= convertFLINTFq_nmod_mpoly_factor2FacCFFList (res, ctx,f.level(),fq_con,alpha);
//F.insert (CFFactor (Lc (f), 1));
fq_nmod_mpoly_factor_clear (res, ctx);
fq_nmod_mpoly_clear (FLINTF, ctx);
nmod_poly_clear (FLINTmipo);
fq_nmod_mpoly_ctx_clear (ctx);
fq_nmod_ctx_clear (fq_con);
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
#elif defined(HAVE_NTL)
F= FqFactorize (f, alpha);
#else
factoryError ("multivariate factorization over Z/pZ(alpha) depends on NTL/Flint(missing)");
return CFFList (CFFactor (f, 1));
#endif
}
}
else // Q(a)[x]
{
if (f.isUnivariate())
{
F= AlgExtFactorize (f, alpha);
}
else //Q(a)[x1,...,xn]
{
#if defined(HAVE_NTL) || defined(HAVE_FLINT)
F= ratFactorize (f, alpha);
#else
factoryError ("multivariate factorization over Q(alpha) depends on NTL or FLINT (missing)");
return CFFList (CFFactor (f, 1));
#endif
}
}
if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
return F;
}
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:379
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:526
convertFacCF2NTLzz_pEX
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition NTLconvert.cc:1064
convertNTLvec_pair_zzpEX_long2FacCFFList
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &cont, const Variable &x, const Variable &alpha)
Definition NTLconvert.cc:870
convertNTLvec_pair_GF2EX_long2FacCFFList
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &cont, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
Definition NTLconvert.cc:959
convertFacCF2NTLGF2EX
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
Definition NTLconvert.cc:1007
isPurePoly
bool isPurePoly(const CanonicalForm &f)
Definition cf_factor.cc:248
res
CanonicalForm res
Definition facAbsFact.cc:60
beta
Variable beta
Definition facAbsFact.cc:95
AlgExtFactorize
CFFList AlgExtFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a univariate polynomial over algebraic extension of Q
Definition facAlgExt.cc:370
FqFactorize
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
Definition facFqFactorize.h:184
fq_con
fq_nmod_ctx_t fq_con
Definition facHensel.cc:99
fq_nmod_ctx_clear
fq_nmod_ctx_clear(fq_con)
fq_nmod_ctx_init_modulus
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
fq_nmod_poly_clear
fq_nmod_poly_clear(prod, fq_con)
getMipo
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition variable.cc:207

## factoryError_intern()

void factoryError_intern | ( | const char * | s | ) |

Definition at line 75 of file cf_util.cc.

{
fputs(s,stderr);
abort();
}

## factoryrandom()

int factoryrandom | ( | int | n | ) |

random integers with abs less than n

Definition at line 177 of file cf_random.cc.

{
if ( n == 0 )
return (int)ranGen.generate();
else
return ranGen.generate() % n;
}
ranGen
INST_VAR RandomGenerator ranGen
Definition cf_random.cc:63

## factoryseed()

void FACTORY_PUBLIC factoryseed | ( | int | s | ) |

random seed initializer

Definition at line 186 of file cf_random.cc.

{
ranGen.seed( s );
#ifdef HAVE_FLINT
#if (__FLINT_RELEASE>=30300)
flint_rand_init(FLINTrandom);
#else
flint_randinit(FLINTrandom);
#endif
#endif
}
FLINTrandom
GLOBAL_VAR flint_rand_t FLINTrandom
Definition cf_random.cc:23

## Farey()

CanonicalForm Farey | ( | const CanonicalForm & | f,
|  | const CanonicalForm & | q )

Farey rational reconstruction.

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

Definition at line 202 of file cf_chinese.cc.

{
int is_rat=isOn(SW_RATIONAL);
Off(SW_RATIONAL);
Variable x = f.mvar();
CanonicalForm result = 0;
CanonicalForm c;
CFIterator i;
#ifdef HAVE_FLINT
fmpz_t FLINTq;
fmpz_init(FLINTq);
convertCF2initFmpz(FLINTq,q);
fmpz_t FLINTc;
fmpz_init(FLINTc);
fmpq_t FLINTres;
fmpq_init(FLINTres);
#elif defined(HAVE_NTL)
ZZ NTLq= convertFacCF2NTLZZ (q);
ZZ bound;
SqrRoot (bound, NTLq/2);
#else
factoryError("NTL/FLINT missing:Farey");
#endif
for ( i = f; i.hasTerms(); i++ )
{
c = i.coeff();
if ( c.inCoeffDomain())
{
#ifdef HAVE_FLINT
if (c.inZ())
{
convertCF2initFmpz(FLINTc,c);
fmpq_reconstruct_fmpz(FLINTres,FLINTc,FLINTq);
result += power (x, i.exp())*(convertFmpq2CF(FLINTres));
}
#elif defined(HAVE_NTL)
if (c.inZ())
{
ZZ NTLc= convertFacCF2NTLZZ (c);
bool lessZero= (sign (NTLc) == -1);
if (lessZero)
NTL::negate (NTLc, NTLc);
ZZ NTLnum, NTLden;
if (ReconstructRational (NTLnum, NTLden, NTLc, NTLq, bound, bound))
{
if (lessZero)
NTL::negate (NTLnum, NTLnum);
CanonicalForm num= convertNTLZZX2CF (to_ZZX (NTLnum), Variable (1));
CanonicalForm den= convertNTLZZX2CF (to_ZZX (NTLden), Variable (1));
On (SW_RATIONAL);
result += power (x, i.exp())*(num/den);
Off (SW_RATIONAL);
}
}
#else
if (c.inZ())
result += power (x, i.exp()) * Farey_n(c,q);
#endif
else
result += power( x, i.exp() ) * Farey(c,q);
}
else
result += power( x, i.exp() ) * Farey(c,q);
}
if (is_rat) On(SW_RATIONAL);
#ifdef HAVE_FLINT
fmpq_clear(FLINTres);
fmpz_clear(FLINTc);
fmpz_clear(FLINTq);
#endif
return result;
}
convertFmpq2CF
CanonicalForm convertFmpq2CF(const fmpq_t q)
conversion of a FLINT rational to CanonicalForm
Definition FLINTconvert.cc:260
convertCF2initFmpz
void convertCF2initFmpz(fmpz_t result, const CanonicalForm &f)
conversion of a factory integer to fmpz_t(init.)
Definition FLINTconvert.cc:133
num
CanonicalForm num(const CanonicalForm &f)
Definition canonicalform.h:337
den
CanonicalForm den(const CanonicalForm &f)
Definition canonicalform.h:340
Farey
CanonicalForm Farey(const CanonicalForm &f, const CanonicalForm &q)
Farey rational reconstruction.
Definition cf_chinese.cc:202
bound
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
CanonicalForm::inZ
bool inZ() const
predicates
Definition canonicalform.cc:69

## fdivides() [1/2]

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

## fdivides() [2/2]

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

## gcd()

CanonicalForm FACTORY_PUBLIC gcd | ( | const CanonicalForm & | f,
|  | const CanonicalForm & | g )

Definition at line 685 of file cf_gcd.cc.

{
bool b = f.isZero();
if ( b || g.isZero() )
{
if ( b )
return abs( g );
else
return abs( f );
}
if ( f.inPolyDomain() || g.inPolyDomain() )
{
if ( f.mvar() != g.mvar() )
{
if ( f.mvar() > g.mvar() )
return cf_content( f, g );
else
return cf_content( g, f );
}
if (isOn(SW_USE_QGCD))
{
Variable m;
if (
(getCharacteristic() == 0) &&
(hasFirstAlgVar(f,m) || hasFirstAlgVar(g,m))
)
{
bool on_rational = isOn(SW_RATIONAL);
CanonicalForm r=QGCD(f,g);
On(SW_RATIONAL);
CanonicalForm cdF = bCommonDen( r );
if (!on_rational) Off(SW_RATIONAL);
return cdF*r;
}
}
if ( f.inExtension() && getReduce( f.mvar() ) )
return CanonicalForm(1);
else
{
if ( fdivides( f, g ) )
return abs( f );
else if ( fdivides( g, f ) )
return abs( g );
if ( !( getCharacteristic() == 0 && isOn( SW_RATIONAL ) ) )
{
CanonicalForm d;
d = gcd_poly( f, g );
return abs( d );
}
else
{
CanonicalForm cdF = bCommonDen( f );
CanonicalForm cdG = bCommonDen( g );
CanonicalForm F = f * cdF, G = g * cdG;
Off( SW_RATIONAL );
CanonicalForm l = gcd_poly( F, G );
On( SW_RATIONAL );
return abs( l );
}
}
}
if ( f.inBaseDomain() && g.inBaseDomain() )
return bgcd( f, g );
else
return 1;
}
QGCD
CanonicalForm QGCD(const CanonicalForm &F, const CanonicalForm &G)
gcd over Q(a)
Definition cfGcdAlgExt.cc:731
fdivides
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
SW_USE_QGCD
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition cf_defs.h:43
gcd_poly
CanonicalForm gcd_poly(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g ).
Definition cf_gcd.cc:492

## gcd_poly()

CanonicalForm FACTORY_PUBLIC 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 492 of file cf_gcd.cc.

{
CanonicalForm fc, gc;
bool fc_isUnivariate=f.isUnivariate();
bool gc_isUnivariate=g.isUnivariate();
bool fc_and_gc_Univariate=fc_isUnivariate && gc_isUnivariate;
fc = f;
gc = g;
int ch=getCharacteristic();
if ( ch != 0 )
{
if (0) {} // dummy, to be able to build without NTL and FLINT
#if defined(HAVE_FLINT) && ( __FLINT_RELEASE >= 20503)
if ( isOn( SW_USE_FL_GCD_P)
&& (CFFactory::gettype() != GaloisFieldDomain)
#ifdef HAVE_NTL
&& (ch>10) // if we have NTL: it is better for char <11
#endif
&&(!hasAlgVar(fc)) && (!hasAlgVar(gc)))
{
return gcdFlintMP_Zp(fc,gc);
}
#endif
#ifdef HAVE_NTL
if ((!fc_and_gc_Univariate) && (isOn( SW_USE_EZGCD_P )))
{
fc= EZGCD_P (fc, gc);
}
#endif
#if defined(HAVE_NTL) || defined(HAVE_FLINT)
else if (isOn(SW_USE_FF_MOD_GCD) && !fc_and_gc_Univariate)
{
Variable a;
if (hasFirstAlgVar (fc, a) || hasFirstAlgVar (gc, a))
fc=modGCDFq (fc, gc, a);
else if (CFFactory::gettype() == GaloisFieldDomain)
fc=modGCDGF (fc, gc);
else
fc=modGCDFp (fc, gc);
}
#endif
else
fc = gcd_poly_p( fc, gc );
}
else if (!fc_and_gc_Univariate) /* && char==0*/
{
#if defined(HAVE_FLINT) && ( __FLINT_RELEASE >= 20503)
if (( isOn( SW_USE_FL_GCD_0) )
&&(!hasAlgVar(fc)) && (!hasAlgVar(gc)))
{
return gcdFlintMP_QQ(fc,gc);
}
else
#endif
#ifdef HAVE_NTL
if ( isOn( SW_USE_EZGCD ) )
fc= ezgcd (fc, gc);
else
#endif
#if defined(HAVE_NTL) || defined(HAVE_FLINT)
if (isOn(SW_USE_CHINREM_GCD))
fc = modGCDZ( fc, gc);
else
#endif
{
fc = gcd_poly_0( fc, gc );
}
}
else
{
fc = gcd_poly_0( fc, gc );
}
if ((ch>0)&&(!hasAlgVar(fc))) fc/=fc.lc();
return fc;
}
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:876
ezgcd
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
Definition cfEzgcd.cc:498
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:479
modGCDFp
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
Definition cfModGcd.cc:1224
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 forComputer Algebra" by Geddes...
Definition cfModGcd.cc:873
modGCDZ
CanonicalForm modGCDZ(const CanonicalForm &FF, const CanonicalForm &GG)
modular GCD over Z
SW_USE_CHINREM_GCD
static const int SW_USE_CHINREM_GCD
set to 1 to use modular gcd over Z
Definition cf_defs.h:41
SW_USE_EZGCD_P
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
Definition cf_defs.h:37
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:45
SW_USE_EZGCD
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
Definition cf_defs.h:35
SW_USE_FL_GCD_0
static const int SW_USE_FL_GCD_0
set to 1 to use Flints gcd over Q/Z
Definition cf_defs.h:49
gcd_poly_0
static CanonicalForm gcd_poly_0(const CanonicalForm &f, const CanonicalForm &g)
Definition cf_gcd.cc:417
gcd_poly_p
static CanonicalForm gcd_poly_p(const CanonicalForm &f, const CanonicalForm &g)
Definition cf_gcd.cc:264
CanonicalForm::lc
CanonicalForm lc() const
CanonicalForm CanonicalForm::lc (), Lc (), LC (), LC ( v ) const.
Definition canonicalform.cc:337
hasAlgVar
int hasAlgVar(const CanonicalForm &f, const Variable &v)
Definition facAlgFuncUtil.cc:322

## get_max_degree_Variable()

Variable get_max_degree_Variable | ( | const CanonicalForm & | f | ) |

get_max_degree_Variable returns Variable with highest degree.

We assume f is not a constant!

Definition at line 264 of file cf_factor.cc.

{
ASSERT( ( ! f.inCoeffDomain() ), "no constants" );
int max=0, maxlevel=0, n=level(f);
for ( int i=1; i<=n; i++ )
{
if (degree(f,Variable(i)) >= max)
{
max= degree(f,Variable(i)); maxlevel= i;
}
}
return Variable(maxlevel);
}
max
static int max(int a, int b)
Definition fast_mult.cc:264

## get_Terms()

CFList get_Terms | ( | const CanonicalForm & | f | ) |

Definition at line 293 of file cf_factor.cc.

{
CFList result,dummy,dummy2;
CFIterator i;
CFListIterator j;
if ( getNumVars(f) == 0 ) result.append(f);
else{
Variable _x(level(f));
for ( i=f; i.hasTerms(); i++ ){
getTerms(i.coeff(), 1, dummy);
for ( j=dummy; j.hasItem(); j++ )
result.append(j.getItem() * power(_x, i.exp()));
dummy= dummy2; // have to initalize new
}
}
return result;
}
getNumVars
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition cf_ops.cc:314
getTerms
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
Definition cf_factor.cc:283

## getCharacteristic()

int FACTORY_PUBLIC getCharacteristic | ( |  | ) |

Definition at line 70 of file cf_char.cc.

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

## getDefaultExtName()

char getDefaultExtName | ( |  | ) |

Definition at line 249 of file variable.cc.

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

## getDefaultVarName()

char getDefaultVarName | ( |  | ) |

Definition at line 244 of file variable.cc.

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

## getGFDegree()

int getGFDegree | ( |  | ) |

Definition at line 75 of file cf_char.cc.

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

## getGFGenerator()

CanonicalForm getGFGenerator | ( |  | ) |

Definition at line 81 of file cf_char.cc.

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

## getMipo()

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

Definition at line 207 of file variable.cc.

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

## getNumVars()

int getNumVars | ( | const CanonicalForm & | f | ) |

int getNumVars ( const CanonicalForm & f )

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

Definition at line 314 of file cf_ops.cc.

{
int n;
if ( f.inCoeffDomain() )
return 0;
else if ( (n = f.level()) == 1 )
return 1;
else
{
int * vars = NEW_ARRAY(int, n+1);
int i;
for ( i = n-1; i >=0; i-- ) vars[i] = 0;
// look for variables
for ( CFIterator I = f; I.hasTerms(); ++I )
fillVarsRec( I.coeff(), vars );
// count them
int m = 0;
for ( i = 1; i < n; i++ )
if ( vars[i] != 0 ) m++;
DELETE_ARRAY(vars);
// do not forget to count our own variable
return m+1;
}
}
fillVarsRec
static void fillVarsRec(const CanonicalForm &f, int *vars)
static void fillVarsRec ( const CanonicalForm & f, int * vars )
Definition cf_ops.cc:296

## getTerms()

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

get_Terms: Split the polynomial in the containing terms.

getTerms: the real work is done here.

Definition at line 283 of file cf_factor.cc.

{
if ( getNumVars(f) == 0 ) result.append(f*t);
else{
Variable x(level(f));
for ( CFIterator i=f; i.hasTerms(); i++ )
getTerms( i.coeff(), t*power(x,i.exp()), result);
}
}

## 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.

{
int n;
if ( f.inCoeffDomain() )
return 1;
else if ( (n = f.level()) == 1 )
return Variable( 1 );
else
{
int * vars = NEW_ARRAY(int, n+1);
int i;
for ( i = n; i >= 0; i-- ) vars[i] = 0;
// look for variables
for ( CFIterator I = f; I.hasTerms(); ++I )
fillVarsRec( I.coeff(), vars );
// multiply them all
CanonicalForm result = 1;
for ( i = n; i > 0; i-- )
if ( vars[i] != 0 ) result *= Variable( i );
DELETE_ARRAY(vars);
// do not forget our own variable
return f.mvar() * result;
}
}

## gf_gf2ff() [1/2]

int gf_gf2ff | ( | int | a | ) |

Definition at line 231 of file gfops.cc.

{
if ( gf_iszero( a ) )
return 0;
else
{
// starting from z^0=1, step through the table
// counting the steps until we hit z^a or z^0
// again. since we are working in char(p), the
// latter is guaranteed to be fulfilled.
int i = 0, ff = 1;
do
{
if ( i == a )
return ff;
ff++;
i = gf_table[i];
} while ( i != 0 );
return -1;
}
}
gf_table
VAR unsigned short * gf_table
Definition gfops.cc:54
gf_iszero
bool gf_iszero(int a)
Definition gfops.h:43

## gf_gf2ff() [2/2]

long gf_gf2ff | ( | long | a | ) |

Definition at line 209 of file gfops.cc.

{
if ( gf_iszero( a ) )
return 0;
else
{
// starting from z^0=1, step through the table
// counting the steps until we hit z^a or z^0
// again. since we are working in char(p), the
// latter is guaranteed to be fulfilled.
long i = 0, ff = 1;
do
{
if ( i == a )
return ff;
ff++;
i = gf_table[i];
} while ( i != 0 );
return -1;
}
}

## gf_isff() [1/2]

bool gf_isff | ( | int | a | ) |

Definition at line 264 of file gfops.cc.

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

## gf_isff() [2/2]

bool gf_isff | ( | long | a | ) |

Definition at line 253 of file gfops.cc.

{
if ( gf_iszero( a ) )
return true;
else
{
// z^a in GF(p) iff (z^a)^p-1=1
return gf_isone( gf_power( a, gf_p - 1 ) );
}
}

## gf_value()

int gf_value | ( | const CanonicalForm & | f | ) |

Definition at line 60 of file singext.cc.

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

## gmp_denominator()

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

Definition at line 40 of file singext.cc.

{
InternalCF * ff = f.getval();
ASSERT( ! is_imm( ff ), "illegal type" );
if ( ff->levelcoeff() == IntegerDomain )
{
mpz_init_set_si( result, 1 );
ff->deleteObject();
}
else if ( ff->levelcoeff() == RationalDomain )
{
mpz_init_set( result, (InternalRational::MPQDEN( ff )) );
ff->deleteObject();
}
else
{
ASSERT( 0, "illegal type" );
}
}
is_imm
int is_imm(const InternalCF *const ptr)
Definition canonicalform.h:65
RationalDomain
#define RationalDomain
Definition cf_defs.h:20
IntegerDomain
#define IntegerDomain
Definition cf_defs.h:21
InternalCF::levelcoeff
virtual int levelcoeff() const
Definition int_cf.h:68
InternalCF::deleteObject
int deleteObject()
Definition int_cf.h:61
InternalRational::MPQDEN
static mpz_ptr MPQDEN(const InternalCF *const c)
Definition int_rat.h:143

## gmp_numerator()

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

Definition at line 20 of file singext.cc.

{
InternalCF * ff = f.getval();
ASSERT( ! is_imm( ff ), "illegal type" );
if ( ff->levelcoeff() == IntegerDomain )
{
mpz_init_set( result, (InternalInteger::MPI( ff )) );
ff->deleteObject();
}
else if ( ff->levelcoeff() == RationalDomain )
{
mpz_init_set( result, (InternalRational::MPQNUM( ff )) );
ff->deleteObject();
}
else
{
ASSERT( 0, "illegal type" );
}
}
InternalInteger::MPI
static mpz_ptr MPI(const InternalCF *const c)
uiNormalizeMPI()' is the same as normalizeMPI()' except that aMpi' is expected to be non-begative.
Definition int_int.h:252
InternalRational::MPQNUM
static mpz_ptr MPQNUM(const InternalCF *const c)
Definition int_rat.h:138

## hasFirstAlgVar()

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

check if poly f contains an algebraic variable a

Definition at line 679 of file cf_ops.cc.

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

## hasMipo()

bool hasMipo | ( | const Variable & | alpha | ) |

Definition at line 226 of file variable.cc.

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

## head()

CanonicalForm head | ( | const CanonicalForm & | f | ) |

inline

Definition at line 501 of file factory.h.

{
if ( f.level() > 0 )
return power( f.mvar(), f.degree() ) * f.LC();
else
return f;
}
power
CanonicalForm FACTORY_PUBLIC power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896

## headdegree()

int headdegree | ( | const CanonicalForm & | f | ) |

inline

Definition at line 510 of file factory.h.

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

## homogenize() [1/2]

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

homogenize homogenizes f with Variable x

Definition at line 317 of file cf_factor.cc.

{
#if 0
int maxdeg=totaldegree(f), deg;
CFIterator i;
CanonicalForm elem, result(0);
for (i=f; i.hasTerms(); i++)
{
elem= i.coeff()*power(f.mvar(),i.exp());
deg = totaldegree(elem);
if ( deg < maxdeg )
result += elem * power(x,maxdeg-deg);
else
result+=elem;
}
return result;
#else
CFList Newlist, Termlist= get_Terms(f);
int maxdeg=totaldegree(f), deg;
CFListIterator i;
CanonicalForm elem, result(0);
for (i=Termlist; i.hasItem(); i++)
{
elem= i.getItem();
deg = totaldegree(elem);
if ( deg < maxdeg )
Newlist.append(elem * power(x,maxdeg-deg));
else
Newlist.append(elem);
}
for (i=Newlist; i.hasItem(); i++) // rebuild
result += i.getItem();
return result;
#endif
}
totaldegree
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition cf_ops.cc:523
get_Terms
CFList get_Terms(const CanonicalForm &f)
Definition cf_factor.cc:293

## homogenize() [2/2]

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

Definition at line 357 of file cf_factor.cc.

{
#if 0
int maxdeg=totaldegree(f), deg;
CFIterator i;
CanonicalForm elem, result(0);
for (i=f; i.hasTerms(); i++)
{
elem= i.coeff()*power(f.mvar(),i.exp());
deg = totaldegree(elem);
if ( deg < maxdeg )
result += elem * power(x,maxdeg-deg);
else
result+=elem;
}
return result;
#else
CFList Newlist, Termlist= get_Terms(f);
int maxdeg=totaldegree(f), deg;
CFListIterator i;
CanonicalForm elem, result(0);
for (i=Termlist; i.hasItem(); i++)
{
elem= i.getItem();
deg = totaldegree(elem,v1,v2);
if ( deg < maxdeg )
Newlist.append(elem * power(x,maxdeg-deg));
else
Newlist.append(elem);
}
for (i=Newlist; i.hasItem(); i++) // rebuild
result += i.getItem();
return result;
#endif
}

## icontent()

CanonicalForm FACTORY_PUBLIC 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 74 of file cf_gcd.cc.

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

## igcd()

int igcd | ( | int | a,
|  | int | b )

Definition at line 56 of file cf_util.cc.

{
if ( a < 0 ) a = -a;
if ( b < 0 ) b = -b;
int c;
while ( b != 0 )
{
c = a % b;
a = b;
b = c;
}
return a;
}

## ilog2()

int ilog2 | ( | const CanonicalForm & | a | ) |

inline

Definition at line 493 of file factory.h.

{ return a.ilog2(); }

## ipower()

int FACTORY_PUBLIC ipower | ( | int | b,
|  | int | m )

int ipower ( int b, int m )

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

Note: Beware of overflows.

Definition at line 27 of file cf_util.cc.

{
int prod = 1;
while ( m != 0 )
{
if ( m % 2 != 0 )
prod *= b;
m /= 2;
if ( m != 0 )
b *= b;
}
return prod;
}

## irrCharSeries()

ListCFList FACTORY_PUBLIC irrCharSeries | ( | const CFList & | PS | ) |

irreducible characteristic series

Definition at line 568 of file cfCharSets.cc.

{
CanonicalForm reducible, reducible2;
CFList qs, cs, factorset, is, ts, L;
CanonicalForm sqrf;
CFFList sqrfFactors;
CFFListIterator iter2;
for (CFListIterator iter= PS; iter.hasItem(); iter++)
{
sqrf= 1;
sqrfFactors= sqrFree (iter.getItem());
if (sqrfFactors.getFirst().factor().inCoeffDomain())
sqrfFactors.removeFirst();
for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
sqrf *= iter2.getItem().factor();
sqrf= normalize (sqrf);
L= Union (CFList (sqrf), L);
}
ListCFList pi, ppi, qqi, qsi, iss, qhi= ListCFList(L);
int nr_of_iteration= 0, indexRed, highestlevel= 0;
for (CFListIterator iter= PS; iter.hasItem(); iter++)
{
if (level (iter.getItem()) > highestlevel)
highestlevel= level(iter.getItem());
}
while (!qhi.isEmpty())
{
sortListCFList (qhi);
qs= qhi.getFirst();
ListCFList ppi1,ppi2;
select (ppi, qs.length(), ppi1, ppi2);
inplaceUnion (ppi2, qqi);
if (nr_of_iteration == 0)
{
nr_of_iteration += 1;
ppi= ListCFList();
}
else
{
nr_of_iteration += 1;
ppi= Union (ppi1, ListCFList (qs));
}
StoreFactors StoredFactors;
if (qs.length() - 3 < highestlevel)
cs= modCharSet (qs, StoredFactors, false);
else
cs= charSetN (qs);
cs= removeContent (cs, StoredFactors);
factorset= StoredFactors.FS1;
if (!cs.isEmpty() && cs.getFirst().level() > 0)
{
ts= irredAS (cs, indexRed, reducible);
if (indexRed <= 0) // irreducible
{
if (!isSubset (cs,qs))
cs= charSetViaCharSetN (Union (qs,cs));
if (!find (pi, cs))
{
pi= Union (ListCFList (cs), pi);
if (cs.getFirst().level() > 0)
{
ts= irredAS (cs, indexRed, reducible);
if (indexRed <= 0) //irreducible
{
qsi= Union (ListCFList(cs), qsi);
if (cs.length() == highestlevel)
is= factorPSet (factorset);
else
is= Union (factorsOfInitials (cs), factorPSet (factorset));
iss= adjoin (is, qs, qqi);
}
}
else
iss= adjoin (factorPSet (factorset), qs, qqi);
}
else
iss= adjoin (factorPSet (factorset), qs, qqi);
}
if (indexRed > 0)
{
is= factorPSet (factorset);
if (indexRed > 1)
{
CFList cst;
for (CFListIterator i= cs ; i.hasItem(); i++)
{
if (i.getItem() == reducible)
break;
else
cst.append (i.getItem());
}
is= Union (factorsOfInitials (Union (cst, CFList (reducible))), is);
iss= Union (adjoinb (ts, qs, qqi, cst), adjoin (is, qs, qqi));
}
else
iss= adjoin (Union (is, ts), qs, qqi);
}
}
else
iss= adjoin (factorPSet (factorset), qs, qqi);
if (qhi.length() > 1)
{
qhi.removeFirst();
qhi= Union (iss, qhi);
}
else
qhi= iss;
}
if (!qsi.isEmpty())
return contract (qsi);
return ListCFList(CFList (1)) ;
}
removeContent
void removeContent(CanonicalForm &F, CanonicalForm &cF)
Definition cfCharSetsUtil.cc:776
isSubset
bool isSubset(const CFList &PS, const CFList &Cset)
is PS a subset of Cset ?
Definition cfCharSetsUtil.cc:461
adjoinb
ListCFList adjoinb(const CFList &is, const CFList &qs, const ListCFList &qh, const CFList &cs)
Definition cfCharSetsUtil.cc:533
contract
ListCFList contract(const ListCFList &cs)
Definition cfCharSetsUtil.cc:926
irredAS
static CFList irredAS(CFList &AS, int &indexRed, CanonicalForm &reducible)
Definition cfCharSets.cc:507
find
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
pi
#define pi
Definition libparse.cc:1145

## is_imm()

int is_imm | ( | const InternalCF *const | ptr | ) |

inline

Definition at line 215 of file factory.h.

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

## isOn()

bool FACTORY_PUBLIC isOn | ( | int | sw | ) |

switches

Definition at line 1971 of file canonicalform.cc.

{
return cf_glob_switches.isOn( sw );
}
cf_glob_switches
INST_VAR CFSwitches cf_glob_switches
Definition cf_switches.cc:54

## isPurePoly()

bool isPurePoly | ( | const CanonicalForm & | f | ) |

Definition at line 248 of file cf_factor.cc.

{
if (f.level()<=0) return false;
for (CFIterator i=f;i.hasTerms();i++)
{
if (!(i.coeff().inBaseDomain())) return false;
}
return true;
}

## isPurePoly_m()

bool isPurePoly_m | ( | const CanonicalForm & | f | ) |

Definition at line 238 of file cf_factor.cc.

{
if (f.inBaseDomain()) return true;
if (f.level()<0) return false;
for (CFIterator i=f;i.hasTerms();i++)
{
if (!isPurePoly_m(i.coeff())) return false;
}
return true;
}
isPurePoly_m
bool isPurePoly_m(const CanonicalForm &f)
Definition cf_factor.cc:238

## LC() [1/2]

CanonicalForm LC | ( | const CanonicalForm & | f | ) |

inline

Definition at line 451 of file factory.h.

{ return f.LC(); }

## LC() [2/2]

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

inline

Definition at line 454 of file factory.h.

{ return f.LC( v ); }

## Lc()

CanonicalForm Lc | ( | const CanonicalForm & | f | ) |

inline

Definition at line 448 of file factory.h.

{ return f.Lc(); }

## lc()

CanonicalForm lc | ( | const CanonicalForm & | f | ) |

inline

Definition at line 445 of file factory.h.

{ return f.lc(); }

## lcm()

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

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

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

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

Returns zero if one of f or g equals zero.

Definition at line 763 of file cf_gcd.cc.

{
if ( f.isZero() || g.isZero() )
return 0;
else
return ( f / gcd( f, g ) ) * g;
}

## leftShift()

CanonicalForm leftShift | ( | const CanonicalForm & | F,
|  | int | n )

left shift the main variable of F by n

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

Definition at line 697 of file cf_ops.cc.

{
ASSERT (n >= 0, "cannot left shift by negative number");
if (F.inBaseDomain())
return F;
if (n == 0)
return F;
Variable x=F.mvar();
CanonicalForm result= 0;
for (CFIterator i= F; i.hasTerms(); i++)
result += i.coeff()*power (x, i.exp()*n);
return result;
}
CanonicalForm::inBaseDomain
bool inBaseDomain() const
Definition canonicalform.cc:104

## level() [1/2]

int level | ( | const CanonicalForm & | f | ) |

inline

Definition at line 472 of file factory.h.

{ return f.level(); }

## level() [2/2]

int level | ( | const Variable & | v | ) |

inline

Definition at line 188 of file factory.h.

{ return v.level(); }

## linearSystemSolve()

bool linearSystemSolve | ( | CFMatrix & | M | ) |

Definition at line 78 of file cf_linsys.cc.

{
typedef int* int_ptr;
if ( ! matrix_in_Z( M ) ) {
int nrows = M.rows(), ncols = M.columns();
int i, j, k;
CanonicalForm rowpivot, pivotrecip;
// triangularization
for ( i = 1; i <= nrows; i++ ) {
//find "pivot"
for (j = i; j <= nrows; j++ )
if ( M(j,i) != 0 ) break;
if ( j > nrows ) return false;
if ( j != i )
M.swapRow( i, j );
pivotrecip = 1 / M(i,i);
for ( j = 1; j <= ncols; j++ )
M(i,j) *= pivotrecip;
for ( j = i+1; j <= nrows; j++ ) {
rowpivot = M(j,i);
if ( rowpivot == 0 ) continue;
for ( k = i; k <= ncols; k++ )
M(j,k) -= M(i,k) * rowpivot;
}
}
// matrix is now upper triangular with 1s down the diagonal
// back-substitute
for ( i = nrows-1; i > 0; i-- ) {
for ( j = nrows+1; j <= ncols; j++ ) {
for ( k = i+1; k <= nrows; k++ )
M(i,j) -= M(k,j) * M(i,k);
}
}
return true;
}
else {
int rows = M.rows(), cols = M.columns();
CFMatrix MM( rows, cols );
int ** mm = new int_ptr[rows];
CanonicalForm Q, Qhalf, mnew, qnew, B;
int i, j, p, pno;
bool ok;
// initialize room to hold the result and the result mod p
for ( i = 0; i < rows; i++ ) {
mm[i] = new int[cols];
}
// calculate the bound for the result
B = bound( M );
DEBOUTLN( cerr, "bound = " << B );
// find a first solution mod p
pno = 0;
do {
DEBOUTSL( cerr );
DEBOUT( cerr, "trying prime(" << pno << ") = " );
p = cf_getBigPrime( pno );
DEBOUT( cerr, p );
DEBOUTENDL( cerr );
setCharacteristic( p );
// map matrix into char p
for ( i = 1; i <= rows; i++ )
for ( j = 1; j <= cols; j++ )
mm[i-1][j-1] = mapinto( M(i,j) ).intval();
// solve mod p
ok = solve( mm, rows, cols );
pno++;
} while ( ! ok );
// initialize the result matrix with first solution
setCharacteristic( 0 );
for ( i = 1; i <= rows; i++ )
for ( j = rows+1; j <= cols; j++ )
MM(i,j) = mm[i-1][j-1];
// Q so far
Q = p;
while ( Q < B && pno < cf_getNumBigPrimes() ) {
do {
DEBOUTSL( cerr );
DEBOUT( cerr, "trying prime(" << pno << ") = " );
p = cf_getBigPrime( pno );
DEBOUT( cerr, p );
DEBOUTENDL( cerr );
setCharacteristic( p );
for ( i = 1; i <= rows; i++ )
for ( j = 1; j <= cols; j++ )
mm[i-1][j-1] = mapinto( M(i,j) ).intval();
// solve mod p
ok = solve( mm, rows, cols );
pno++;
} while ( ! ok );
// found a solution mod p
// now chinese remainder it to a solution mod Q*p
setCharacteristic( 0 );
for ( i = 1; i <= rows; i++ )
for ( j = rows+1; j <= cols; j++ )
{
chineseRemainder( MM[i][j], Q, CanonicalForm(mm[i-1][j-1]), CanonicalForm(p), mnew, qnew );
MM(i, j) = mnew;
}
Q = qnew;
}
if ( pno == cf_getNumBigPrimes() )
fuzzy_result = true;
else
fuzzy_result = false;
// store the result in M
Qhalf = Q / 2;
for ( i = 1; i <= rows; i++ ) {
for ( j = rows+1; j <= cols; j++ )
if ( MM(i,j) > Qhalf )
M(i,j) = MM(i,j) - Q;
else
M(i,j) = MM(i,j);
delete [] mm[i-1];
}
delete [] mm;
return ! fuzzy_result;
}
}
mapinto
CanonicalForm mapinto(const CanonicalForm &f)
Definition canonicalform.h:355
ncols
int int ncols
Definition cf_linsys.cc:32
fuzzy_result
VAR bool fuzzy_result
Definition cf_linsys.cc:75
nrows
int nrows
Definition cf_linsys.cc:32
solve
bool solve(int **extmat, int nrows, int ncols)
Definition cf_linsys.cc:504
CanonicalForm::intval
long intval() const
conversion functions
Definition canonicalform.cc:200
DEBOUTENDL
#define DEBOUTENDL(stream)
Definition debug.h:48
DEBOUTSL
#define DEBOUTSL(stream)
Definition debug.h:46

## make_cf() [1/2]

CanonicalForm FACTORY_PUBLIC make_cf | ( | const mpz_ptr | n | ) |

Definition at line 66 of file singext.cc.

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

## make_cf() [2/2]

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

Definition at line 71 of file singext.cc.

{
return CanonicalForm( CFFactory::rational( n, d, normalize ) );
}
CFFactory::rational
static InternalCF * rational(long num, long den)
Definition cf_factory.cc:268

## make_cf_from_gf()

CanonicalForm make_cf_from_gf | ( | const int | z | ) |

Definition at line 76 of file singext.cc.

{
return CanonicalForm(int2imm_gf(z));
}

## mapdomain()

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

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.

{
if ( f.inBaseDomain() )
return mf( f );
else
{
CanonicalForm result = 0;
CFIterator i;
Variable x = f.mvar();
for ( i = f; i.hasTerms(); i++ )
result += power( x, i.exp() ) * mapdomain( i.coeff(), mf );
return result;
}
}
mapdomain
CanonicalForm mapdomain(const CanonicalForm &f, CanonicalForm(*mf)(const CanonicalForm &))
CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) ).
Definition cf_ops.cc:440

## mapinto()

CanonicalForm mapinto | ( | const CanonicalForm & | f | ) |

inline

Definition at line 496 of file factory.h.

{ return f.mapinto(); }

## maxNorm()

CanonicalForm maxNorm | ( | const CanonicalForm & | f | ) |

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()'.

**/ bool fdivides ( const CanonicalForm & f, const CanonicalForm & g ) { trivial cases if ( g.isZero() ) return true; else if ( f.isZero() ) return false;

if ( (f.inCoeffDomain() || g.inCoeffDomain()) && ((getCharacteristic() == 0 && isOn( SW_RATIONAL )) || (getCharacteristic() > 0) )) { if we are in a field all elements not equal to zero are units if ( f.inCoeffDomain() ) return true; else g.inCoeffDomain() return false; }

we may assume now that both levels either equal LEVELBASE or are greater zero int fLevel = f.level(); int gLevel = g.level(); if ( (gLevel > 0) && (fLevel == gLevel) ) f and g are polynomials in the same main variable if ( degree( f ) <= degree( g ) && fdivides( f.tailcoeff(), g.tailcoeff() ) && fdivides( f.LC(), g.LC() ) ) { CanonicalForm q, r; return divremt( g, f, q, r ) && r.isZero(); } else return false; else if ( gLevel < fLevel ) g is a coefficient w.r.t. f return false; else { either f is a coefficient w.r.t. polynomial g or both f and g are from a base domain (should be Z or Z/p^n, then) CanonicalForm q, r; return divremt( g, f, q, r ) && r.isZero(); } }

/ same as fdivides if true returns quotient quot of g by f otherwise quot == 0 bool fdivides ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm& quot ) { quot= 0; trivial cases if ( g.isZero() ) return true; else if ( f.isZero() ) return false;

if ( (f.inCoeffDomain() || g.inCoeffDomain()) && ((getCharacteristic() == 0 && isOn( SW_RATIONAL )) || (getCharacteristic() > 0) )) { if we are in a field all elements not equal to zero are units if ( f.inCoeffDomain() ) { quot= g/f; return true; } else g.inCoeffDomain() return false; }

we may assume now that both levels either equal LEVELBASE or are greater zero int fLevel = f.level(); int gLevel = g.level(); if ( (gLevel > 0) && (fLevel == gLevel) ) f and g are polynomials in the same main variable if ( degree( f ) <= degree( g ) && fdivides( f.tailcoeff(), g.tailcoeff() ) && fdivides( f.LC(), g.LC() ) ) { CanonicalForm q, r; if (divremt( g, f, q, r ) && r.isZero()) { quot= q; return true; } else return false; } else return false; else if ( gLevel < fLevel ) g is a coefficient w.r.t. f return false; else { either f is a coefficient w.r.t. polynomial g or both f and g are from a base domain (should be Z or Z/p^n, then) CanonicalForm q, r; if (divremt( g, f, q, r ) && r.isZero()) { quot= q; return true; } else return false; } }

/ same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f bool tryFdivides ( const CanonicalForm & f, const CanonicalForm & g, const CanonicalForm& M, bool& fail ) { fail= false; trivial cases if ( g.isZero() ) return true; else if ( f.isZero() ) return false;

if (f.inCoeffDomain() || g.inCoeffDomain()) { if we are in a field all elements not equal to zero are units if ( f.inCoeffDomain() ) { CanonicalForm inv; tryInvert (f, M, inv, fail); return !fail; } else { return false; } }

we may assume now that both levels either equal LEVELBASE or are greater zero int fLevel = f.level(); int gLevel = g.level(); if ( (gLevel > 0) && (fLevel == gLevel) ) { if (degree( f ) > degree( g )) return false; bool dividestail= tryFdivides (f.tailcoeff(), g.tailcoeff(), M, fail);

if (fail || !dividestail) return false; bool dividesLC= tryFdivides (f.LC(),g.LC(), M, fail); if (fail || !dividesLC) return false; CanonicalForm q,r; bool divides= tryDivremt (g, f, q, r, M, fail); if (fail || !divides) return false; return r.isZero(); } else if ( gLevel < fLevel ) { g is a coefficient w.r.t. f return false; } else { either f is a coefficient w.r.t. polynomial g or both f and g are from a base domain (should be Z or Z/p^n, then) CanonicalForm q, r; bool divides= tryDivremt (g, f, q, r, M, fail); if (fail || !divides) return false; return r.isZero(); } }

/** CanonicalForm maxNorm ( const CanonicalForm & f )

maxNorm() - return maximum norm of `f'.

That is, the base coefficient of `f' with the largest absolute value.

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

## Type info:

f: CurrentPP

Definition at line 536 of file cf_algorithm.cc.

{
if ( f.inBaseDomain() )
return abs( f );
else {
CanonicalForm result = 0;
for ( CFIterator i = f; i.hasTerms(); i++ ) {
CanonicalForm coeffMaxNorm = maxNorm( i.coeff() );
if ( coeffMaxNorm > result )
result = coeffMaxNorm;
}
return result;
}
}
maxNorm
CanonicalForm maxNorm(const CanonicalForm &f)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
Definition cf_algorithm.cc:536

## mod()

CF_NO_INLINE FACTORY_PUBLIC CanonicalForm mod | ( | const CanonicalForm & | ,
|  | const CanonicalForm & | )

## modCharSet() [1/2]

CFList modCharSet | ( | const CFList & | PS,
|  | bool | removeContents )

Definition at line 404 of file cfCharSets.cc.

{
StoreFactors tmp;
return modCharSet (PS, tmp, removeContents);
}

## modCharSet() [2/2]

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

modified medial set

Definition at line 284 of file cfCharSets.cc.

{
CFList QS, RS= L, CSet, tmp, contents, initial, removedFactors;
CFListIterator i;
CanonicalForm r, cF;
bool noRemainder= true;
StoreFactors StoredFactors2;
QS= uniGcd (L);
while (!RS.isEmpty())
{
noRemainder= true;
CSet= basicSet (QS);
initial= factorsOfInitials (CSet);
StoredFactors2.FS1= StoredFactors.FS1;
StoredFactors2.FS2= Union (StoredFactors2.FS2, initial);
RS= CFList();
if (CSet.length() > 0 && CSet.getFirst().level() > 0)
{
tmp= Difference (QS, CSet);
for (i= tmp; i.hasItem(); i++)
{
r= Prem (i.getItem(), CSet);
if (!r.isZero())
{
noRemainder= false;
if (removeContents)
{
removeContent (r, cF);
if (!cF.isZero())
contents= Union (contents, factorPSet (CFList(cF))); //factorPSet maybe too much it should suffice to do a squarefree factorization instead
}
removeFactors (r, StoredFactors2, removedFactors);
StoredFactors2.FS1= Union (StoredFactors2.FS1, removedFactors);
StoredFactors2.FS2= Difference (StoredFactors2.FS2, removedFactors);
removedFactors= CFList();
RS= Union (RS, CFList (r));
}
}
if (removeContents && !noRemainder)
{
StoredFactors.FS1= Union (StoredFactors2.FS1, contents);
StoredFactors.FS2= StoredFactors2.FS2;
}
else
StoredFactors= StoredFactors2;
QS= Union (CSet, RS);
contents= CFList();
removedFactors= CFList();
}
else
StoredFactors= StoredFactors2;
}
return CSet;
}
removeFactors
void removeFactors(CanonicalForm &r, StoreFactors &StoredFactors, CFList &removedFactors)
Definition cfCharSetsUtil.cc:823
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

## mvar()

Variable mvar | ( | const CanonicalForm & | f | ) |

inline

Definition at line 475 of file factory.h.

{ return f.mvar(); }

## name()

char name | ( | const Variable & | v | ) |

inline

Definition at line 189 of file factory.h.

{ return v.name(); }

## neworder()

Varlist neworder | ( | const CFList & | PolyList | ) |

## newordercf()

CFList newordercf | ( | const CFList & | PolyList | ) |

Definition at line 75 of file cfCharSets.cc.

{
Varlist reorder= neworder (PolyList);
CFList output;
for (VarlistIterator i=reorder; i.hasItem(); i++)
output.append (CanonicalForm (i.getItem()));
return output;
}
VarlistIterator
ListIterator< Variable > VarlistIterator
Definition canonicalform.h:404
reorder
CFList reorder(const Varlist &betterorder, const CFList &PS)
Definition cfCharSets.cc:101
neworder
Varlist neworder(const CFList &PolyList)

## neworderint()

IntList FACTORY_PUBLIC neworderint | ( | const CFList & | PolyList | ) |

Definition at line 88 of file cfCharSets.cc.

{
Varlist reorder= neworder (PolyList);
IntList output;
for (VarlistIterator i= reorder; i.hasItem(); i++)
output.append (level (i.getItem()));
return output;
}

## num()

CanonicalForm num | ( | const CanonicalForm & | f | ) |

inline

Definition at line 478 of file factory.h.

{ return f.num(); }

## Off()

void FACTORY_PUBLIC Off | ( | int | sw | ) |

switches

Definition at line 1964 of file canonicalform.cc.

{
cf_glob_switches.Off( sw );
}

## On()

void FACTORY_PUBLIC On | ( | int | sw | ) |

switches

Definition at line 1957 of file canonicalform.cc.

{
cf_glob_switches.On( sw );
}

## operator%()

CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator% | ( | const CanonicalForm & | ,
|  | const CanonicalForm & | )

## operator*()

CF_INLINE FACTORY_PUBLIC CanonicalForm operator* | ( | const CanonicalForm & | lhs,
|  | const CanonicalForm & | rhs )

See also
  CanonicalForm::operator *=()

Definition at line 524 of file cf_inline.cc.

{
CanonicalForm result( lhs );
result *= rhs;
return result;
}

## operator+()

CF_INLINE FACTORY_PUBLIC 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 503 of file cf_inline.cc.

{
CanonicalForm result( lhs );
result += rhs;
return result;
}

## operator-()

CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator- | ( | const CanonicalForm & | ,
|  | const CanonicalForm & | )

## operator/()

CF_NO_INLINE FACTORY_PUBLIC CanonicalForm operator/ | ( | const CanonicalForm & | ,
|  | const CanonicalForm & | )

## power() [1/2]

CanonicalForm FACTORY_PUBLIC power | ( | const CanonicalForm & | f,
|  | int | n )

exponentiation

Definition at line 1896 of file canonicalform.cc.

{
ASSERT( n >= 0, "illegal exponent" );
if ( f.isZero() )
return CanonicalForm(0L);
else if ( f.isOne() )
return f;
else if ( f == -1 )
{
if ( n % 2 == 0 )
return CanonicalForm(1L);
else
return CanonicalForm(-1L);
}
else if ( n == 0 )
return CanonicalForm(1L);
//else if (f.inGF())
//{
//}
else
{
CanonicalForm g,h;
h=f;
while(n%2==0)
{
h*=h;
n/=2;
}
g=h;
while(1)
{
n/=2;
if(n==0)
return g;
h*=h;
if(n%2!=0) g*=h;
}
}
}
h
STATIC_VAR Poly * h
Definition janet.cc:971

## power() [2/2]

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

exponentiation

Definition at line 1939 of file canonicalform.cc.

{
//ASSERT( n >= 0, "illegal exponent" );
if ( n == 0 )
return 1;
else if ( n == 1 )
return v;
else if (( v.level() < 0 ) && (hasMipo(v)))
{
CanonicalForm result( v, n-1 );
return result * v;
}
else
return CanonicalForm( v, n );
}
hasMipo
bool hasMipo(const Variable &alpha)
Definition variable.cc:226

## pp()

CanonicalForm FACTORY_PUBLIC pp | ( | const CanonicalForm & | f | ) |

CanonicalForm pp ( const CanonicalForm & f ).

pp() - return primitive part of f.

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

Definition at line 676 of file cf_gcd.cc.

{
if ( f.isZero() )
return f;
else
return f / content( f );
}

## Prem()

CanonicalForm Prem | ( | const CanonicalForm & | F,
|  | const CanonicalForm & | G )

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

Definition at line 616 of file cfCharSetsUtil.cc.

{
CanonicalForm f, g, l, test, lu, lv, t, retvalue;
int degF, degG, levelF, levelG;
bool reord;
Variable v, vg= G.mvar();
if ( (levelF= F.level()) < (levelG= G.level()))
return F;
else
{
if ( levelF == levelG )
{
f= F;
g= G;
reord= false;
v= F.mvar();
}
else
{
v= Variable (levelF + 1);
f= swapvar (F, vg, v);
g= swapvar (G, vg, v);
reord= true;
}
degG= degree (g, v );
degF= degree (f, v );
if (degG <= degF)
{
l= LC (g);
g= g - l*power (v, degG);
}
else
l= 1;
while ((degG <= degF) && (!f.isZero()))
{
test= gcd (l, LC(f));
lu= l / test;
lv= LC(f) / test;
t= g*lv*power (v, degF - degG);
if (degF == 0)
f= 0;
else
f= f - LC (f)*power (v, degF);
f= f*lu - t;
degF= degree (f, v);
}
if (reord)
retvalue= swapvar (f, vg, v);
else
retvalue= f;
return retvalue;
}
}
LC
CanonicalForm LC(const CanonicalForm &f)
Definition canonicalform.h:310
swapvar
CFList swapvar(const CFList &PS, const Variable &x, const Variable &y)
swapvar a whole list of CanonicalForms
Definition cfCharSetsUtil.cc:304
test
CanonicalForm test
Definition cfModGcd.cc:4104
retvalue
static CanonicalForm * retvalue
Definition readcf.cc:126
gcd
int gcd(int a, int b)
Definition walkSupport.cc:836

## probIrredTest()

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

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

Returns
  probIrredTest returns 1 for irreducibility, -1 for reducibility or 0 if the test is not applicable

Parameters

  [in] | F | some poly over Z/p
  [in] | error | 0 < error < 1

Definition at line 63 of file facIrredTest.cc.

{
CFMap N;
CanonicalForm G= compress (F, N);
int n= G.level();
int p= getCharacteristic();
double sqrtTrials= inverseERF (1-2.0*error)*sqrt (2.0);
double s= sqrtTrials;
double pn= pow ((double) p, (double) n);
double p1= (double) 1/p;
p1= p1*(1.0-p1);
p1= p1/(double) pn;
p1= sqrt (p1);
p1 *= s;
p1 += (double) 1/p;
double p2= (double) (2*p-1)/(p*p);
p2= p2*(1-p2);
p2= p2/(double) pn;
p2= sqrt (p2);
p2 *= s;
p2= (double) (2*p - 1)/(p*p)-p2;
//no testing possible
if (p2 < p1)
return 0;
double den= sqrt (p1*(1-p1))+sqrt (p2*(1-p2));
double num= p2-p1;
sqrtTrials *= den/num;
int trials= (int) floor (pow (sqrtTrials, 2.0));
double experimentalNumZeros= numZeros (G, trials);
double pmiddle= sqrt (p1*p2);
num= den;
den= sqrt (p1*(1.0-p2))+sqrt (p2*(1.0-p1));
pmiddle *= (den/num);
if (experimentalNumZeros < pmiddle)
return 1;
else
return -1;
}
pow
Rational pow(const Rational &a, int e)
Definition GMPrat.cc:411
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
inverseERF
double inverseERF(double d)
Definition facIrredTest.cc:42
sqrt
gmp_float sqrt(const gmp_float &a)
Definition mpr_complex.cc:319
error
#define error(a)
Definition mpr_numeric.cc:966

## prune()

void FACTORY_PUBLIC prune | ( | Variable & | alpha | ) |

Definition at line 261 of file variable.cc.

{
if (alpha.level()==LEVELBASE) return;
int last_var=-alpha.level();
if ((last_var <= 0)||(var_names_ext==NULL)) return;
int i, n = strlen( var_names_ext );
ASSERT (n+1 >= last_var, "wrong variable");
if (last_var == 1)
{
delete [] var_names_ext;
delete [] algextensions;
var_names_ext= 0;
algextensions= 0;
alpha= Variable();
return;
}
char * newvarnames = new char [last_var+1];
for ( i = 0; i < last_var; i++ )
newvarnames[i] = var_names_ext[i];
newvarnames[last_var] = 0;
delete [] var_names_ext;
var_names_ext = newvarnames;
ext_entry * newalgext = new ext_entry [last_var];
for ( i = 0; i < last_var; i++ )
newalgext[i] = algextensions[i];
delete [] algextensions;
algextensions = newalgext;
alpha= Variable();
}
ext_entry
Definition variable.cc:19

## prune1()

void prune1 | ( | const Variable & | alpha | ) |

Definition at line 291 of file variable.cc.

{
int i, n = strlen( var_names_ext );
ASSERT (n+1 >= -alpha.level(), "wrong variable");
char * newvarnames = new char [-alpha.level() + 2];
for ( i = 0; i <= -alpha.level(); i++ )
newvarnames[i] = var_names_ext[i];
newvarnames[-alpha.level()+1] = 0;
delete [] var_names_ext;
var_names_ext = newvarnames;
ext_entry * newalgext = new ext_entry [-alpha.level()+1];
for ( i = 0; i <= -alpha.level(); i++ )
newalgext[i] = algextensions[i];
delete [] algextensions;
algextensions = newalgext;
}

## psq()

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

cf_algorithm.cc - simple mathematical algorithms.

Hierarchy: mathematical algorithms on canonical forms

## Developers note:

A "mathematical" algorithm is an algorithm which calculates some mathematical function in contrast to a "structural" algorithm which gives structural information on polynomials.

Compare these functions to the functions in `cf_ops.cc', which are structural algorithms.

**/

void out_cf(const char *s1,const CanonicalForm &f,const char *s2);

/** 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() **/ CanonicalForm

psr ( const CanonicalForm &rr, const CanonicalForm &vv, const Variable & x ) { CanonicalForm r=rr, v=vv, l, test, lu, lv, t, retvalue; int dr, dv, d,n=0;

dr = degree( r, x ); if (dr>0) { dv = degree( v, x ); if (dv <= dr) {l=LC(v,x); v = v -l*power(x,dv);} else { l = 1; } d= dr-dv+1; out_cf("psr(",rr," "); out_cf("",vv," "); printf(" var=%d\n",x.level()); while ( ( dv <= dr ) && ( !r.isZero()) ) { test = power(x,dr-dv)*v*LC(r,x); if ( dr == 0 ) { r= CanonicalForm(0); } else { r= r - LC(r,x)*power(x,dr); } r= l*r -test; dr= degree(r,x); n+=1; } r= power(l, d-n)*r; } return r; }

/** 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.

{
ASSERT( x.level() > 0, "type error: polynomial variable expected" );
ASSERT( ! g.isZero(), "math error: division by zero" );
// swap variables such that x's level is larger or equal
// than both f's and g's levels.
Variable X = tmax( tmax( f.mvar(), g.mvar() ), x );
CanonicalForm F = swapvar( f, x, X );
CanonicalForm G = swapvar( g, x, X );
// now, we have to calculate the pseudo remainder of F and G
// w.r.t. X
int fDegree = degree( F, X );
int gDegree = degree( G, X );
if ( fDegree < 0 || fDegree < gDegree )
return 0;
else {
CanonicalForm result = (power( LC( G, X ), fDegree-gDegree+1 ) * F) / G;
return swapvar( result, x, X );
}
}

## psqr()

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

## psr()

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

## reduce()

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

Definition at line 660 of file cf_ops.cc.

{
if(f.inBaseDomain() || f.level() < M.level())
return f;
if(f.level() == M.level())
{
if(f.degree() < M.degree())
return f;
CanonicalForm tmp = mod (f, M);
return tmp;
}
// here: f.level() > M.level()
CanonicalForm result = 0;
for(CFIterator i=f; i.hasTerms(); i++)
result += reduce(i.coeff(),M) * power(f.mvar(),i.exp());
return result;
}
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:660

## reorder() [1/3]

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

Definition at line 120 of file cfCharSets.cc.

{
int i= 1, n= betterorder.length();
Intarray v (1, n);
CFFList ps= PS;
//initalize:
for (VarlistIterator j= betterorder; j.hasItem(); j++)
{
v[i]= level (j.getItem());
i++;
}
// reorder:
for (i= 1; i <= n; i++)
ps= swapvar (ps, Variable (v[i]), Variable (n + i));
return ps;
}
Intarray
Array< int > Intarray
Definition canonicalform.h:405

## reorder() [2/3]

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

Definition at line 101 of file cfCharSets.cc.

{
int i= 1, n= betterorder.length();
Intarray v (1, n);
CFList ps= PS;
//initalize:
for (VarlistIterator j= betterorder; j.hasItem(); j++)
{
v[i]= level (j.getItem());
i++;
}
// reorder:
for (i= 1; i <= n; i++)
ps= swapvar (ps, Variable (v[i]), Variable (n + i));
return ps;
}

## reorder() [3/3]

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

Definition at line 140 of file cfCharSets.cc.

{
ListCFList Q1;
for (ListCFListIterator i= Q; i.hasItem(); i++)
Q1.append (reorder (betterorder, i.getItem()));
return Q1;
}
ListCFListIterator
ListIterator< CFList > ListCFListIterator
Definition canonicalform.h:400

## replaceLc()

CanonicalForm replaceLc | ( | const CanonicalForm & | f,
|  | const CanonicalForm & | c )

Definition at line 90 of file fac_util.cc.

{
if ( f.inCoeffDomain() )
return c;
else
return f + ( c - LC( f ) ) * power( f.mvar(), degree( f ) );
}

## replacevar()

CanonicalForm FACTORY_PUBLIC 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.

{
//ASSERT( x2.level() > 0, "cannot replace with algebraic variable" );
if ( f.inBaseDomain() || x1 == x2 || ( x1 > f.mvar() ) )
return f;
else
{
sv_x1 = x1;
sv_x2 = x2;
return replacevar_between( f );
}
}
sv_x2
STATIC_INST_VAR Variable sv_x2
Definition cf_ops.cc:43
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
sv_x1
STATIC_INST_VAR Variable sv_x1
static Variable sv_x1, sv_x2;
Definition cf_ops.cc:43

## resultant()

CanonicalForm FACTORY_PUBLIC 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.

{
ASSERT( x.level() > 0, "cannot calculate resultant with respect to algebraic variables" );
// some checks on triviality. We will not use degree( v )
// here because this may involve variable swapping.
if ( f.isZero() || g.isZero() )
return 0;
if ( f.mvar() < x )
return power( f, g.degree( x ) );
if ( g.mvar() < x )
return power( g, f.degree( x ) );
// make x main variale
CanonicalForm F, G;
Variable X;
if ( f.mvar() > x || g.mvar() > x ) {
if ( f.mvar() > g.mvar() )
X = f.mvar();
else
X = g.mvar();
F = swapvar( f, X, x );
G = swapvar( g, X, x );
}
else {
X = x;
F = f;
G = g;
}
// at this point, we have to calculate resultant( F, G, X )
// where X is equal to or greater than the main variables
// of F and G
int m = degree( F, X );
int n = degree( G, X );
// catch trivial cases
if ( m+n <= 2 || m == 0 || n == 0 )
return swapvar( trivialResultant( F, G, X ), X, x );
// exchange F and G if necessary
int flipFactor;
if ( m < n ) {
CanonicalForm swap = F;
F = G; G = swap;
int degswap = m;
m = n; n = degswap;
if ( m & 1 && n & 1 )
flipFactor = -1;
else
flipFactor = 1;
} else
flipFactor = 1;
// this is not an effective way to calculate the resultant!
CanonicalForm extFactor;
if ( m == n ) {
if ( n & 1 )
extFactor = -LC( G, X );
else
extFactor = LC( G, X );
} else
extFactor = power( LC( F, X ), m-n-1 );
CanonicalForm result;
result = subResChain( F, G, X )[0] / extFactor;
return swapvar( result, X, x ) * flipFactor;
}
swap
#define swap(_i, _j)
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
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

## 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] | A | some poly
  [in] | B | some poly
  [in] | x | some polynomial variable
  [in] | prob | if true use probabilistic algorithm

Definition at line 560 of file cfModResultant.cc.

{
ASSERT (getCharacteristic() == 0, "characteristic > 0 expected");
#ifndef NOASSERT
bool isRat= isOn (SW_RATIONAL);
On (SW_RATIONAL);
ASSERT (bCommonDen (A).isOne(), "input A is rational");
ASSERT (bCommonDen (B).isOne(), "input B is rational");
if (!isRat)
Off (SW_RATIONAL);
#endif
int degAx= degree (A, x);
int degBx= degree (B, x);
if (A.level() < x.level())
return power (A, degBx);
if (B.level() < x.level())
return power (B, degAx);
if (degAx == 0)
return power (A, degBx);
else if (degBx == 0)
return power (B, degAx);
CanonicalForm F= A;
CanonicalForm G= B;
Variable X= x;
if (F.level() != x.level() || G.level() != x.level())
{
if (F.level() > G.level())
X= F.mvar();
else
X= G.mvar();
F= swapvar (F, X, x);
G= swapvar (G, X, x);
}
// now X is the main variable
CanonicalForm d= 0;
CanonicalForm dd= 0;
CanonicalForm buf;
for (CFIterator i= F; i.hasTerms(); i++)
{
buf= oneNorm (i.coeff());
d= (buf > d) ? buf : d;
}
CanonicalForm e= 0, ee= 0;
for (CFIterator i= G; i.hasTerms(); i++)
{
buf= oneNorm (i.coeff());
e= (buf > e) ? buf : e;
}
d= power (d, degBx);
e= power (e, degAx);
CanonicalForm bound= 1;
for (int i= degBx + degAx; i > 1; i--)
bound *= i;
bound *= d*e;
bound *= 2;
bool onRational= isOn (SW_RATIONAL);
if (onRational)
Off (SW_RATIONAL);
int i = cf_getNumBigPrimes() - 1;
int p;
CanonicalForm l= lc (F)*lc(G);
CanonicalForm resultModP, q (0), newResult, newQ;
CanonicalForm result;
int equalCount= 0;
CanonicalForm test, newTest;
int count= 0;
do
{
p = cf_getBigPrime( i );
i--;
while ( i >= 0 && mod( l, p ) == 0)
{
p = cf_getBigPrime( i );
i--;
}
if (i <= 0)
return resultant (A, B, x);
setCharacteristic (p);
TIMING_START (fac_resultant_p);
resultModP= resultantFp (mapinto (F), mapinto (G), X, prob);
TIMING_END_AND_PRINT (fac_resultant_p, "time to compute resultant mod p: ");
setCharacteristic (0);
count++;
if ( q.isZero() )
{
result= mapinto(resultModP);
q= p;
}
else
{
chineseRemainder( result, q, mapinto (resultModP), p, newResult, newQ );
q= newQ;
result= newResult;
test= symmetricRemainder (result,q);
if (test != newTest)
{
newTest= test;
equalCount= 0;
}
else
equalCount++;
if (newQ > bound || (prob && equalCount == 2))
{
result= test;
break;
}
}
} while (1);
if (onRational)
On (SW_RATIONAL);
return swapvar (result, X, x);
}
lc
CanonicalForm lc(const CanonicalForm &f)
Definition canonicalform.h:304
oneNorm
static CanonicalForm oneNorm(const CanonicalForm &F)
Definition cfModResultant.cc:243
symmetricRemainder
static CanonicalForm symmetricRemainder(const CanonicalForm &f, const CanonicalForm &q)
Definition cfModResultant.cc:545
resultantFp
CanonicalForm resultantFp(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Fp
Definition cfModResultant.cc:349
resultant
CanonicalForm FACTORY_PUBLIC 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
buf
int status int void * buf
Definition si_signals.h:69
TIMING_END_AND_PRINT
#define TIMING_END_AND_PRINT(t, msg)
Definition timing.h:94

## rootOf()

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

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

returns a symbolic root of polynomial with name name.

Note
  : algebraic variables have a level < 0

Use it to define algebraic variables

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

Definition at line 162 of file variable.cc.

{
ASSERT (mipo.isUnivariate(), "not a legal extension");
int l;
if ( var_names_ext == 0 ) {
var_names_ext = new char [3];
var_names_ext[0] = '@';
var_names_ext[1] = name;
var_names_ext[2] = '\0';
l = 1;
Variable result( -l, true );
algextensions = new ext_entry [2];
algextensions[1] = ext_entry( 0, false );
algextensions[1] = ext_entry( (InternalPoly*)(conv2mipo( mipo, result ).getval()), true );
return result;
}
else {
int i, n = strlen( var_names_ext );
char * newvarnames = new char [n+2];
for ( i = 0; i < n; i++ )
newvarnames[i] = var_names_ext[i];
newvarnames[n] = name;
newvarnames[n+1] = 0;
delete [] var_names_ext;
var_names_ext = newvarnames;
l = n;
Variable result( -l, true );
ext_entry * newalgext = new ext_entry [n+1];
for ( i = 0; i < n; i++ )
newalgext[i] = algextensions[i];
newalgext[n] = ext_entry( 0, false );
delete [] algextensions;
algextensions = newalgext;
algextensions[n] = ext_entry( (InternalPoly*)(conv2mipo( mipo, result ).getval()), true );
return result;
}
}
InternalPoly
factory's class for polynomials
Definition int_poly.h:71
mipo
CanonicalForm mipo
Definition facAlgExt.cc:57
name
char name(const Variable &v)
Definition factory.h:189
conv2mipo
static CanonicalForm conv2mipo(const CanonicalForm &mipo, const Variable &alpha)
Definition variable.cc:154

## setCharacteristic() [1/3]

void FACTORY_PUBLIC setCharacteristic | ( | int | c | ) |

Definition at line 28 of file cf_char.cc.

{
if ( c == 0 )
{
theDegree = 0;
CFFactory::settype( IntegerDomain );
theCharacteristic = 0;
}
else
{
theDegree = 1;
CFFactory::settype( FiniteFieldDomain );
ff_big = c > cf_getSmallPrime( cf_getNumSmallPrimes()-1 );
if (c!=theCharacteristic)
{
if (c > 536870909) factoryError("characteristic is too large(max is 2^29)");
ff_setprime( c );
}
theCharacteristic = c;
}
}
FiniteFieldDomain
#define FiniteFieldDomain
Definition cf_defs.h:19
cf_getNumSmallPrimes
int cf_getNumSmallPrimes()
Definition cf_primes.cc:34
cf_getSmallPrime
int cf_getSmallPrime(int i)
Definition cf_primes.cc:28
CFFactory::settype
static void settype(int type)
Definition cf_factory.h:29
ff_big
VAR bool ff_big
Definition ffops.cc:25
ff_setprime
void ff_setprime(const int p)
Definition ffops.cc:28

## setCharacteristic() [2/3]

void setCharacteristic | ( | int | c,
|  | int | n )

## setCharacteristic() [3/3]

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

Definition at line 61 of file cf_char.cc.

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

## setMipo()

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

Definition at line 219 of file variable.cc.

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

## setReduce()

void setReduce | ( | const Variable & | alpha,
|  | bool | reduce )

Definition at line 238 of file variable.cc.

{
ASSERT( alpha.level() < 0 && alpha.level() != LEVELBASE, "illegal extension" );
algextensions[-alpha.level()].reduce() = reduce;
}
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:660

## sign()

int sign | ( | const CanonicalForm & | a | ) |

inline

Definition at line 484 of file factory.h.

{ return a.sign(); }

## size() [1/2]

int size | ( | const CanonicalForm & | f | ) |

int size ( const CanonicalForm & f )

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

Returns one if f is in an coefficient domain.

Definition at line 627 of file cf_ops.cc.

{
if ( f.inCoeffDomain() )
return 1;
else
{
int result = 0;
CFIterator i;
for ( i = f; i.hasTerms(); i++ )
result += size( i.coeff() );
return result;
}
}
size
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
Definition cf_ops.cc:600

## size() [2/2]

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

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

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

Returns one if f is in an base domain.

Definition at line 600 of file cf_ops.cc.

{
if ( f.inBaseDomain() )
return 1;
if ( f.mvar() < v )
// polynomials with level < v1 are counted as coefficients
return 1;
else
{
CFIterator i;
int result = 0;
// polynomials with level > v2 are not counted al all
for ( i = f; i.hasTerms(); i++ )
result += size( i.coeff(), v );
return result;
}
}

## size_maxexp()

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

Definition at line 641 of file cf_ops.cc.

{
if ( f.inCoeffDomain() )
return 1;
else
{
if (f.degree()>maxexp) maxexp=f.degree();
int result = 0;
CFIterator i;
for ( i = f; i.hasTerms(); i++ )
result += size_maxexp( i.coeff(), maxexp );
return result;
}
}
size_maxexp
int size_maxexp(const CanonicalForm &f, int &maxexp)
Definition cf_ops.cc:641

## sqrFree()

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

squarefree factorization

Definition at line 961 of file cf_factor.cc.

{
// ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
CFFList result;
if ( getCharacteristic() == 0 )
result = sqrFreeZ( f );
else
{
Variable alpha;
if (hasFirstAlgVar (f, alpha))
result = FqSqrf( f, alpha );
else
result= FpSqrf (f);
}
if (sort)
{
CFFactor buf= result.getFirst();
result.removeFirst();
result= sortCFFList (result);
result.insert (buf);
}
return result;
}
sort
static void sort(int **points, int sizePoints)
Definition cfNewtonPolygon.cc:100
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
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
sqrFreeZ
CFFList sqrFreeZ(const CanonicalForm &a)
Definition fac_sqrfree.cc:49
sortCFFList
CFFList sortCFFList(CFFList &F)
Definition fac_sqrfree.cc:25

## sqrt()

CanonicalForm sqrt | ( | const CanonicalForm & | a | ) |

inline

Definition at line 490 of file factory.h.

{ return a.sqrt(); }
CanonicalForm::sqrt
CanonicalForm sqrt() const
CanonicalForm CanonicalForm::sqrt () const.
Definition canonicalform.cc:1383

## 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.

{
ASSERT( x.level() > 0, "cannot calculate subresultant sequence with respect to algebraic variables" );
CFArray trivialResult( 0, 0 );
CanonicalForm F, G;
Variable X;
// some checks on triviality
if ( f.isZero() || g.isZero() ) {
trivialResult[0] = 0;
return trivialResult;
}
// make x main variable
if ( f.mvar() > x || g.mvar() > x ) {
if ( f.mvar() > g.mvar() )
X = f.mvar();
else
X = g.mvar();
F = swapvar( f, X, x );
G = swapvar( g, X, x );
}
else {
X = x;
F = f;
G = g;
}
// at this point, we have to calculate the sequence of F and
// G in respect to X where X is equal to or greater than the
// main variables of F and G
// initialization of chain
int m = degree( F, X );
int n = degree( G, X );
int j = (m <= n) ? n : m-1;
int r;
CFArray S( 0, j+1 );
CanonicalForm R;
S[j+1] = F; S[j] = G;
// make sure that S[j+1] is regular and j < n
if ( m == n && j > 0 ) {
S[j-1] = LC( S[j], X ) * psr( S[j+1], S[j], X );
j--;
} else if ( m < n ) {
S[j-1] = LC( S[j], X ) * LC( S[j], X ) * S[j+1];
j--;
} else if ( m > n && j > 0 ) {
// calculate first step
r = degree( S[j], X );
R = LC( S[j+1], X );
// if there was a gap calculate similar polynomial
if ( j > r && r >= 0 )
S[r] = power( LC( S[j], X ), j - r ) * S[j] * power( R, j - r );
if ( r > 0 ) {
// calculate remainder
S[r-1] = psr( S[j+1], S[j], X ) * power( -R, j - r );
j = r-1;
}
}
while ( j > 0 ) {
// at this point, 0 < j < n and S[j+1] is regular
r = degree( S[j], X );
R = LC( S[j+1], X );
// if there was a gap calculate similar polynomial
if ( j > r && r >= 0 )
S[r] = (power( LC( S[j], X ), j - r ) * S[j]) / power( R, j - r );
if ( r <= 0 ) break;
// calculate remainder
S[r-1] = psr( S[j+1], S[j], X ) / power( -R, j - r + 2 );
j = r-1;
// again 0 <= j < r <= jOld and S[j+1] is regular
}
for ( j = 0; j <= S.max(); j++ ) {
// reswap variables if necessary
if ( X != x ) {
S[j] = swapvar( S[j], X, x );
}
}
return S;
}
psr
CanonicalForm psr(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)

## swapvar()

CanonicalForm FACTORY_PUBLIC 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.

{
ASSERT( x1.level() > 0 && x2.level() > 0, "cannot swap algebraic Variables" );
if ( f.inCoeffDomain() || x1 == x2 || ( x1 > f.mvar() && x2 > f.mvar() ) )
return f;
else
{
CanonicalForm result = 0;
if ( x1 > x2 )
{
sv_x1 = x2; sv_x2 = x1;
}
else
{
sv_x1 = x1; sv_x2 = x2;
}
if ( f.mvar() < sv_x2 )
// we only have to replace sv_x1 by sv_x2
swapvar_between( f, result, 1, 0 );
else
// we really have to swap variables
swapvar_rec( f, result, 1 );
return result;
}
}
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
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

## tailcoeff() [1/2]

CanonicalForm tailcoeff | ( | const CanonicalForm & | f | ) |

inline

Definition at line 466 of file factory.h.

{ return f.tailcoeff(); }

## tailcoeff() [2/2]

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

inline

Definition at line 469 of file factory.h.

{ return f.tailcoeff(v); }

## taildegree()

int taildegree | ( | const CanonicalForm & | f | ) |

inline

Definition at line 463 of file factory.h.

{ 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.

{
if ( f.isZero() )
return -1;
else if ( f.inCoeffDomain() )
return 0;
else
{
CFIterator i;
int cdeg = 0, dummy;
// calculate maximum over all coefficients of f, taking
// in account our own exponent
for ( i = f; i.hasTerms(); i++ )
if ( (dummy = totaldegree( i.coeff() ) + i.exp()) > cdeg )
cdeg = dummy;
return cdeg;
}
}
totaldegree
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition cf_ops.cc:523

## totaldegree() [2/2]

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

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

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

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

Definition at line 554 of file cf_ops.cc.

{
if ( f.isZero() )
return -1;
else if ( v1 > v2 )
return 0;
else if ( f.inCoeffDomain() )
return 0;
else if ( f.mvar() < v1 )
return 0;
else if ( f.mvar() == v1 )
return f.degree();
else if ( f.mvar() > v2 )
{
// v2's level is larger than f's level, descend down
CFIterator i;
int cdeg = 0, dummy;
// calculate maximum over all coefficients of f
for ( i = f; i.hasTerms(); i++ )
if ( (dummy = totaldegree( i.coeff(), v1, v2 )) > cdeg )
cdeg = dummy;
return cdeg;
}
else
{
// v1 < f.mvar() <= v2
CFIterator i;
int cdeg = 0, dummy;
// calculate maximum over all coefficients of f, taking
// in account our own exponent
for ( i = f; i.hasTerms(); i++ )
if ( (dummy = totaldegree( i.coeff(), v1, v2 ) + i.exp()) > cdeg )
cdeg = dummy;
return cdeg;
}
}

## tryFdivides()

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

## vcontent()

CanonicalForm FACTORY_PUBLIC 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 653 of file cf_gcd.cc.

{
ASSERT( x.level() > 0, "cannot calculate vcontent with respect to algebraic variable" );
if ( f.mvar() <= x )
return content( f, x );
else {
CFIterator i;
CanonicalForm d = 0;
for ( i = f; i.hasTerms() && ! d.isOne(); i++ )
d = gcd( d, vcontent( i.coeff(), x ) );
return d;
}
}
vcontent
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x ).
Definition cf_gcd.cc:653

## Variable Documentation

## factoryConfiguration

const char factoryConfiguration[]

extern

## factoryError

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

Definition at line 1127 of file factory.h.

## singular_homog_flag

EXTERN_VAR int singular_homog_flag

Definition at line 586 of file factory.h.

## SW_BERLEKAMP

const int SW_BERLEKAMP =10

static

set to 1 to use Factorys Berlekamp alg.

Definition at line 108 of file factory.h.

## SW_FAC_QUADRATICLIFT

const int SW_FAC_QUADRATICLIFT =11

static

Definition at line 110 of file factory.h.

## SW_RATIONAL

const int SW_RATIONAL = 0

static

set to 1 for computations over Q

Definition at line 88 of file factory.h.

## SW_SYMMETRIC_FF

const int SW_SYMMETRIC_FF = 1

static

set to 1 for symmetric representation over F_q

Definition at line 90 of file factory.h.

## SW_USE_CHINREM_GCD

const int SW_USE_CHINREM_GCD =5

static

set to 1 to use modular gcd over Z

Definition at line 98 of file factory.h.

## SW_USE_EZGCD

const int SW_USE_EZGCD = 2

static

set to 1 to use EZGCD over Z

Definition at line 92 of file factory.h.

## SW_USE_EZGCD_P

const int SW_USE_EZGCD_P = 3

static

set to 1 to use EZGCD over F_q

Definition at line 94 of file factory.h.

## SW_USE_FF_MOD_GCD

const int SW_USE_FF_MOD_GCD =7

static

set to 1 to use modular GCD over F_q

Definition at line 102 of file factory.h.

## SW_USE_FL_FAC_0

const int SW_USE_FL_FAC_0 =13

static

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

Definition at line 114 of file factory.h.

## SW_USE_FL_FAC_0A

const int SW_USE_FL_FAC_0A =14

static

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

Definition at line 116 of file factory.h.

## SW_USE_FL_FAC_P

const int SW_USE_FL_FAC_P =12

static

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

Definition at line 112 of file factory.h.

## SW_USE_FL_GCD_0

const int SW_USE_FL_GCD_0 =9

static

set to 1 to use Flints gcd over Q/Z

Definition at line 106 of file factory.h.

## SW_USE_FL_GCD_P

const int SW_USE_FL_GCD_P =8

static

set to 1 to use Flints gcd over F_p

Definition at line 104 of file factory.h.

## SW_USE_NTL_SORT

const int SW_USE_NTL_SORT =4

static

set to 1 to sort factors in a factorization

Definition at line 96 of file factory.h.

## SW_USE_QGCD

const int SW_USE_QGCD =6

static

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

Definition at line 100 of file factory.h.