 |
My Project
UNKNOWN_GIT_VERSION
|
‘factory.h’ is the user interface to Factory.
More...
Go to the source code of this file.
|
int | cf_getPrime (int i) |
|
int | cf_getNumPrimes () |
|
int | cf_getSmallPrime (int i) |
|
int | cf_getNumSmallPrimes () |
|
int | cf_getBigPrime (int i) |
|
int | cf_getNumBigPrimes () |
|
Variable | rootOf (const CanonicalForm &, char name='@') |
| returns a symbolic root of polynomial with name name Use it to define algebraic variables More...
|
|
int | level (const Variable &v) |
|
char | name (const Variable &v) |
|
void | setReduce (const Variable &alpha, bool reduce) |
|
void | setMipo (const Variable &alpha, const CanonicalForm &mipo) |
|
CanonicalForm | getMipo (const Variable &alpha, const Variable &x) |
|
bool | hasMipo (const Variable &alpha) |
|
char | getDefaultVarName () |
|
char | getDefaultExtName () |
|
void | prune (Variable &alpha) |
|
void | prune1 (const Variable &alpha) |
|
int | ExtensionLevel () |
|
int | is_imm (const InternalCF *const ptr) |
|
CF_INLINE CanonicalForm | operator+ (const CanonicalForm &, const CanonicalForm &) |
| CF_INLINE CanonicalForm operator +, -, *, /, % ( const CanonicalForm & lhs, const CanonicalForm & rhs ) More...
|
|
CF_NO_INLINE CanonicalForm | operator- (const CanonicalForm &, const CanonicalForm &) |
|
CF_INLINE CanonicalForm | operator* (const CanonicalForm &, const CanonicalForm &) |
|
CF_NO_INLINE CanonicalForm | operator/ (const CanonicalForm &, const CanonicalForm &) |
|
CF_NO_INLINE CanonicalForm | operator% (const CanonicalForm &, const CanonicalForm &) |
|
CF_NO_INLINE CanonicalForm | div (const CanonicalForm &, const CanonicalForm &) |
| CF_INLINE CanonicalForm div, mod ( const CanonicalForm & lhs, const CanonicalForm & rhs ) More...
|
|
CF_NO_INLINE CanonicalForm | mod (const CanonicalForm &, const CanonicalForm &) |
|
CanonicalForm | blcm (const CanonicalForm &f, const CanonicalForm &g) |
|
CanonicalForm | power (const CanonicalForm &f, int n) |
| exponentiation More...
|
|
CanonicalForm | power (const Variable &v, int n) |
| exponentiation More...
|
|
CanonicalForm | gcd (const CanonicalForm &, const CanonicalForm &) |
|
CanonicalForm | gcd_poly (const CanonicalForm &f, const CanonicalForm &g) |
| CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g ) More...
|
|
CanonicalForm | lcm (const CanonicalForm &, const CanonicalForm &) |
| CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g ) More...
|
|
CanonicalForm | pp (const CanonicalForm &) |
| CanonicalForm pp ( const CanonicalForm & f ) More...
|
|
CanonicalForm | content (const CanonicalForm &) |
| CanonicalForm content ( const CanonicalForm & f ) More...
|
|
CanonicalForm | content (const CanonicalForm &, const Variable &) |
| CanonicalForm content ( const CanonicalForm & f, const Variable & x ) More...
|
|
CanonicalForm | icontent (const CanonicalForm &f) |
| CanonicalForm icontent ( const CanonicalForm & f ) More...
|
|
CanonicalForm | vcontent (const CanonicalForm &f, const Variable &x) |
| CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x ) More...
|
|
CanonicalForm | swapvar (const CanonicalForm &, const Variable &, const Variable &) |
| swapvar() - swap variables x1 and x2 in f. More...
|
|
CanonicalForm | replacevar (const CanonicalForm &, const Variable &, const Variable &) |
| CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 ) More...
|
|
int | getNumVars (const CanonicalForm &f) |
| int getNumVars ( const CanonicalForm & f ) More...
|
|
CanonicalForm | getVars (const CanonicalForm &f) |
| CanonicalForm getVars ( const CanonicalForm & f ) More...
|
|
CanonicalForm | apply (const CanonicalForm &f, void(*mf)(CanonicalForm &, int &)) |
| CanonicalForm apply ( const CanonicalForm & f, void (*mf)( CanonicalForm &, int & ) ) More...
|
|
CanonicalForm | mapdomain (const CanonicalForm &f, CanonicalForm(*mf)(const CanonicalForm &)) |
| CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) ) More...
|
|
int * | degrees (const CanonicalForm &f, int *degs=0) |
| int * degrees ( const CanonicalForm & f, int * degs ) More...
|
|
int | totaldegree (const CanonicalForm &f) |
| int totaldegree ( const CanonicalForm & f ) More...
|
|
int | totaldegree (const CanonicalForm &f, const Variable &v1, const Variable &v2) |
| int totaldegree ( const CanonicalForm & f, const Variable & v1, const Variable & v2 ) More...
|
|
int | size (const CanonicalForm &f, const Variable &v) |
| int size ( const CanonicalForm & f, const Variable & v ) More...
|
|
int | size (const CanonicalForm &f) |
| int size ( const CanonicalForm & f ) More...
|
|
CanonicalForm | reduce (const CanonicalForm &f, const CanonicalForm &M) |
| polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of f are reduced modulo M More...
|
|
bool | hasFirstAlgVar (const CanonicalForm &f, Variable &a) |
| check if poly f contains an algebraic variable a More...
|
|
CanonicalForm | leftShift (const CanonicalForm &F, int n) |
| left shift the main variable of F by n More...
|
|
CanonicalForm | lc (const CanonicalForm &f) |
|
CanonicalForm | Lc (const CanonicalForm &f) |
|
CanonicalForm | LC (const CanonicalForm &f) |
|
CanonicalForm | LC (const CanonicalForm &f, const Variable &v) |
|
int | degree (const CanonicalForm &f) |
|
int | degree (const CanonicalForm &f, const Variable &v) |
|
int | taildegree (const CanonicalForm &f) |
|
CanonicalForm | tailcoeff (const CanonicalForm &f) |
|
CanonicalForm | tailcoeff (const CanonicalForm &f, const Variable &v) |
|
int | level (const CanonicalForm &f) |
|
Variable | mvar (const CanonicalForm &f) |
|
CanonicalForm | num (const CanonicalForm &f) |
|
CanonicalForm | den (const CanonicalForm &f) |
|
int | sign (const CanonicalForm &a) |
|
CanonicalForm | deriv (const CanonicalForm &f, const Variable &x) |
|
CanonicalForm | sqrt (const CanonicalForm &a) |
|
int | ilog2 (const CanonicalForm &a) |
|
CanonicalForm | mapinto (const CanonicalForm &f) |
|
CanonicalForm | head (const CanonicalForm &f) |
|
int | headdegree (const CanonicalForm &f) |
|
void | setCharacteristic (int c) |
|
void | setCharacteristic (int c, int n) |
|
void | setCharacteristic (int c, int n, char name) |
|
int | getCharacteristic () |
|
int | getGFDegree () |
|
CanonicalForm | getGFGenerator () |
|
void | On (int) |
| switches More...
|
|
void | Off (int) |
| switches More...
|
|
bool | isOn (int) |
| switches More...
|
|
CanonicalForm | psr (const CanonicalForm &f, const CanonicalForm &g, const Variable &x) |
| CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
|
|
CanonicalForm | psq (const CanonicalForm &f, const CanonicalForm &g, const Variable &x) |
| CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
|
|
void | psqr (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, const Variable &x) |
| void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable & x ) More...
|
|
CanonicalForm | bCommonDen (const CanonicalForm &f) |
| CanonicalForm bCommonDen ( const CanonicalForm & f ) More...
|
|
bool | fdivides (const CanonicalForm &f, const CanonicalForm &g) |
| bool fdivides ( const CanonicalForm & f, const CanonicalForm & g ) More...
|
|
bool | fdivides (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm ") |
| same as fdivides if true returns quotient quot of g by f otherwise quot == 0 More...
|
|
bool | tryFdivides (const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail) |
| same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f More...
|
|
CanonicalForm | maxNorm (const CanonicalForm &f) |
| CanonicalForm maxNorm ( const CanonicalForm & f ) More...
|
|
CanonicalForm | euclideanNorm (const CanonicalForm &f) |
| CanonicalForm euclideanNorm ( const CanonicalForm & f ) More...
|
|
void | chineseRemainder (const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew) |
| void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew ) More...
|
|
void | chineseRemainder (const CFArray &x, const CFArray &q, CanonicalForm &xnew, CanonicalForm &qnew) |
| void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew ) More...
|
|
void | chineseRemainderCached (CFArray &a, CFArray &n, CanonicalForm &xnew, CanonicalForm &prod, CFArray &inv) |
|
CanonicalForm | Farey (const CanonicalForm &f, const CanonicalForm &q) |
| Farey rational reconstruction. More...
|
|
bool | isPurePoly (const CanonicalForm &f) |
|
bool | isPurePoly_m (const CanonicalForm &f) |
|
CFFList | factorize (const CanonicalForm &f, bool issqrfree=false) |
| factorization over or More...
|
|
CFFList | factorize (const CanonicalForm &f, const Variable &alpha) |
| factorization over or More...
|
|
CFFList | sqrFree (const CanonicalForm &f, bool sort=false) |
| squarefree factorization More...
|
|
CanonicalForm | homogenize (const CanonicalForm &f, const Variable &x) |
| homogenize homogenizes f with Variable x More...
|
|
CanonicalForm | homogenize (const CanonicalForm &f, const Variable &x, const Variable &v1, const Variable &v2) |
|
Variable | get_max_degree_Variable (const CanonicalForm &f) |
| get_max_degree_Variable returns Variable with highest degree. More...
|
|
CFList | get_Terms (const CanonicalForm &f) |
|
void | getTerms (const CanonicalForm &f, const CanonicalForm &t, CFList &result) |
| get_Terms: Split the polynomial in the containing terms. More...
|
|
bool | linearSystemSolve (CFMatrix &M) |
|
CanonicalForm | determinant (const CFMatrix &M, int n) |
|
CFArray | subResChain (const CanonicalForm &f, const CanonicalForm &g, const Variable &x) |
| CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
|
|
CanonicalForm | resultant (const CanonicalForm &f, const CanonicalForm &g, const Variable &x) |
| CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
|
|
CanonicalForm | abs (const CanonicalForm &f) |
| inline CanonicalForm abs ( const CanonicalForm & f ) More...
|
|
int | factoryrandom (int n) |
| random integers with abs less than n More...
|
|
void | factoryseed (int s) |
| random seed initializer More...
|
|
CanonicalForm | replaceLc (const CanonicalForm &f, const CanonicalForm &c) |
|
CanonicalForm | compress (const CanonicalForm &f, CFMap &m) |
| CanonicalForm compress ( const CanonicalForm & f, CFMap & m ) More...
|
|
void | compress (const CFArray &a, CFMap &M, CFMap &N) |
| void compress ( const CFArray & a, CFMap & M, CFMap & N ) More...
|
|
void | compress (const CanonicalForm &f, const CanonicalForm &g, CFMap &M, CFMap &N) |
| void compress ( const CanonicalForm & f, const CanonicalForm & g, CFMap & M, CFMap & N ) More...
|
|
long | gf_gf2ff (long a) |
|
int | gf_gf2ff (int a) |
|
bool | gf_isff (long a) |
|
bool | gf_isff (int a) |
|
CFMatrix * | cf_HNF (CFMatrix &A) |
| The input matrix A is square matrix of integers output: the Hermite Normal Form of A; that is, the unique m x m matrix whose rows span L, such that. More...
|
|
CFMatrix * | cf_LLL (CFMatrix &A) |
| performs LLL reduction. More...
|
|
void | gmp_numerator (const CanonicalForm &f, mpz_ptr result) |
|
void | gmp_denominator (const CanonicalForm &f, mpz_ptr result) |
|
int | gf_value (const CanonicalForm &f) |
|
CanonicalForm | make_cf (const mpz_ptr n) |
|
CanonicalForm | make_cf (const mpz_ptr n, const mpz_ptr d, bool normalize) |
|
CanonicalForm | make_cf_from_gf (const int z) |
|
int | igcd (int a, int b) |
|
int | ipower (int b, int n) |
| int ipower ( int b, int m ) More...
|
|
void | factoryError_intern (const char *s) |
|
int | probIrredTest (const CanonicalForm &F, double error) |
| given some error probIrredTest detects irreducibility or reducibility of F with confidence level 1-error More...
|
|
CFAFList | absFactorize (const CanonicalForm &G) |
| absolute factorization of a multivariate poly over Q More...
|
|
CanonicalForm | resultantZ (const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob=true) |
| modular resultant algorihtm over Z More...
|
|
CFFList | facAlgFunc2 (const CanonicalForm &f, const CFList &as) |
| factorize a polynomial f that is irreducible over the ground field modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. , and each element of as is assumed to be integral as well. must be either or . More...
|
|
CFFList | facAlgFunc (const CanonicalForm &f, const CFList &as) |
| factorize a polynomial f modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. , and each element of as is assumed to be integral as well. must be either or . More...
|
|
CanonicalForm | Prem (const CanonicalForm &F, const CanonicalForm &G) |
| pseudo remainder of F by G with certain factors of LC (g) cancelled More...
|
|
CFList | basicSet (const CFList &PS) |
| basic set in the sense of Wang a.k.a. minimal ascending set in the sense of Greuel/Pfister More...
|
|
CFList | charSet (const CFList &PS) |
| characteristic set More...
|
|
CFList | modCharSet (const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true) |
| modified medial set More...
|
|
CFList | modCharSet (const CFList &PS, bool removeContents) |
|
CFList | charSetViaCharSetN (const CFList &PS) |
| compute a characteristic set via medial set More...
|
|
CFList | charSetN (const CFList &PS) |
| medial set More...
|
|
CFList | charSetViaModCharSet (const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true) |
| modified characteristic set, i.e. a characteristic set with certain factors removed More...
|
|
CFList | charSetViaModCharSet (const CFList &PS, bool removeContents=true) |
| modified characteristic set, i.e. a characteristic set with certain factors removed More...
|
|
ListCFList | charSeries (const CFList &L) |
| characteristic series More...
|
|
ListCFList | irrCharSeries (const CFList &PS) |
| irreducible characteristic series More...
|
|
Varlist | neworder (const CFList &PolyList) |
|
CFList | newordercf (const CFList &PolyList) |
|
IntList | neworderint (const CFList &PolyList) |
|
CFList | reorder (const Varlist &betterorder, const CFList &PS) |
|
CFFList | reorder (const Varlist &betterorder, const CFFList &PS) |
|
ListCFList | reorder (const Varlist &betterorder, const ListCFList &Q) |
|
CanonicalForm | extgcd (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &a, CanonicalForm &b) |
| CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b ) More...
|
|
‘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.
◆ CF_INLINE [1/2]
◆ CF_INLINE [2/2]
◆ CF_NO_INLINE [1/2]
◆ CF_NO_INLINE [2/2]
◆ FiniteFieldDomain
#define FiniteFieldDomain 3 |
◆ GaloisFieldDomain
#define GaloisFieldDomain 4 |
◆ IntegerDomain
◆ ISTREAM
#define ISTREAM std::istream |
◆ LEVELBASE
#define LEVELBASE -1000000 |
◆ LEVELEXPR
#define LEVELEXPR 1000001 |
◆ LEVELQUOT
#define LEVELQUOT 1000000 |
◆ LEVELTRANS
#define LEVELTRANS -500000 |
◆ OSTREAM
#define OSTREAM std::ostream |
◆ RationalDomain
◆ UndefinedDomain
#define UndefinedDomain 32000 |
◆ CFAFactor
◆ CFAFList
◆ CFAFListIterator
◆ CFArray
◆ CFFactor
◆ CFFList
◆ CFFListIterator
◆ CFList
◆ CFListIterator
◆ CFMatrix
◆ Intarray
◆ IntList
◆ IntListIterator
◆ ListCFList
◆ ListCFListIterator
◆ MPList
◆ MPListIterator
◆ termList
◆ Varlist
◆ VarlistIterator
◆ abs()
inline CanonicalForm abs ( const CanonicalForm & f )
abs() - return absolute value of ‘f’.
The absolute value is defined in terms of the function ‘sign()’. If it reports negative sign for ‘f’ than -‘f’ is returned, otherwise ‘f’.
This behaviour is most useful for integers and rationals. But it may be used to sign-normalize the leading coefficient of arbitrary polynomials, too.
Type info:
f: CurrentPP
Definition at line 626 of file factory.h.
◆ 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
-
Definition at line 267 of file facAbsFact.cc.
292 for (;
i.hasItem();
i++)
◆ apply()
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:
Then apply( f, diff ) is differentation of f with respect to the main variable of f.
Definition at line 402 of file cf_ops.cc.
404 if (
f.inCoeffDomain() )
409 ASSERT(
exp == 0,
"illegal result, do not know what variable to use" );
418 for (
i =
f;
i.hasTerms();
i++ )
◆ basicSet()
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.
174 for (
i= QS;
i.hasItem();
i++)
176 if (
degree (
i.getItem(), cb) < degb)
◆ 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.
◆ blcm()
◆ cf_getBigPrime()
int cf_getBigPrime |
( |
int |
i | ) |
|
◆ cf_getNumBigPrimes()
int cf_getNumBigPrimes |
( |
| ) |
|
◆ cf_getNumPrimes()
◆ cf_getNumSmallPrimes()
int cf_getNumSmallPrimes |
( |
| ) |
|
◆ cf_getPrime()
◆ cf_getSmallPrime()
int cf_getSmallPrime |
( |
int |
i | ) |
|
◆ 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 38 of file cf_hnf.cc.
◆ 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
Definition at line 48 of file cf_hnf.cc.
◆ charSeries()
characteristic series
Definition at line 411 of file cfCharSets.cc.
441 select (ppi,
l.length(), ppi1, ppi2);
450 if (
l.length() - 3 < highestLevel)
◆ charSet()
characteristic set
Definition at line 187 of file cfCharSets.cc.
189 CFList QS= PS, RS= PS, CSet, tmp;
193 while (!RS.isEmpty())
198 if (CSet.length() > 0 && CSet.getFirst().level() > 0)
201 for (
i= tmp;
i.hasItem();
i++)
203 r=
Prem (
i.getItem(), CSet);
◆ charSetN()
medial set
Definition at line 216 of file cfCharSets.cc.
218 CFList QS= PS, RS= PS, CSet, tmp;
222 while (!RS.isEmpty())
228 if (CSet.length() > 0 && CSet.getFirst().level() > 0)
231 for (
i= tmp;
i.hasItem();
i++)
233 r=
Prem (
i.getItem(), CSet);
237 QS=
Union (CSet, RS);
◆ charSetViaCharSetN()
compute a characteristic set via medial set
Definition at line 246 of file cfCharSets.cc.
256 for (iter2= sqrfFactors; iter2.
hasItem(); iter2++)
257 sqrf *= iter2.
getItem().factor();
263 if (
result.isEmpty() ||
result.getFirst().inCoeffDomain())
◆ charSetViaModCharSet() [1/2]
modified characteristic set, i.e. a characteristic set with certain factors removed
Definition at line 397 of file cfCharSets.cc.
◆ charSetViaModCharSet() [2/2]
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.
367 for (iter2= sqrfFactors; iter2.
hasItem(); iter2++)
368 sqrf *= iter2.
getItem().factor();
376 if (
result.isEmpty() ||
result.getFirst().inCoeffDomain())
◆ 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 52 of file cf_chinese.cc.
◆ chineseRemainder() [2/2]
void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew )
chineseRemainder - integer chinese remaindering.
Calculate xnew such that xnew=x[i] (mod q[i]) and qnew is the product of all q[i]. q[i] should be positive integers, pairwise prime. x[i] should be polynomials with integer coefficients. If all coefficients of all x[i] are positive integers, the result is guaranteed to have positive coefficients, too.
This is a standard algorithm, too, except for the fact that we use a divide-and-conquer method instead of a linear approach to calculate the remainder.
Note: Be sure you are calculating in Z, and not in Q!
Definition at line 119 of file cf_chinese.cc.
121 DEBINCLEVEL( cerr,
"chineseRemainder( ... CFArray ... )" );
123 ASSERT(
x.min() == q.
min() &&
x.size() == q.
size(),
"incompatible arrays" );
125 int i,
j, n =
x.size(), start =
x.min();
127 DEBOUTLN( cerr,
"array size = " << n );
132 while (
i < start + n - 1 )
158 DEBDECLEVEL( cerr,
"chineseRemainder( ... CFArray ... )" );
◆ chineseRemainderCached()
◆ compress() [1/3]
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.
219 while( degs[
i] == 0 )
i++;
◆ compress() [2/3]
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.
351 int n =
tmax(
f.level(),
g.level() );
356 for (
i = 0;
i <= n;
i++ )
376 if ( (
i !=
k ) && (
i != pe ) && (
i != p1 ) )
◆ compress() [3/3]
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.
254 for (
i = a.
min() + 1;
i <= a.
max();
i++ )
255 if (
level( a[
i] ) > maxlevel )
262 for (
i = maxlevel;
i >= 1;
i-- )
276 while (
i <= maxlevel )
◆ content() [1/2]
◆ content() [2/2]
◆ degree() [1/2]
Definition at line 446 of file factory.h.
446 {
return f.degree(); }
◆ degree() [2/2]
Definition at line 449 of file factory.h.
449 {
return f.degree(
v ); }
◆ degrees()
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.
495 if (
f.inCoeffDomain() )
◆ den()
◆ deriv()
Definition at line 476 of file factory.h.
476 {
return f.deriv(
x ); }
◆ determinant()
Definition at line 222 of file cf_linsys.cc.
226 ASSERT( rows <=
M.rows() && rows <=
M.columns() && rows > 0,
"undefined determinant" );
229 else if ( rows == 2 )
230 return M(1,1)*
M(2,2)-
M(2,1)*
M(1,2);
235 int n,
i, intdet,
p, pno;
236 for (
i = 0;
i < rows;
i++ )
238 mm[
i] =
new int[rows];
278 for (
i = 0;
i < rows;
i++ )
288 for (
i = 1;
i <= rows;
i++ ) {
290 for (
j =
i+1;
j <= rows;
j++ ) {
296 if (
pivot.isZero() )
303 for (
j =
i+1;
j <= rows;
j++ )
310 for (
k =
i+1;
k <= rows;
k++ )
316 for (
i = 1;
i <= rows;
i++ )
318 return pivot / divisor;
◆ div()
◆ euclideanNorm()
CanonicalForm euclideanNorm ( const CanonicalForm & f )
euclideanNorm() - return Euclidean norm of ‘f’.
Returns the largest integer smaller or equal norm(‘f’) = sqrt(sum( ‘f’[i]^2 )).
Type info:
f: UVPoly( Z )
Definition at line 563 of file cf_algorithm.cc.
565 ASSERT( (
f.inBaseDomain() ||
f.isUnivariate()) &&
f.LC().inZ(),
566 "type error: univariate poly over Z expected" );
◆ ExtensionLevel()
◆ extgcd()
CanonicalForm extgcd ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & a, CanonicalForm & b )
extgcd() - returns polynomial extended gcd of f and g.
Returns gcd(f, g) and a and b sucht that f*a+g*b=gcd(f, g). The gcd is calculated using an extended euclidean polynomial remainder sequence, so f and g should be polynomials over an euclidean domain. Normalizes result.
Note: be sure that f and g have the same level!
Definition at line 173 of file cfUnivarGcd.cc.
192 nmod_poly_t F1, G1,
A,
B,
R;
198 nmod_poly_xgcd (
R,
A,
B, F1, G1);
239 fmpq_poly_xgcd (
R,
A,
B, F1, G1);
243 fmpq_poly_clear (F1);
244 fmpq_poly_clear (G1);
264 XGCD(RR,
A,
B,F1,G1,1);
276 XGCD (RR,
A,
B,F1,G1,1);
284 XGCD(RR,
A,
B,F1,G1,1);
295 XGCD (RR,
A,
B,F1,G1,1);
312 while ( ! p1.isZero() )
322 a = f0 / ( contf * contp0 );
323 b = g0 / ( contg * contp0 );
◆ facAlgFunc()
factorize a polynomial f modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e.
, and each element of as is assumed to be integral as well.
must be either
or
.
- Returns
- the returned factors are not necessarily monic but only primitive and the product of the factors equals f up to a unit.
factorize a polynomial f modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e.
, and each element of as is assumed to be integral as well.
must be either
or
.
- Parameters
-
[in] | f | univariate poly |
[in] | as | irreducible characteristic set |
Definition at line 1043 of file facAlgFunc.cc.
1049 if (Factors.
getFirst().factor().inCoeffDomain())
1072 j.getItem().exp()*
i.getItem().exp()));
◆ facAlgFunc2()
factorize a polynomial f that is irreducible over the ground field modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e.
, and each element of as is assumed to be integral as well.
must be either
or
.
- Returns
- the returned factors are not necessarily monic but only primitive and the product of the factors equals f up to a unit.
factorize a polynomial f that is irreducible over the ground field modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e.
, and each element of as is assumed to be integral as well.
must be either
or
.
- Parameters
-
[in] | f | univariate poly |
[in] | as | irreducible characteristic set |
Definition at line 905 of file facAlgFunc.cc.
930 for (
int ii= 1; ii <
level (vf); ii++)
933 for (
i= as;
i.hasItem();
i++)
961 bool isFunctionField= (newuord.
length() > 0);
968 bool derivZero=
f.deriv().isZero();
969 if (isFunctionField && (
degree (Fgcd,
f.mvar()) > 0) && !derivZero)
992 for (
i= Astar;
i.hasItem();
i++)
997 if (newuord.
length() == 0)
1004 Factorlist=
Trager(
f, Astar, vminpoly, as, isFunctionField);
1021 Factorlist=
Trager (
f, Astar, vminpoly, as, isFunctionField);
1030 Factorlist=
Trager (
f, Astar, vminpoly, as, isFunctionField);
◆ factorize() [1/2]
factorization over
or
Definition at line 390 of file cf_factor.cc.
392 if (
f.inCoeffDomain() )
397 ( const CanonicalForm & f, const Variable & alpha ) instead");
400 if (!
f.isUnivariate() )
412 for (
j=Intermediatelist;
j.hasItem();
j++ )
415 CFFactor( n(
j.getItem().factor()),
j.getItem().exp()) );
419 for (
j=Homoglist;
j.hasItem();
j++ )
423 d_xn -= (
degree(unhomogelem,
xn)*
j.getItem().exp());
434 if (
f.isUnivariate())
442 nmod_poly_factor_t
result;
443 nmod_poly_factor_init (
result);
444 mp_limb_t leadingCoeff= nmod_poly_factor (
result, f1);
446 nmod_poly_factor_clear (
result);
463 zz_p leadcoeff = LeadCoeff(f1);
466 f1=f1 / LeadCoeff(f1);
468 vec_pair_zz_pX_long factors;
486 vec_pair_GF2X_long factors;
495 factoryError (
"univariate factorization depends on NTL(missing)");
522 ASSERT(
f.isUnivariate(),
"multivariate factorization depends on NTL(missing)" );
523 factoryError (
"multivariate factorization depends on NTL(missing)");
535 if (
f.isUnivariate() )
542 vec_pair_ZZX_long factors;
550 if ( F.
getFirst().factor().inCoeffDomain() )
561 if ( !F.
getFirst().factor().inCoeffDomain() )
568 factoryError (
"univariate factorization over Z depends on NTL(missing)");
587 factoryError (
"multivariate factorization depends on NTL(missing)");
596 if ( F.
getFirst().factor().inCoeffDomain() )
◆ factorize() [2/2]
factorization over
or
Definition at line 617 of file cf_factor.cc.
619 if (
f.inCoeffDomain() )
630 does not coincide with alpha");
633 if (
f.isUnivariate()&& (ch>0))
639 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
640 nmod_poly_t FLINTmipo, leadingCoeff;
648 fq_nmod_poly_t FLINTF;
650 fq_nmod_poly_factor_t
res;
652 fq_nmod_poly_factor (
res, leadingCoeff, FLINTF,
fq_con);
676 zz_pE leadcoeff= LeadCoeff(f1);
682 vec_pair_zz_pEX_long factors;
710 GF2E f1_coef=LeadCoeff(f1);
714 vec_pair_GF2EX_long factors;
721 factoryError (
"univariate factorization depends on NTL(missing)");
730 ASSERT(
f.isUnivariate(),
"multivariate factorization depends on NTL(missing)" );
731 factoryError (
"multivariate factorization depends on NTL(missing)");
736 else if (
f.isUnivariate() && (ch == 0))
745 ASSERT(
f.isUnivariate(),
"multivariate factorization depends on NTL(missing)" );
746 factoryError (
"multivariate factorization depends on NTL(missing)");
◆ factoryError_intern()
void factoryError_intern |
( |
const char * |
s | ) |
|
◆ factoryrandom()
int factoryrandom |
( |
int |
n | ) |
|
random integers with abs less than n
Definition at line 168 of file cf_random.cc.
◆ factoryseed()
void factoryseed |
( |
int |
s | ) |
|
◆ Farey()
Farey rational reconstruction.
If NTL is available it uses the fast algorithm from NTL, i.e. Encarnacion, Collins.
Definition at line 197 of file cf_chinese.cc.
208 SqrRoot (
bound, NTLq/2);
210 for (
i =
f;
i.hasTerms();
i++ )
219 bool lessZero= (
sign (NTLc) == -1);
221 NTL::negate (NTLc, NTLc);
223 if (ReconstructRational (NTLnum, NTLden, NTLc, NTLq,
bound,
bound))
226 NTL::negate (NTLnum, NTLnum);
◆ fdivides() [1/2]
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
fdivides() - check whether ‘f’ divides ‘g’.
Returns true iff ‘f’ divides ‘g’. Uses some extra heuristic to avoid polynomial division. Without the heuristic, the test essentialy looks like ‘divremt(g, f, q, r) && r.isZero()’.
Type info:
f, g: Current
Elements from prime power domains (or polynomials over such domains) are admissible if ‘f’ (or lc(‘f’), resp.) is not a zero divisor. This is a slightly stronger precondition than mathematically necessary since divisibility is a well-defined notion in arbitrary rings. Hence, we decided not to declare the weaker type ‘CurrentPP’.
Developers note:
One may consider the the test ‘fdivides( f.LC(), g.LC() )’ in the main ‘if’-test superfluous since ‘divremt()’ in the ‘if’-body repeats the test. However, ‘divremt()’ does not use any heuristic to do so.
It seems not reasonable to call ‘fdivides()’ from ‘divremt()’ to check divisibility of leading coefficients. ‘fdivides()’ is on a relatively high level compared to ‘divremt()’.
Definition at line 338 of file cf_algorithm.cc.
343 else if (
f.isZero() )
346 if ( (
f.inCoeffDomain() ||
g.inCoeffDomain())
351 if (
f.inCoeffDomain() )
360 int fLevel =
f.level();
361 int gLevel =
g.level();
362 if ( (gLevel > 0) && (fLevel == gLevel) )
373 else if ( gLevel < fLevel )
◆ fdivides() [2/2]
same as fdivides if true returns quotient quot of g by f otherwise quot == 0
Definition at line 388 of file cf_algorithm.cc.
394 else if (
f.isZero() )
397 if ( (
f.inCoeffDomain() ||
g.inCoeffDomain())
402 if (
f.inCoeffDomain() )
414 int fLevel =
f.level();
415 int gLevel =
g.level();
416 if ( (gLevel > 0) && (fLevel == gLevel) )
433 else if ( gLevel < fLevel )
◆ gcd()
Definition at line 257 of file cf_gcd.cc.
260 if (
b ||
g.isZero() )
267 if (
f.inPolyDomain() ||
g.inPolyDomain() )
269 if (
f.mvar() !=
g.mvar() )
271 if (
f.mvar() >
g.mvar() )
322 if (
f.inBaseDomain() &&
g.inBaseDomain() )
◆ 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 91 of file cf_gcd.cc.
94 bool fc_isUnivariate=
f.isUnivariate();
95 bool gc_isUnivariate=
g.isUnivariate();
96 bool fc_and_gc_Univariate=fc_isUnivariate && gc_isUnivariate;
120 else if (!fc_and_gc_Univariate)
◆ get_max_degree_Variable()
get_max_degree_Variable returns Variable with highest degree.
We assume f is not a constant!
Definition at line 245 of file cf_factor.cc.
247 ASSERT( ( !
f.inCoeffDomain() ),
"no constants" );
249 for (
int i=1;
i<=n;
i++ )
◆ get_Terms()
Definition at line 274 of file cf_factor.cc.
282 for (
i=
f;
i.hasTerms();
i++ ){
284 for (
j=dummy;
j.hasItem();
j++ )
◆ getCharacteristic()
int getCharacteristic |
( |
| ) |
|
◆ getDefaultExtName()
char getDefaultExtName |
( |
| ) |
|
◆ getDefaultVarName()
char getDefaultVarName |
( |
| ) |
|
◆ getGFDegree()
◆ getGFGenerator()
◆ getMipo()
◆ getNumVars()
int getNumVars ( const CanonicalForm & f )
getNumVars() - get number of polynomial variables in f.
Definition at line 314 of file cf_ops.cc.
317 if (
f.inCoeffDomain() )
319 else if ( (n =
f.level()) == 1 )
325 for (
i = n-1;
i >=0;
i-- ) vars[
i] = 0;
333 for (
i = 1;
i < n;
i++ )
334 if ( vars[
i] != 0 )
m++;
◆ getTerms()
get_Terms: Split the polynomial in the containing terms.
getTerms: the real work is done here.
Definition at line 264 of file cf_factor.cc.
◆ 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.
353 if (
f.inCoeffDomain() )
355 else if ( (n =
f.level()) == 1 )
361 for (
i = n;
i >= 0;
i-- ) vars[
i] = 0;
369 for (
i = n;
i > 0;
i-- )
◆ gf_gf2ff() [1/2]
◆ gf_gf2ff() [2/2]
◆ gf_isff() [1/2]
◆ gf_isff() [2/2]
◆ gf_value()
Definition at line 60 of file singext.cc.
63 return ((intptr_t)ff) >>2;
◆ gmp_denominator()
◆ gmp_numerator()
◆ hasFirstAlgVar()
check if poly f contains an algebraic variable a
Definition at line 665 of file cf_ops.cc.
667 if(
f.inBaseDomain() )
◆ hasMipo()
◆ head()
◆ headdegree()
◆ homogenize() [1/2]
homogenize homogenizes f with Variable x
Definition at line 298 of file cf_factor.cc.
305 for (
i=
f;
i.hasTerms();
i++)
307 elem=
i.coeff()*
power(
f.mvar(),
i.exp());
321 for (
i=Termlist;
i.hasItem();
i++)
330 for (
i=Newlist;
i.hasItem();
i++)
◆ homogenize() [2/2]
Definition at line 338 of file cf_factor.cc.
345 for (
i=
f;
i.hasTerms();
i++)
347 elem=
i.coeff()*
power(
f.mvar(),
i.exp());
361 for (
i=Termlist;
i.hasItem();
i++)
370 for (
i=Newlist;
i.hasItem();
i++)
◆ icontent()
◆ igcd()
int igcd |
( |
int |
a, |
|
|
int |
b |
|
) |
| |
◆ ilog2()
◆ ipower()
int ipower |
( |
int |
b, |
|
|
int |
m |
|
) |
| |
int ipower ( int b, int m )
ipower() - calculate b^m in standard integer arithmetic.
Note: Beware of overflows.
Definition at line 25 of file cf_util.cc.
◆ irrCharSeries()
irreducible characteristic series
Definition at line 568 of file cfCharSets.cc.
571 CFList qs, cs, factorset, is, ts, L;
579 if (sqrfFactors.
getFirst().factor().inCoeffDomain())
581 for (iter2= sqrfFactors; iter2.
hasItem(); iter2++)
582 sqrf *= iter2.
getItem().factor();
589 int nr_of_iteration= 0, indexRed, highestlevel= 0;
608 if (nr_of_iteration == 0)
610 nr_of_iteration += 1;
615 nr_of_iteration += 1;
620 if (qs.
length() - 3 < highestlevel)
626 factorset= StoredFactors.
FS1;
630 ts=
irredAS (cs, indexRed, reducible);
641 ts=
irredAS (cs, indexRed, reducible);
646 if (cs.
length() == highestlevel)
650 iss=
adjoin (is, qs, qqi);
668 if (
i.getItem() == reducible)
685 qhi=
Union (iss, qhi);
◆ is_imm()
Definition at line 206 of file factory.h.
209 return ( ((
int)((intptr_t)ptr)) & 3 );
◆ isOn()
◆ isPurePoly()
Definition at line 229 of file cf_factor.cc.
231 if (
f.level()<=0)
return false;
234 if (!(
i.coeff().inBaseDomain()))
return false;
◆ isPurePoly_m()
Definition at line 219 of file cf_factor.cc.
221 if (
f.inBaseDomain())
return true;
222 if (
f.level()<0)
return false;
◆ lc()
◆ Lc()
◆ LC() [1/2]
◆ LC() [2/2]
◆ 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 338 of file cf_gcd.cc.
340 if (
f.isZero() ||
g.isZero() )
343 return (
f /
gcd(
f,
g ) ) *
g;
◆ leftShift()
left shift the main variable of F by n
- Returns
- if x is the main variable of F the result is F(x^n)
Definition at line 683 of file cf_ops.cc.
685 ASSERT (n >= 0,
"cannot left shift by negative number");
◆ level() [1/2]
Definition at line 461 of file factory.h.
461 {
return f.level(); }
◆ level() [2/2]
◆ linearSystemSolve()
Definition at line 78 of file cf_linsys.cc.
90 if (
M(
j,
i) != 0 )
break;
91 if (
j >
nrows )
return false;
94 pivotrecip = 1 /
M(
i,
i);
99 if ( rowpivot == 0 )
continue;
101 M(
j,
k) -=
M(
i,
k) * rowpivot;
115 int rows =
M.rows(), cols =
M.columns();
123 for (
i = 0;
i < rows;
i++ ) {
124 mm[
i] =
new int[cols];
135 DEBOUT( cerr,
"trying prime(" << pno <<
") = " );
141 for (
i = 1;
i <= rows;
i++ )
142 for (
j = 1;
j <= cols;
j++ )
145 ok =
solve( mm, rows, cols );
151 for (
i = 1;
i <= rows;
i++ )
152 for (
j = rows+1;
j <= cols;
j++ )
153 MM(
i,
j) = mm[
i-1][
j-1];
160 DEBOUT( cerr,
"trying prime(" << pno <<
") = " );
165 for (
i = 1;
i <= rows;
i++ )
166 for (
j = 1;
j <= cols;
j++ )
169 ok =
solve( mm, rows, cols );
175 for (
i = 1;
i <= rows;
i++ )
176 for (
j = rows+1;
j <= cols;
j++ )
189 for (
i = 1;
i <= rows;
i++ ) {
190 for (
j = rows+1;
j <= cols;
j++ )
191 if ( MM(
i,
j) > Qhalf )
◆ make_cf() [1/2]
◆ make_cf() [2/2]
◆ make_cf_from_gf()
◆ 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.
442 if (
f.inBaseDomain() )
449 for (
i =
f;
i.hasTerms();
i++ )
◆ mapinto()
Definition at line 485 of file factory.h.
485 {
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 534 of file cf_algorithm.cc.
536 if (
f.inBaseDomain() )
542 if ( coeffMaxNorm >
result )
◆ mod()
◆ modCharSet() [1/2]
◆ modCharSet() [2/2]
modified medial set
Definition at line 284 of file cfCharSets.cc.
286 CFList QS, RS= L, CSet, tmp, contents,
initial, removedFactors;
289 bool noRemainder=
true;
301 StoredFactors2.
FS1= StoredFactors.
FS1;
306 if (CSet.length() > 0 && CSet.getFirst().level() > 0)
310 for (
i= tmp;
i.hasItem();
i++)
312 r=
Prem (
i.getItem(), CSet);
325 StoredFactors2.
FS1=
Union (StoredFactors2.
FS1, removedFactors);
334 if (removeContents && !noRemainder)
336 StoredFactors.
FS1=
Union (StoredFactors2.
FS1, contents);
337 StoredFactors.
FS2= StoredFactors2.
FS2;
340 StoredFactors= StoredFactors2;
342 QS=
Union (CSet, RS);
348 StoredFactors= StoredFactors2;
◆ mvar()
◆ name()
◆ neworder()
◆ newordercf()
◆ neworderint()
◆ num()
◆ Off()
◆ On()
◆ operator%()
◆ operator*()
◆ 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 496 of file cf_inline.cc.
◆ operator-()
◆ operator/()
◆ power() [1/2]
◆ power() [2/2]
◆ pp()
◆ Prem()
pseudo remainder of F by G with certain factors of LC (g) cancelled
Definition at line 616 of file cfCharSetsUtil.cc.
619 int degF, degG, levelF, levelG;
623 if ( (levelF= F.
level()) < (levelG=
G.level()))
627 if ( levelF == levelG )
650 while ((degG <= degF) && (!
f.isZero()))
655 t=
g*lv*
power (
v, degF - degG);
◆ probIrredTest()
given some error probIrredTest detects irreducibility or reducibility of F with confidence level 1-error
- Returns
- probIrredTest returns 1 for irreducibility, -1 for reducibility or 0 if the test is not applicable
- Parameters
-
[in] | F | some poly over Z/p |
[in] | error | 0 < error < 1 |
Definition at line 63 of file facIrredTest.cc.
74 double pn=
pow ((
double)
p, (
double) n);
75 double p1= (double) 1/
p;
82 double p2= (double) (2*
p-1)/(
p*
p);
87 p2= (double) (2*
p - 1)/(
p*
p)-p2;
98 int trials= (int)
floor (
pow (sqrtTrials, 2.0));
100 double experimentalNumZeros=
numZeros (
G, trials);
102 double pmiddle=
sqrt (p1*p2);
108 if (experimentalNumZeros < pmiddle)
◆ prune()
Definition at line 261 of file variable.cc.
267 ASSERT (n+1 >= last_var,
"wrong variable");
277 char * newvarnames =
new char [last_var+1];
278 for (
i = 0;
i < last_var;
i++ )
280 newvarnames[last_var] = 0;
284 for (
i = 0;
i < last_var;
i++ )
◆ prune1()
◆ 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.
174 ASSERT(
x.
level() > 0,
"type error: polynomial variable expected" );
175 ASSERT( !
g.isZero(),
"math error: division by zero" );
185 int fDegree =
degree( F, X );
187 if ( fDegree < 0 || fDegree < gDegree )
◆ 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.
225 ASSERT(
x.
level() > 0,
"type error: polynomial variable expected" );
226 ASSERT( !
g.isZero(),
"math error: division by zero" );
236 int fDegree =
degree( F, X );
238 if ( fDegree < 0 || fDegree < gDegree ) {
◆ 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.
133 while ( ( dv <= dr ) && ( !r.
isZero()) )
◆ reduce()
polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of f are reduced modulo M
Definition at line 646 of file cf_ops.cc.
648 if(
f.inBaseDomain() ||
f.level() <
M.level())
650 if(
f.level() ==
M.level())
652 if(
f.degree() <
M.degree())
◆ reorder() [1/3]
◆ reorder() [2/3]
◆ reorder() [3/3]
◆ replaceLc()
Definition at line 89 of file fac_util.cc.
91 if (
f.inCoeffDomain() )
◆ replacevar()
◆ 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.
175 ASSERT(
x.
level() > 0,
"cannot calculate resultant with respect to algebraic variables" );
179 if (
f.isZero() ||
g.isZero() )
189 if (
f.mvar() >
x ||
g.mvar() >
x ) {
190 if (
f.mvar() >
g.mvar() )
209 if (
m+n <= 2 ||
m == 0 || n == 0 )
219 if (
m & 1 && n & 1 )
230 extFactor = -
LC(
G, X );
232 extFactor =
LC(
G, X );
234 extFactor =
power(
LC( F, X ),
m-n-1 );
◆ resultantZ()
modular resultant algorihtm over Z
- Returns
- resultantZ returns the resultant of A and B wrt. x
- Parameters
-
[in] | A | some poly |
[in] | B | some poly |
[in] | x | some polynomial variable |
[in] | prob | if true use probabilistic algorithm |
Definition at line 560 of file cfModResultant.cc.
618 for (
int i= degBx + degAx;
i > 1;
i--)
638 while (
i >= 0 &&
mod(
l,
p ) == 0)
674 if (newQ >
bound || (prob && equalCount == 2))
◆ rootOf()
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.
181 char * newvarnames =
new char [n+2];
182 for (
i = 0;
i < n;
i++ )
184 newvarnames[n] =
name;
185 newvarnames[n+1] = 0;
191 for (
i = 0;
i < n;
i++ )
◆ setCharacteristic() [1/3]
void setCharacteristic |
( |
int |
c | ) |
|
Definition at line 23 of file cf_char.cc.
37 if (c > 536870909)
factoryError(
"characteristic is too large(max is 2^29)");
◆ setCharacteristic() [2/3]
void setCharacteristic |
( |
int |
c, |
|
|
int |
n |
|
) |
| |
◆ setCharacteristic() [3/3]
void setCharacteristic |
( |
int |
c, |
|
|
int |
n, |
|
|
char |
name |
|
) |
| |
◆ setMipo()
◆ setReduce()
◆ sign()
◆ size() [1/2]
int size ( const CanonicalForm & f )
size() - return number of monomials in f which are in an coefficient domain.
Returns one if f is in an coefficient domain.
Definition at line 628 of file cf_ops.cc.
630 if (
f.inCoeffDomain() )
636 for (
i =
f;
i.hasTerms();
i++ )
◆ size() [2/2]
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.
602 if (
f.inBaseDomain() )
613 for (
i =
f;
i.hasTerms();
i++ )
◆ sqrFree()
◆ sqrt()
◆ subResChain()
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.
44 ASSERT(
x.
level() > 0,
"cannot calculate subresultant sequence with respect to algebraic variables" );
51 if (
f.isZero() ||
g.isZero() ) {
57 if (
f.mvar() >
x ||
g.mvar() >
x ) {
58 if (
f.mvar() >
g.mvar() )
78 int j = (
m <= n) ? n :
m-1;
86 if (
m == n &&
j > 0 ) {
87 S[
j-1] =
LC( S[
j], X ) *
psr( S[
j+1], S[
j], X );
90 S[
j-1] =
LC( S[
j], X ) *
LC( S[
j], X ) * S[
j+1];
92 }
else if (
m > n &&
j > 0 ) {
98 if (
j > r && r >= 0 )
114 if (
j > r && r >= 0 )
119 S[r-1] =
psr( S[
j+1], S[
j], X ) /
power( -
R,
j - r + 2 );
125 for (
j = 0;
j <= S.max();
j++ ) {
◆ 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.
170 ASSERT( x1.
level() > 0 && x2.
level() > 0,
"cannot swap algebraic Variables" );
171 if (
f.inCoeffDomain() || x1 == x2 || ( x1 >
f.mvar() && x2 >
f.mvar() ) )
◆ tailcoeff() [1/2]
Definition at line 455 of file factory.h.
455 {
return f.tailcoeff(); }
◆ tailcoeff() [2/2]
Definition at line 458 of file factory.h.
458 {
return f.tailcoeff(
v); }
◆ taildegree()
Definition at line 452 of file factory.h.
452 {
return f.taildegree(); }
◆ totaldegree() [1/2]
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.
527 else if (
f.inCoeffDomain() )
535 for (
i =
f;
i.hasTerms();
i++ )
◆ totaldegree() [2/2]
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.
560 else if (
f.inCoeffDomain() )
562 else if (
f.mvar() < v1 )
564 else if (
f.mvar() == v1 )
566 else if (
f.mvar() > v2 )
572 for (
i =
f;
i.hasTerms();
i++ )
573 if ( (dummy =
totaldegree(
i.coeff(), v1, v2 )) > cdeg )
584 for (
i =
f;
i.hasTerms();
i++ )
585 if ( (dummy =
totaldegree(
i.coeff(), v1, v2 ) +
i.exp()) > cdeg )
◆ tryFdivides()
same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f
Definition at line 454 of file cf_algorithm.cc.
460 else if (
f.isZero() )
463 if (
f.inCoeffDomain() ||
g.inCoeffDomain())
466 if (
f.inCoeffDomain() )
480 int fLevel =
f.level();
481 int gLevel =
g.level();
482 if ( (gLevel > 0) && (fLevel == gLevel) )
486 bool dividestail=
tryFdivides (
f.tailcoeff(),
g.tailcoeff(),
M, fail);
488 if (fail || !dividestail)
491 if (fail || !dividesLC)
495 if (fail || !divides)
499 else if ( gLevel < fLevel )
511 if (fail || !divides)
◆ 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 225 of file cf_gcd.cc.
227 ASSERT(
x.
level() > 0,
"cannot calculate vcontent with respect to algebraic variable" );
234 for (
i =
f;
i.hasTerms() && ! d.
isOne();
i++ )
◆ factoryConfiguration
const char factoryConfiguration[] |
|
extern |
◆ factoryError
void(* factoryError) (const char *s) |
|
extern |
◆ singular_homog_flag
◆ SW_RATIONAL
const int SW_RATIONAL = 0 |
|
static |
set to 1 for computations over Q
Definition at line 92 of file factory.h.
◆ SW_SYMMETRIC_FF
const int SW_SYMMETRIC_FF = 1 |
|
static |
set to 1 for symmetric representation over F_q
Definition at line 94 of file factory.h.
◆ SW_USE_CHINREM_GCD
const int SW_USE_CHINREM_GCD =5 |
|
static |
set to 1 to use modular gcd over Z
Definition at line 102 of file factory.h.
◆ SW_USE_EZGCD
const int SW_USE_EZGCD = 2 |
|
static |
set to 1 to use EZGCD over Z
Definition at line 96 of file factory.h.
◆ SW_USE_EZGCD_P
const int SW_USE_EZGCD_P = 3 |
|
static |
set to 1 to use EZGCD over F_q
Definition at line 98 of file factory.h.
◆ SW_USE_FF_MOD_GCD
const int SW_USE_FF_MOD_GCD =7 |
|
static |
set to 1 to use modular GCD over F_q
Definition at line 106 of file factory.h.
◆ SW_USE_NTL_SORT
const int SW_USE_NTL_SORT =4 |
|
static |
set to 1 to sort factors in a factorization
Definition at line 100 of file factory.h.
◆ SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
Definition at line 104 of file factory.h.
bool hasMipo(const Variable &alpha)
static CanonicalForm symmetricRemainder(const CanonicalForm &f, const CanonicalForm &q)
void error(const char *fmt,...)
CanonicalForm convertZZ2CF(const ZZ &a)
NAME: convertZZ2CF.
CanonicalForm convertnmod_poly_t2FacCF(const nmod_poly_t poly, const Variable &x)
conversion of a FLINT poly over Z/p to CanonicalForm
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
CFList FS2
candidate factors that might get removed
static const int SW_RATIONAL
set to 1 for computations over Q
int cmpCF(const CFFactor &f, const CFFactor &g)
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
bool isZero(const CFArray &A)
checks if entries of A are zero
CanonicalForm lcm(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm lcm ( const CanonicalForm & f, const CanonicalForm & g )
CFFList convertNTLvec_pair_ZZX_long2FacCFFList(const vec_pair_ZZX_long &e, const ZZ &multi, const Variable &x)
NAME: convertNTLvec_pair_ZZX_long2FacCFFList.
CanonicalForm psr(const CanonicalForm &rr, const CanonicalForm &vv, const Variable &x)
CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
ListCFList contract(const ListCFList &cs)
static CanonicalForm * retvalue
bool isPurePoly(const CanonicalForm &f)
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
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
class to iterate through CanonicalForm's
void Off(int s)
switch 's' off
#define DEBOUTLN(stream, objects)
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
const CanonicalForm int const CFList const Variable & y
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p multi, const Variable &x)
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
int gf_power(int a, int n)
CFFList factorize(const CanonicalForm &f, bool issqrfree)
factorization over or
bool isInseparable(const CFList &Astar)
CanonicalForm subResGCD_0(const CanonicalForm &f, const CanonicalForm &g)
subresultant GCD over Z.
static int theCharacteristic
nmod_poly_clear(FLINTmipo)
class to store factors that get removed during char set computation
static void swapvar_rec(const CanonicalForm &f, CanonicalForm &result, const CanonicalForm &term)
swapvar_between() - swap occurences of sv_x1 and sv_x2 in f.
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
CFList basicSet(const CFList &PS)
basic set in the sense of Wang a.k.a. minimal ascending set in the sense of Greuel/Pfister
static CanonicalForm icontent(const CanonicalForm &f, const CanonicalForm &c)
static CanonicalForm icontent ( const CanonicalForm & f, const CanonicalForm & c )
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
static CFList irredAS(CFList &AS, int &indexRed, CanonicalForm &reducible)
CanonicalForm homogenize(const CanonicalForm &f, const Variable &x)
homogenize homogenizes f with Variable x
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
CFList FpSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over
Varlist varsInAs(const Varlist &uord, const CFList &Astar)
static CanonicalForm ezgcd(const CanonicalForm &FF, const CanonicalForm &GG, REvaluation &b, bool internal)
real implementation of EZGCD over Z
CFList swapvar(const CFList &PS, const Variable &x, const Variable &y)
swapvar a whole list of CanonicalForms
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
static CanonicalForm internalBCommonDen(const CanonicalForm &f)
static CanonicalForm internalBCommonDen ( const CanonicalForm & f )
Varlist neworder(const CFList &PolyList)
CFList modCharSet(const CFList &L, StoreFactors &StoredFactors, bool removeContents)
modified medial set
CFList factorsOfInitials(const CFList &L)
static CanonicalForm chin_mul_inv(CanonicalForm a, CanonicalForm b, int ind, CFArray &inv)
Variable get_max_degree_Variable(const CanonicalForm &f)
get_max_degree_Variable returns Variable with highest degree.
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
gmp_float sqrt(const gmp_float &a)
const signed long floor(const ampf< Precision > &x)
const CanonicalForm CFMap CFMap & N
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
virtual class for internal CanonicalForm's
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
static CanonicalForm oneNorm(const CanonicalForm &F)
poly initial(const poly p, const ring r, const gfan::ZVector &w)
Returns the initial form of p with respect to w.
bool isPurePoly(const CanonicalForm &f)
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
int cf_getBigPrime(int i)
CanonicalForm QGCD(const CanonicalForm &F, const CanonicalForm &G)
gcd over Q(a)
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm Premb(const CanonicalForm &f, const CFList &L)
pseudo remainder of f by L with faster test for remainder being zero
CFFList sqrFreeZ(const CanonicalForm &a)
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.
unsigned short * gf_table
CanonicalForm gcd_poly(const CanonicalForm &f, const CanonicalForm &g)
CanonicalForm gcd_poly ( const CanonicalForm & f, const CanonicalForm & g )
static mpz_ptr MPQNUM(const InternalCF *const c)
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
bool isSubset(const CFList &PS, const CFList &Cset)
is PS a subset of Cset ?
void sortCFListByLevel(CFList &list)
sort in descending order of level of elements
static void fillVarsRec(const CanonicalForm &f, int *vars)
static void fillVarsRec ( const CanonicalForm & f, int * vars )
static const int SW_USE_EZGCD
set to 1 to use EZGCD over Z
InternalCF * copyObject()
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
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
#define GaloisFieldDomain
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
convertFacCF2nmod_poly_t(FLINTmipo, M)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
static void optvalues(const int *df, const int *dg, const int n, int &p1, int &pe)
virtual int levelcoeff() const
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
CFList ratSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree multivariate polynomial over
#define ASSERT(expression, message)
fq_nmod_ctx_clear(fq_con)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
Rational abs(const Rational &a)
CFArray subResChain(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
int status int void * buf
void select(const ListCFList &ppi, int length, ListCFList &ppi1, ListCFList &ppi2)
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
CanonicalForm cd(bCommonDen(FF))
CFAFList absFactorizeMain(const CanonicalForm &G)
main absolute factorization routine, expects poly which is irreducible over Q
CFList reorder(const Varlist &betterorder, const CFList &PS)
TIMING_START(fac_alg_resultant)
int sign(const CanonicalForm &a)
CFFList AlgExtFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a univariate polynomial over algebraic extension of Q
static CanonicalForm trivialResultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
static CanonicalForm trivialResultant ( const CanonicalForm & f, const CanonicalForm & g,...
bool betterpivot(const CanonicalForm &oldpivot, const CanonicalForm &newpivot)
factory's class for polynomials
static InternalCF * basic(long value)
nmod_poly_init(FLINTmipo, getCharacteristic())
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,...
static void degreesRec(const CanonicalForm &f, int *degs)
static void degreesRec ( const CanonicalForm & f, int * degs )
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
CanonicalForm detbound(const CFMatrix &M, int rows)
static int max(int a, int b)
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....
CFList FS1
factors that were removed
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &multi, const Variable &x, const Variable &alpha)
#define DEBINCLEVEL(stream, msg)
void prune(Variable &alpha)
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...
void removeFactors(CanonicalForm &r, StoreFactors &StoredFactors, CFList &removedFactors)
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,...
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].
#define DEBDECLEVEL(stream, msg)
mat_ZZ * convertFacCFMatrix2NTLmat_ZZ(const CFMatrix &m)
static const int SW_USE_CHINREM_GCD
set to 1 to use modular gcd over Z
CanonicalForm determinant(const CFMatrix &M, int n)
ListCFList adjoin(const CFList &is, const CFList &qs, const ListCFList &qh)
#define FiniteFieldDomain
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
CFList get_Terms(const CanonicalForm &f)
static const int SW_USE_FF_MOD_GCD
set to 1 to use modular GCD over F_q
void gf_setcharacteristic(int p, int n, char name)
static InternalCF * rational(long num, long den)
CFFList sortCFFList(CFFList &F)
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
static char * var_names_ext
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
CanonicalForm content(const CanonicalForm &f)
CanonicalForm content ( const CanonicalForm & f )
double inverseERF(double d)
void sort(CFArray &A, int l=0)
quick sort A
CanonicalForm head(const CanonicalForm &f)
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
static void settype(int type)
CanonicalForm subResGCD_p(const CanonicalForm &f, const CanonicalForm &g)
subresultant GCD over finite fields. In case things become too dense we switch to a modular algorithm
static CanonicalForm conv2mipo(const CanonicalForm &mipo, const Variable &alpha)
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
gmp_float exp(const gmp_float &a)
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
void sortListCFList(ListCFList &list)
sort in descending order of length of elements
void convertFacCF2Fmpq_poly_t(fmpq_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomials over Q to fmpq_poly_t
CanonicalForm modGCDFp(const CanonicalForm &F, const CanonicalForm &G, CanonicalForm &coF, CanonicalForm &coG, bool &topLevel, CFList &l)
CFFList SteelTrager(const CanonicalForm &f, const CFList &AS)
algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate...
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
void(* factoryError)(const char *s)
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
CFMatrix * convertNTLmat_ZZ2FacCFMatrix(const mat_ZZ &m)
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
CFList uniGcd(const CFList &L)
void setCharacteristic(int c)
static mpz_ptr MPI(const InternalCF *const c)
MPI() - return underlying mpz_t of ācā.
TIMING_END_AND_PRINT(fac_alg_resultant, "time to compute resultant0: ")
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
factory's class for variables
CanonicalForm convertFmpq_poly_t2FacCF(const fmpq_poly_t p, const Variable &x)
conversion of a FLINT poly over Q to CanonicalForm
static const int SW_USE_EZGCD_P
set to 1 to use EZGCD over F_q
static CanonicalForm bound(const CFMatrix &M)
int cf_getSmallPrime(int i)
ListCFList adjoinb(const CFList &is, const CFList &qs, const ListCFList &qh, const CFList &cs)
CFSwitches cf_glob_switches
CFSwitches cf_glob_switches;.
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
CanonicalForm Farey(const CanonicalForm &f, const CanonicalForm &q)
Farey rational reconstruction.
bool matrix_in_Z(const CFMatrix &M, int rows)
char name(const Variable &v)
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents)
characteristic set via modified medial set
CanonicalForm gcd(const CanonicalForm &f, const CanonicalForm &g)
bool solve(int **extmat, int nrows, int ncols)
int getDegOfExt(IntList °reelist, int n)
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...
static CanonicalForm cf_content(const CanonicalForm &f, const CanonicalForm &g)
static CanonicalForm cf_content ( const CanonicalForm & f, const CanonicalForm & g )
Rational pow(const Rational &a, int e)
CFList charSetN(const CFList &PS)
medial set
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
CFList GFSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over GF
CanonicalForm lowestRank(const CFList &L)
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
int determinant(int **extmat, int n)
#define DEBOUTENDL(stream)
static ext_entry * algextensions
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
const CanonicalForm CFMap CFMap const Variable & x
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
const Variable & v
< [in] a sqrfree bivariate poly
CanonicalForm resultantFp(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Fp
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 & ...
const CanonicalForm int s
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
#define DEBOUT(stream, objects)
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
int status int void size_t count
InternalCF * int2imm_gf(long i)
int cf_getNumSmallPrimes()
static const int SW_USE_QGCD
set to 1 to use Encarnacion GCD over Q(a)
static int * multiplicity
CanonicalForm modGCDZ(const CanonicalForm &FF, const CanonicalForm &GG)
modular GCD over Z
fq_nmod_poly_clear(prod, fq_con)
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
bool getReduce(const Variable &alpha)
CFList factorPSet(const CFList &PS)
static char default_name_ext
void On(int s)
switch 's' on
CanonicalForm mapdomain(const CanonicalForm &f, CanonicalForm(*mf)(const CanonicalForm &))
CanonicalForm mapdomain ( const CanonicalForm & f, CanonicalForm (*mf)( const CanonicalForm & ) )
bool isPurePoly_m(const CanonicalForm &f)
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
void removeContent(CanonicalForm &F, CanonicalForm &cF)
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &multi, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
int size(const CanonicalForm &f, const Variable &v)
int size ( const CanonicalForm & f, const Variable & v )
CanonicalForm reduce(const CanonicalForm &f, const CanonicalForm &M)
polynomials in M.mvar() are considered coefficients M univariate monic polynomial the coefficients of...
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
static mpz_ptr MPQDEN(const InternalCF *const c)
CanonicalForm convertNTLzzpX2CF(const zz_pX &poly, const Variable &x)
void sort(int(*)(const T &, const T &))
static bool fill_int_mat(const CFMatrix &M, int **m, int rows)
void inplaceUnion(const ListCFList &a, ListCFList &b)
Union of a and b stored in b.
bool isOn(int s) const
check if 's' is on
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...
static CanonicalForm replacevar_between(const CanonicalForm &f)
replacevar_between() - replace occurences of sv_x1 in f with sv_x2.
CanonicalForm generateMipo(int degOfExt)
void ff_setprime(const int p)
static Variable sv_x1
static Variable sv_x1, sv_x2;