My Project
Loading...
Searching...
No Matches
Data Structures | Macros | Typedefs | Functions | Variables
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< CanonicalFormCFAFactor
 
typedef List< CFAFactorCFAFList
 
typedef ListIterator< CFAFactorCFAFListIterator
 
typedef Factor< CanonicalFormCFFactor
 
typedef List< CFFactorCFFList
 
typedef ListIterator< CFFactorCFFListIterator
 
typedef List< CanonicalFormCFList
 
typedef ListIterator< CanonicalFormCFListIterator
 
typedef Array< CanonicalFormCFArray
 
typedef Matrix< CanonicalFormCFMatrix
 
typedef List< CFListListCFList
 
typedef ListIterator< CFListListCFListIterator
 
typedef List< intIntList
 
typedef ListIterator< intIntListIterator
 
typedef List< VariableVarlist
 
typedef ListIterator< VariableVarlistIterator
 
typedef Array< intIntarray
 
typedef termtermList
 
typedef List< MapPairMPList
 
typedef ListIterator< MapPairMPListIterator
 

Functions

int FACTORY_PUBLIC cf_getPrime (int i)
 
int FACTORY_PUBLIC cf_getNumPrimes ()
 
int FACTORY_PUBLIC cf_getSmallPrime (int i)
 
int FACTORY_PUBLIC cf_getNumSmallPrimes ()
 
int FACTORY_PUBLIC cf_getBigPrime (int i)
 
int FACTORY_PUBLIC cf_getNumBigPrimes ()
 
Variable FACTORY_PUBLIC rootOf (const CanonicalForm &, char name='@')
 returns a symbolic root of polynomial with name name Use it to define algebraic variables
 
int level (const Variable &v)
 
char name (const Variable &v)
 
void setReduce (const Variable &alpha, bool reduce)
 
void setMipo (const Variable &alpha, const CanonicalForm &mipo)
 
CanonicalForm getMipo (const Variable &alpha, const Variable &x)
 
bool hasMipo (const Variable &alpha)
 
char getDefaultVarName ()
 
char getDefaultExtName ()
 
void FACTORY_PUBLIC prune (Variable &alpha)
 
void prune1 (const Variable &alpha)
 
int ExtensionLevel ()
 
int is_imm (const InternalCF *const ptr)
 
CF_INLINE 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 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 & ) )
 
intdegrees (const CanonicalForm &f, int *degs=0)
 int * degrees ( const CanonicalForm & f, int * degs )
 
int totaldegree (const CanonicalForm &f)
 int totaldegree ( const CanonicalForm & f )
 
int totaldegree (const CanonicalForm &f, const Variable &v1, const Variable &v2)
 int totaldegree ( const CanonicalForm & f, const Variable & v1, const Variable & v2 )
 
int size (const CanonicalForm &f, const Variable &v)
 int size ( const CanonicalForm & f, const Variable & v )
 
int size (const CanonicalForm &f)
 int size ( const CanonicalForm & f )
 
int size_maxexp (const CanonicalForm &f, int &maxexp)
 
CanonicalForm reduce (const CanonicalForm &f, const CanonicalForm &M)
 polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of f are reduced modulo M
 
bool hasFirstAlgVar (const CanonicalForm &f, Variable &a)
 check if poly f contains an algebraic variable a
 
CanonicalForm leftShift (const CanonicalForm &F, int n)
 left shift the main variable of F by n
 
CanonicalForm lc (const CanonicalForm &f)
 
CanonicalForm Lc (const CanonicalForm &f)
 
CanonicalForm LC (const CanonicalForm &f)
 
CanonicalForm LC (const CanonicalForm &f, const Variable &v)
 
int degree (const CanonicalForm &f)
 
int degree (const CanonicalForm &f, const Variable &v)
 
int taildegree (const CanonicalForm &f)
 
CanonicalForm tailcoeff (const CanonicalForm &f)
 
CanonicalForm tailcoeff (const CanonicalForm &f, const Variable &v)
 
int level (const CanonicalForm &f)
 
Variable mvar (const CanonicalForm &f)
 
CanonicalForm num (const CanonicalForm &f)
 
CanonicalForm den (const CanonicalForm &f)
 
int sign (const CanonicalForm &a)
 
CanonicalForm deriv (const CanonicalForm &f, const Variable &x)
 
CanonicalForm sqrt (const CanonicalForm &a)
 
int ilog2 (const CanonicalForm &a)
 
CanonicalForm mapinto (const CanonicalForm &f)
 
CanonicalForm head (const CanonicalForm &f)
 
int headdegree (const CanonicalForm &f)
 
void FACTORY_PUBLIC setCharacteristic (int c)
 
void setCharacteristic (int c, int n)
 
void setCharacteristic (int c, int n, char name)
 
int FACTORY_PUBLIC getCharacteristic ()
 
int getGFDegree ()
 
CanonicalForm getGFGenerator ()
 
void FACTORY_PUBLIC On (int)
 switches
 
void FACTORY_PUBLIC Off (int)
 switches
 
bool FACTORY_PUBLIC isOn (int)
 switches
 
CanonicalForm psr (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
 
CanonicalForm psq (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
 
void psqr (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, const Variable &x)
 void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable & x )
 
CanonicalForm FACTORY_PUBLIC bCommonDen (const CanonicalForm &f)
 CanonicalForm bCommonDen ( const CanonicalForm & f )
 
bool fdivides (const CanonicalForm &f, const CanonicalForm &g)
 bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
 
bool fdivides (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &quot)
 same as fdivides if true returns quotient quot of g by f otherwise quot == 0
 
bool tryFdivides (const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
 same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f
 
CanonicalForm maxNorm (const CanonicalForm &f)
 CanonicalForm maxNorm ( const CanonicalForm & f )
 
CanonicalForm euclideanNorm (const CanonicalForm &f)
 CanonicalForm euclideanNorm ( const CanonicalForm & f )
 
void FACTORY_PUBLIC chineseRemainder (const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
 void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew )
 
void FACTORY_PUBLIC chineseRemainder (const CFArray &x, const CFArray &q, CanonicalForm &xnew, CanonicalForm &qnew)
 void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew )
 
void FACTORY_PUBLIC chineseRemainderCached (const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew, CFArray &inv)
 
void FACTORY_PUBLIC chineseRemainderCached (const CFArray &a, const CFArray &n, CanonicalForm &xnew, CanonicalForm &prod, CFArray &inv)
 
CanonicalForm Farey (const CanonicalForm &f, const CanonicalForm &q)
 Farey rational reconstruction.
 
bool isPurePoly (const CanonicalForm &f)
 
bool isPurePoly_m (const CanonicalForm &f)
 
CFFList FACTORY_PUBLIC factorize (const CanonicalForm &f, bool issqrfree=false)
 factorization over $ F_p $ or $ Q $
 
CFFList FACTORY_PUBLIC factorize (const CanonicalForm &f, const Variable &alpha)
 factorization over $ F_p(\alpha) $ or $ Q(\alpha) $
 
CFFList FACTORY_PUBLIC sqrFree (const CanonicalForm &f, bool sort=false)
 squarefree factorization
 
CanonicalForm homogenize (const CanonicalForm &f, const Variable &x)
 homogenize homogenizes f with Variable x
 
CanonicalForm homogenize (const CanonicalForm &f, const Variable &x, const Variable &v1, const Variable &v2)
 
Variable get_max_degree_Variable (const CanonicalForm &f)
 get_max_degree_Variable returns Variable with highest degree.
 
CFList get_Terms (const CanonicalForm &f)
 
void getTerms (const CanonicalForm &f, const CanonicalForm &t, CFList &result)
 get_Terms: Split the polynomial in the containing terms.
 
bool linearSystemSolve (CFMatrix &M)
 
CanonicalForm FACTORY_PUBLIC determinant (const CFMatrix &M, int n)
 
CFArray subResChain (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
 
CanonicalForm FACTORY_PUBLIC resultant (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
 
CanonicalForm abs (const CanonicalForm &f)
 inline CanonicalForm abs ( const CanonicalForm & f )
 
int factoryrandom (int n)
 random integers with abs less than n
 
void FACTORY_PUBLIC factoryseed (int s)
 random seed initializer
 
CanonicalForm replaceLc (const CanonicalForm &f, const CanonicalForm &c)
 
CanonicalForm compress (const CanonicalForm &f, CFMap &m)
 CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
 
void compress (const CFArray &a, CFMap &M, CFMap &N)
 void compress ( const CFArray & a, CFMap & M, CFMap & N )
 
void compress (const CanonicalForm &f, const CanonicalForm &g, CFMap &M, CFMap &N)
 void compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N )
 
long gf_gf2ff (long a)
 
int gf_gf2ff (int a)
 
bool gf_isff (long a)
 
bool gf_isff (int a)
 
CFMatrix *FACTORY_PUBLIC 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 *FACTORY_PUBLIC 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. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $.
 
CFFList facAlgFunc (const CanonicalForm &f, const CFList &as)
 factorize a polynomial f modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $.
 
CanonicalForm Prem (const CanonicalForm &F, const CanonicalForm &G)
 pseudo remainder of F by G with certain factors of LC (g) cancelled
 
CFList basicSet (const CFList &PS)
 basic set in the sense of Wang a.k.a. minimal ascending set in the sense of Greuel/Pfister
 
CFList charSet (const CFList &PS)
 characteristic set
 
CFList modCharSet (const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true)
 modified medial set
 
CFList modCharSet (const CFList &PS, bool removeContents)
 
CFList charSetViaCharSetN (const CFList &PS)
 compute a characteristic set via medial set
 
CFList charSetN (const CFList &PS)
 medial set
 
CFList charSetViaModCharSet (const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true)
 modified characteristic set, i.e. a characteristic set with certain factors removed
 
CFList charSetViaModCharSet (const CFList &PS, bool removeContents=true)
 modified characteristic set, i.e. a characteristic set with certain factors removed
 
ListCFList charSeries (const CFList &L)
 characteristic series
 
ListCFList FACTORY_PUBLIC irrCharSeries (const CFList &PS)
 irreducible characteristic series
 
Varlist neworder (const CFList &PolyList)
 
CFList newordercf (const CFList &PolyList)
 
IntList FACTORY_PUBLIC neworderint (const CFList &PolyList)
 
CFList reorder (const Varlist &betterorder, const CFList &PS)
 
CFFList reorder (const Varlist &betterorder, const CFFList &PS)
 
ListCFList reorder (const Varlist &betterorder, const ListCFList &Q)
 
CanonicalForm FACTORY_PUBLIC extgcd (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b)
 CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b )
 

Variables

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

Detailed Description

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

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

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

Definition in file factory.h.

Macro Definition Documentation

◆ CF_INLINE [1/2]

#define CF_INLINE

Definition at line 208 of file factory.h.

◆ CF_INLINE [2/2]

#define CF_INLINE

Definition at line 208 of file factory.h.

◆ CF_NO_INLINE [1/2]

#define CF_NO_INLINE

Definition at line 210 of file factory.h.

◆ CF_NO_INLINE [2/2]

#define CF_NO_INLINE

Definition at line 210 of file factory.h.

◆ ISTREAM

#define ISTREAM   std::istream

Definition at line 41 of file factory.h.

◆ LEVELBASE

#define LEVELBASE   -1000000

Definition at line 82 of file factory.h.

◆ LEVELEXPR

#define LEVELEXPR   1000001

Definition at line 85 of file factory.h.

◆ LEVELQUOT

#define LEVELQUOT   1000000

Definition at line 84 of file factory.h.

◆ LEVELTRANS

#define LEVELTRANS   -500000

Definition at line 83 of file factory.h.

◆ OSTREAM

#define OSTREAM   std::ostream

Definition at line 40 of file factory.h.

Typedef Documentation

◆ CFAFactor

Definition at line 530 of file factory.h.

◆ CFAFList

Definition at line 531 of file factory.h.

◆ CFAFListIterator

Definition at line 532 of file factory.h.

◆ CFArray

Definition at line 538 of file factory.h.

◆ CFFactor

Definition at line 533 of file factory.h.

◆ CFFList

Definition at line 534 of file factory.h.

◆ CFFListIterator

Definition at line 535 of file factory.h.

◆ CFList

Definition at line 536 of file factory.h.

◆ CFListIterator

Definition at line 537 of file factory.h.

◆ CFMatrix

Definition at line 539 of file factory.h.

◆ Intarray

Definition at line 546 of file factory.h.

◆ IntList

Definition at line 542 of file factory.h.

◆ IntListIterator

Definition at line 543 of file factory.h.

◆ ListCFList

Definition at line 540 of file factory.h.

◆ ListCFListIterator

Definition at line 541 of file factory.h.

◆ MPList

Definition at line 986 of file factory.h.

◆ MPListIterator

Definition at line 987 of file factory.h.

◆ termList

Definition at line 799 of file factory.h.

◆ Varlist

Definition at line 544 of file factory.h.

◆ VarlistIterator

Definition at line 545 of file factory.h.

Function Documentation

◆ abs()

CanonicalForm abs ( const CanonicalForm & f)
inline

inline CanonicalForm abs ( const CanonicalForm & f )

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

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

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

Type info:

f: CurrentPP

Definition at line 638 of file factory.h.

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

◆ absFactorize()

absolute factorization of a multivariate poly over Q

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

Definition at line 262 of file facAbsFact.cc.

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

◆ apply()

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

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

apply() - apply mf to terms of f.

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

An example:

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

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

Definition at line 402 of file cf_ops.cc.

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

◆ basicSet()

CFList basicSet ( const CFList & PS)

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

Definition at line 150 of file cfCharSets.cc.

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

◆ bCommonDen()

CanonicalForm bCommonDen ( const CanonicalForm & f )

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

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

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

Type info:

f: CurrentPP

Definition at line 293 of file cf_algorithm.cc.

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

◆ blcm()

Definition at line 1816 of file canonicalform.cc.

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

◆ cf_getBigPrime()

int FACTORY_PUBLIC cf_getBigPrime ( int i)

Definition at line 39 of file cf_primes.cc.

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

◆ cf_getNumBigPrimes()

int FACTORY_PUBLIC cf_getNumBigPrimes ( )

Definition at line 45 of file cf_primes.cc.

46{
47 return NUMBIGPRIMES;
48}

◆ cf_getNumPrimes()

int FACTORY_PUBLIC cf_getNumPrimes ( )

Definition at line 23 of file cf_primes.cc.

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

◆ cf_getNumSmallPrimes()

int FACTORY_PUBLIC cf_getNumSmallPrimes ( )

Definition at line 34 of file cf_primes.cc.

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

◆ cf_getPrime()

int FACTORY_PUBLIC cf_getPrime ( int i)

Definition at line 14 of file cf_primes.cc.

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

◆ cf_getSmallPrime()

int FACTORY_PUBLIC cf_getSmallPrime ( int i)

Definition at line 28 of file cf_primes.cc.

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

◆ cf_HNF()

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

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

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

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

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

Definition at line 44 of file cf_hnf.cc.

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

◆ cf_LLL()

performs LLL reduction.

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

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

Note
: uses NTL or FLINT

Definition at line 66 of file cf_hnf.cc.

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

◆ charSeries()

ListCFList charSeries ( const CFList & L)

characteristic series

Definition at line 411 of file cfCharSets.cc.

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

◆ charSet()

CFList charSet ( const CFList & PS)

characteristic set

Definition at line 187 of file cfCharSets.cc.

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

◆ charSetN()

CFList charSetN ( const CFList & PS)

medial set

Definition at line 216 of file cfCharSets.cc.

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

◆ charSetViaCharSetN()

CFList charSetViaCharSetN ( const CFList & PS)

compute a characteristic set via medial set

Definition at line 246 of file cfCharSets.cc.

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

◆ charSetViaModCharSet() [1/2]

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

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

Definition at line 397 of file cfCharSets.cc.

398{
401}

◆ charSetViaModCharSet() [2/2]

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

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

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

Definition at line 356 of file cfCharSets.cc.

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

◆ chineseRemainder() [1/2]

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

chineseRemainder - integer chinese remaindering.

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

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

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

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

Definition at line 57 of file cf_chinese.cc.

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

◆ chineseRemainder() [2/2]

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

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

chineseRemainder - integer chinese remaindering.

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

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

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

Definition at line 124 of file cf_chinese.cc.

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

◆ chineseRemainderCached() [1/2]

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

Definition at line 308 of file cf_chinese.cc.

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

◆ chineseRemainderCached() [2/2]

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

Definition at line 290 of file cf_chinese.cc.

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

◆ compress() [1/3]

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

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

compress() - compress the canonical form f.

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

Definition at line 210 of file cf_map.cc.

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

◆ compress() [2/3]

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

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

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

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

Definition at line 349 of file cf_map.cc.

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

◆ compress() [3/3]

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

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

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

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

Definition at line 245 of file cf_map.cc.

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

◆ content() [1/2]

CanonicalForm content ( const CanonicalForm & f )

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

Normalizes result.

Definition at line 603 of file cf_gcd.cc.

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

◆ content() [2/2]

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

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

x should be a polynomial variable.

Definition at line 629 of file cf_gcd.cc.

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

◆ degree() [1/2]

int degree ( const CanonicalForm & f)
inline

Definition at line 457 of file factory.h.

457{ return f.degree(); }

◆ degree() [2/2]

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

Definition at line 460 of file factory.h.

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

◆ degrees()

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

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

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

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

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

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

Definition at line 493 of file cf_ops.cc.

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

◆ den()

CanonicalForm den ( const CanonicalForm & f)
inline

Definition at line 481 of file factory.h.

481{ return f.den(); }

◆ deriv()

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

Definition at line 487 of file factory.h.

487{ return f.deriv( x ); }

◆ determinant()

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

Definition at line 222 of file cf_linsys.cc.

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

◆ div()

◆ euclideanNorm()

CanonicalForm euclideanNorm ( const CanonicalForm & f)

CanonicalForm euclideanNorm ( const CanonicalForm & f )

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

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

Type info:

f: UVPoly( Z )

Definition at line 565 of file cf_algorithm.cc.

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

◆ ExtensionLevel()

int ExtensionLevel ( )

Definition at line 254 of file variable.cc.

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

◆ extgcd()

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

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

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

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

Definition at line 174 of file cfUnivarGcd.cc.

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

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

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

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

Definition at line 1043 of file facAlgFunc.cc.

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

◆ facAlgFunc2()

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

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

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

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

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

Definition at line 905 of file facAlgFunc.cc.

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

◆ factorize() [1/2]

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

factorization over $ F_p $ or $ Q $

Definition at line 409 of file cf_factor.cc.

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

◆ factorize() [2/2]

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

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

Definition at line 778 of file cf_factor.cc.

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

◆ factoryError_intern()

void factoryError_intern ( const char * s)

Definition at line 75 of file cf_util.cc.

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

◆ factoryrandom()

int factoryrandom ( int n)

random integers with abs less than n

Definition at line 180 of file cf_random.cc.

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

◆ factoryseed()

void FACTORY_PUBLIC factoryseed ( int s)

random seed initializer

Definition at line 189 of file cf_random.cc.

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

◆ Farey()

Farey rational reconstruction.

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

Definition at line 202 of file cf_chinese.cc.

203{
206 Variable x = f.mvar();
210#ifdef HAVE_FLINT
218#elif defined(HAVE_NTL)
220 ZZ bound;
221 SqrRoot (bound, NTLq/2);
222#else
223 factoryError("NTL/FLINT missing:Farey");
224#endif
225 for ( i = f; i.hasTerms(); i++ )
226 {
227 c = i.coeff();
228 if ( c.inCoeffDomain())
229 {
230#ifdef HAVE_FLINT
231 if (c.inZ())
232 {
235 result += power (x, i.exp())*(convertFmpq2CF(FLINTres));
236 }
237#elif defined(HAVE_NTL)
238 if (c.inZ())
239 {
241 bool lessZero= (sign (NTLc) == -1);
242 if (lessZero)
246 {
247 if (lessZero)
251 On (SW_RATIONAL);
252 result += power (x, i.exp())*(num/den);
254 }
255 }
256#else
257 if (c.inZ())
258 result += power (x, i.exp()) * Farey_n(c,q);
259#endif
260 else
261 result += power( x, i.exp() ) * Farey(c,q);
262 }
263 else
264 result += power( x, i.exp() ) * Farey(c,q);
265 }
266 if (is_rat) On(SW_RATIONAL);
267#ifdef HAVE_FLINT
271#endif
272 return result;
273}
CanonicalForm convertFmpq2CF(const fmpq_t q)
conversion of a FLINT rational to CanonicalForm
void convertCF2initFmpz(fmpz_t result, const CanonicalForm &f)
conversion of a factory integer to fmpz_t(init.)
CanonicalForm num(const CanonicalForm &f)
CanonicalForm den(const CanonicalForm &f)
CanonicalForm Farey(const CanonicalForm &f, const CanonicalForm &q)
Farey rational reconstruction.
static CanonicalForm bound(const CFMatrix &M)
Definition cf_linsys.cc:460
bool inZ() const
predicates

◆ fdivides() [1/2]

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

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

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

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

Type info:

f, g: Current

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

Developers note:

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

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

Definition at line 340 of file cf_algorithm.cc.

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

◆ fdivides() [2/2]

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

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

Definition at line 390 of file cf_algorithm.cc.

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

◆ gcd()

Definition at line 685 of file cf_gcd.cc.

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

◆ gcd_poly()

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

gcd_poly() - calculate polynomial gcd.

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

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

See also
gcd(), cf_defs.h

Definition at line 492 of file cf_gcd.cc.

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

◆ get_max_degree_Variable()

Variable get_max_degree_Variable ( const CanonicalForm & f)

get_max_degree_Variable returns Variable with highest degree.

We assume f is not a constant!

Definition at line 264 of file cf_factor.cc.

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

◆ get_Terms()

CFList get_Terms ( const CanonicalForm & f)

Definition at line 293 of file cf_factor.cc.

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

◆ getCharacteristic()

int FACTORY_PUBLIC getCharacteristic ( )

Definition at line 70 of file cf_char.cc.

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

◆ getDefaultExtName()

char getDefaultExtName ( )

Definition at line 249 of file variable.cc.

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

◆ getDefaultVarName()

char getDefaultVarName ( )

Definition at line 244 of file variable.cc.

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

◆ getGFDegree()

int getGFDegree ( )

Definition at line 75 of file cf_char.cc.

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

◆ getGFGenerator()

CanonicalForm getGFGenerator ( )

Definition at line 81 of file cf_char.cc.

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

◆ getMipo()

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

Definition at line 207 of file variable.cc.

208{
209 ASSERT( alpha.level() < 0 && alpha.level() != LEVELBASE, "illegal extension" );
211}
#define LEVELBASE
Definition cf_defs.h:25
InternalCF * copyObject()
Definition int_cf.h:62
InternalPoly * mipo()
Definition variable.cc:36
STATIC_VAR ext_entry * algextensions
Definition variable.cc:41

◆ getNumVars()

int getNumVars ( const CanonicalForm & f)

int getNumVars ( const CanonicalForm & f )

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

Definition at line 314 of file cf_ops.cc.

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

◆ getTerms()

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

get_Terms: Split the polynomial in the containing terms.

getTerms: the real work is done here.

Definition at line 283 of file cf_factor.cc.

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

◆ getVars()

CanonicalForm getVars ( const CanonicalForm & f )

getVars() - get polynomial variables of f.

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

Definition at line 350 of file cf_ops.cc.

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

◆ gf_gf2ff() [1/2]

int gf_gf2ff ( int a)

Definition at line 231 of file gfops.cc.

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

◆ gf_gf2ff() [2/2]

long gf_gf2ff ( long a)

Definition at line 209 of file gfops.cc.

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

◆ gf_isff() [1/2]

bool gf_isff ( int a)

Definition at line 264 of file gfops.cc.

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

◆ gf_isff() [2/2]

bool gf_isff ( long a)

Definition at line 253 of file gfops.cc.

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

◆ gf_value()

int gf_value ( const CanonicalForm & f)

Definition at line 60 of file singext.cc.

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

◆ gmp_denominator()

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

Definition at line 40 of file singext.cc.

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

◆ gmp_numerator()

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

Definition at line 20 of file singext.cc.

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

◆ hasFirstAlgVar()

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

check if poly f contains an algebraic variable a

Definition at line 679 of file cf_ops.cc.

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

◆ hasMipo()

bool hasMipo ( const Variable & alpha)

Definition at line 226 of file variable.cc.

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

◆ head()

CanonicalForm head ( const CanonicalForm & f)
inline

Definition at line 501 of file factory.h.

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

◆ headdegree()

int headdegree ( const CanonicalForm & f)
inline

Definition at line 510 of file factory.h.

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

◆ homogenize() [1/2]

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

homogenize homogenizes f with Variable x

Definition at line 317 of file cf_factor.cc.

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

◆ homogenize() [2/2]

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

Definition at line 357 of file cf_factor.cc.

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

◆ icontent()

CanonicalForm icontent ( const CanonicalForm & f )

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

Definition at line 74 of file cf_gcd.cc.

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

◆ igcd()

int igcd ( int a,
int b )

Definition at line 56 of file cf_util.cc.

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

◆ ilog2()

int ilog2 ( const CanonicalForm & a)
inline

Definition at line 493 of file factory.h.

493{ return a.ilog2(); }
int ilog2() const
int CanonicalForm::ilog2 () const

◆ ipower()

int FACTORY_PUBLIC ipower ( int b,
int m )

int ipower ( int b, int m )

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

Note: Beware of overflows.

Definition at line 27 of file cf_util.cc.

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

◆ irrCharSeries()

ListCFList FACTORY_PUBLIC irrCharSeries ( const CFList & PS)

irreducible characteristic series

Definition at line 568 of file cfCharSets.cc.

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

◆ is_imm()

int is_imm ( const InternalCF *const ptr)
inline

Definition at line 215 of file factory.h.

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

◆ isOn()

bool FACTORY_PUBLIC isOn ( int sw)

switches

Definition at line 1971 of file canonicalform.cc.

1972{
1973 return cf_glob_switches.isOn( sw );
1974}
INST_VAR CFSwitches cf_glob_switches
bool isOn(int s) const
check if 's' is on
Definition cf_switches.h:55

◆ isPurePoly()

bool isPurePoly ( const CanonicalForm & f)

Definition at line 248 of file cf_factor.cc.

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

◆ isPurePoly_m()

bool isPurePoly_m ( const CanonicalForm & f)

Definition at line 238 of file cf_factor.cc.

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

◆ lc()

CanonicalForm lc ( const CanonicalForm & f)
inline

Definition at line 445 of file factory.h.

445{ return f.lc(); }

◆ Lc()

CanonicalForm Lc ( const CanonicalForm & f)
inline

Definition at line 448 of file factory.h.

448{ return f.Lc(); }

◆ LC() [1/2]

CanonicalForm LC ( const CanonicalForm & f)
inline

Definition at line 451 of file factory.h.

451{ return f.LC(); }

◆ LC() [2/2]

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

Definition at line 454 of file factory.h.

454{ return f.LC( v ); }

◆ lcm()

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

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

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

Returns zero if one of f or g equals zero.

Definition at line 763 of file cf_gcd.cc.

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

◆ leftShift()

CanonicalForm leftShift ( const CanonicalForm & F,
int n )

left shift the main variable of F by n

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

Definition at line 697 of file cf_ops.cc.

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

◆ level() [1/2]

int level ( const CanonicalForm & f)
inline

Definition at line 472 of file factory.h.

472{ return f.level(); }

◆ level() [2/2]

int level ( const Variable & v)
inline

Definition at line 188 of file factory.h.

188{ return v.level(); }

◆ linearSystemSolve()

bool linearSystemSolve ( CFMatrix & M)

Definition at line 78 of file cf_linsys.cc.

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

◆ make_cf() [1/2]

Definition at line 66 of file singext.cc.

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

◆ make_cf() [2/2]

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

Definition at line 71 of file singext.cc.

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

◆ make_cf_from_gf()

CanonicalForm make_cf_from_gf ( const int z)

Definition at line 76 of file singext.cc.

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

◆ mapdomain()

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

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

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

Definition at line 440 of file cf_ops.cc.

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

◆ mapinto()

CanonicalForm mapinto ( const CanonicalForm & f)
inline

Definition at line 496 of file factory.h.

496{ return f.mapinto(); }

◆ maxNorm()

CanonicalForm maxNorm ( const CanonicalForm & f )

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

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

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

Type info:

f: CurrentPP

Definition at line 536 of file cf_algorithm.cc.

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

◆ mod()

◆ modCharSet() [1/2]

CFList modCharSet ( const CFList & PS,
bool removeContents )

Definition at line 404 of file cfCharSets.cc.

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

◆ modCharSet() [2/2]

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

modified medial set

Definition at line 284 of file cfCharSets.cc.

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

◆ mvar()

Variable mvar ( const CanonicalForm & f)
inline

Definition at line 475 of file factory.h.

475{ return f.mvar(); }

◆ name()

char name ( const Variable & v)
inline

Definition at line 189 of file factory.h.

189{ return v.name(); }
char name() const
Definition variable.cc:122

◆ neworder()

Varlist neworder ( const CFList & PolyList)

◆ newordercf()

CFList newordercf ( const CFList & PolyList)

Definition at line 75 of file cfCharSets.cc.

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

◆ neworderint()

IntList FACTORY_PUBLIC neworderint ( const CFList & PolyList)

Definition at line 88 of file cfCharSets.cc.

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

◆ num()

CanonicalForm num ( const CanonicalForm & f)
inline

Definition at line 478 of file factory.h.

478{ return f.num(); }

◆ Off()

void FACTORY_PUBLIC Off ( int sw)

switches

Definition at line 1964 of file canonicalform.cc.

1965{
1966 cf_glob_switches.Off( sw );
1967}
void Off(int s)
switch 's' off
Definition cf_switches.h:53

◆ On()

switches

Definition at line 1957 of file canonicalform.cc.

1958{
1959 cf_glob_switches.On( sw );
1960}
void On(int s)
switch 's' on
Definition cf_switches.h:51

◆ operator%()

◆ operator*()

See also
CanonicalForm::operator *=()

Definition at line 524 of file cf_inline.cc.

525{
527 result *= rhs;
528 return result;
529}

◆ operator+()

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

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

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

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

Type info:

lhs, rhs: CurrentPP

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

Developers note:

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

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

See also
CanonicalForm::operator +=()

Definition at line 503 of file cf_inline.cc.

504{
506 result += rhs;
507 return result;
508}

◆ operator-()

◆ operator/()

◆ power() [1/2]

exponentiation

Definition at line 1896 of file canonicalform.cc.

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

◆ power() [2/2]

exponentiation

Definition at line 1939 of file canonicalform.cc.

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

◆ pp()

CanonicalForm pp ( const CanonicalForm & f )

pp() - return primitive part of f.

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

Definition at line 676 of file cf_gcd.cc.

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

◆ Prem()

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

Definition at line 616 of file cfCharSetsUtil.cc.

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

◆ probIrredTest()

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

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

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

Definition at line 63 of file facIrredTest.cc.

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

◆ prune()

void FACTORY_PUBLIC prune ( Variable & alpha)

Definition at line 261 of file variable.cc.

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

◆ prune1()

void prune1 ( const Variable & alpha)

Definition at line 291 of file variable.cc.

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

◆ psq()

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

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

‘g’ must not equal zero.

Type info:

f, g: Current x: Polynomial

Developers note:

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

See also
psr(), psqr()

Definition at line 172 of file cf_algorithm.cc.

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

◆ psqr()

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

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

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

See ‘psr()’ for more detailed information.

Type info:

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

Developers note:

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

See also
psr(), psq()

Definition at line 223 of file cf_algorithm.cc.

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

◆ psr()

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

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

‘g’ must not equal zero.

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

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

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

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

Type info:

f, g: Current x: Polynomial

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

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

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

Developers note:

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

See also
psq(), psqr()

Definition at line 117 of file cf_algorithm.cc.

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

◆ reduce()

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

Definition at line 660 of file cf_ops.cc.

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

◆ reorder() [1/3]

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

Definition at line 120 of file cfCharSets.cc.

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

◆ reorder() [2/3]

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

Definition at line 101 of file cfCharSets.cc.

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

◆ reorder() [3/3]

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

Definition at line 140 of file cfCharSets.cc.

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

◆ replaceLc()

Definition at line 90 of file fac_util.cc.

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

◆ replacevar()

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

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

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

Definition at line 271 of file cf_ops.cc.

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

◆ resultant()

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

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

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

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

Definition at line 173 of file cf_resultant.cc.

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

◆ resultantZ()

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

modular resultant algorihtm over Z

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

Definition at line 559 of file cfModResultant.cc.

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

◆ rootOf()

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

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

returns a symbolic root of polynomial with name name.

Note
: algebraic variables have a level < 0

Use it to define algebraic variables

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

Definition at line 162 of file variable.cc.

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

◆ setCharacteristic() [1/3]

void FACTORY_PUBLIC setCharacteristic ( int c)

Definition at line 28 of file cf_char.cc.

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

◆ setCharacteristic() [2/3]

void setCharacteristic ( int c,
int n )

◆ setCharacteristic() [3/3]

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

Definition at line 61 of file cf_char.cc.

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

◆ setMipo()

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

Definition at line 219 of file variable.cc.

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

◆ setReduce()

void setReduce ( const Variable & alpha,
bool reduce )

Definition at line 238 of file variable.cc.

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

◆ sign()

int sign ( const CanonicalForm & a)
inline

Definition at line 484 of file factory.h.

484{ return a.sign(); }
int sign() const
int CanonicalForm::sign () const

◆ size() [1/2]

int size ( const CanonicalForm & f)

int size ( const CanonicalForm & f )

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

Returns one if f is in an coefficient domain.

Definition at line 627 of file cf_ops.cc.

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

◆ size() [2/2]

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

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

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

Returns one if f is in an base domain.

Definition at line 600 of file cf_ops.cc.

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

◆ size_maxexp()

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

Definition at line 641 of file cf_ops.cc.

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

◆ sqrFree()

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

squarefree factorization

Definition at line 961 of file cf_factor.cc.

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

◆ sqrt()

CanonicalForm sqrt ( const CanonicalForm & a)
inline

Definition at line 490 of file factory.h.

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

◆ subResChain()

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

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

subResChain() - caculate extended subresultant chain.

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

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

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

Definition at line 42 of file cf_resultant.cc.

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

◆ swapvar()

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

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

Definition at line 168 of file cf_ops.cc.

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

◆ tailcoeff() [1/2]

CanonicalForm tailcoeff ( const CanonicalForm & f)
inline

Definition at line 466 of file factory.h.

466{ return f.tailcoeff(); }

◆ tailcoeff() [2/2]

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

Definition at line 469 of file factory.h.

469{ return f.tailcoeff(v); }

◆ taildegree()

int taildegree ( const CanonicalForm & f)
inline

Definition at line 463 of file factory.h.

463{ return f.taildegree(); }

◆ totaldegree() [1/2]

int totaldegree ( const CanonicalForm & f)

int totaldegree ( const CanonicalForm & f )

totaldegree() - return the total degree of f.

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

Definition at line 523 of file cf_ops.cc.

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

◆ totaldegree() [2/2]

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

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

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

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

Definition at line 554 of file cf_ops.cc.

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

◆ tryFdivides()

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

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

Definition at line 456 of file cf_algorithm.cc.

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

◆ vcontent()

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

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

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

Definition at line 653 of file cf_gcd.cc.

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

Variable Documentation

◆ factoryConfiguration

const char factoryConfiguration[]
extern

◆ factoryError

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

Definition at line 1127 of file factory.h.

◆ singular_homog_flag

EXTERN_VAR int singular_homog_flag

Definition at line 586 of file factory.h.

◆ SW_BERLEKAMP

const int SW_BERLEKAMP =10
static

set to 1 to use Factorys Berlekamp alg.

Definition at line 108 of file factory.h.

◆ SW_FAC_QUADRATICLIFT

const int SW_FAC_QUADRATICLIFT =11
static

Definition at line 110 of file factory.h.

◆ SW_RATIONAL

const int SW_RATIONAL = 0
static

set to 1 for computations over Q

Definition at line 88 of file factory.h.

◆ SW_SYMMETRIC_FF

const int SW_SYMMETRIC_FF = 1
static

set to 1 for symmetric representation over F_q

Definition at line 90 of file factory.h.

◆ SW_USE_CHINREM_GCD

const int SW_USE_CHINREM_GCD =5
static

set to 1 to use modular gcd over Z

Definition at line 98 of file factory.h.

◆ SW_USE_EZGCD

const int SW_USE_EZGCD = 2
static

set to 1 to use EZGCD over Z

Definition at line 92 of file factory.h.

◆ SW_USE_EZGCD_P

const int SW_USE_EZGCD_P = 3
static

set to 1 to use EZGCD over F_q

Definition at line 94 of file factory.h.

◆ SW_USE_FF_MOD_GCD

const int SW_USE_FF_MOD_GCD =7
static

set to 1 to use modular GCD over F_q

Definition at line 102 of file factory.h.

◆ SW_USE_FL_FAC_0

const int SW_USE_FL_FAC_0 =13
static

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

Definition at line 114 of file factory.h.

◆ SW_USE_FL_FAC_0A

const int SW_USE_FL_FAC_0A =14
static

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

Definition at line 116 of file factory.h.

◆ SW_USE_FL_FAC_P

const int SW_USE_FL_FAC_P =12
static

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

Definition at line 112 of file factory.h.

◆ SW_USE_FL_GCD_0

const int SW_USE_FL_GCD_0 =9
static

set to 1 to use Flints gcd over Q/Z

Definition at line 106 of file factory.h.

◆ SW_USE_FL_GCD_P

const int SW_USE_FL_GCD_P =8
static

set to 1 to use Flints gcd over F_p

Definition at line 104 of file factory.h.

◆ SW_USE_NTL_SORT

const int SW_USE_NTL_SORT =4
static

set to 1 to sort factors in a factorization

Definition at line 96 of file factory.h.

◆ SW_USE_QGCD

const int SW_USE_QGCD =6
static

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

Definition at line 100 of file factory.h.