 |
My Project
debian-1:4.1.1-p2+ds-4build3
|
Go to the source code of this file.
|
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...
|
|
declarations of higher level algorithms.
Header file corresponds to: cf_algorithm.cc, cf_chinese.cc, cf_factor.cc, cf_linsys.cc, cf_resultant.cc
Hierarchy: mathematical algorithms on canonical forms
Developers note:
This header file collects declarations of most of the functions in Factory which implement higher level algorithms on canonical forms (factorization, gcd, etc.) and declarations of some low level mathematical functions, too (absolute value, euclidean norm, etc.).
Definition in file cf_algorithm.h.
◆ 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 116 of file cf_algorithm.h.
◆ 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.
◆ 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()
◆ 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;
◆ 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" );
◆ 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)");
◆ 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 )
◆ 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++ )
◆ 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.
◆ 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++)
◆ 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;
◆ 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 )
◆ 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 )
◆ 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()) )
◆ 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 );
◆ sqrFree()
◆ 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++ ) {
◆ 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)
◆ singular_homog_flag
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
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
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 )
bool isPurePoly(const CanonicalForm &f)
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
class to iterate through CanonicalForm's
#define DEBOUTLN(stream, objects)
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p multi, const Variable &x)
CFFList factorize(const CanonicalForm &f, bool issqrfree)
factorization over or
nmod_poly_clear(FLINTmipo)
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
CanonicalForm homogenize(const CanonicalForm &f, const Variable &x)
homogenize homogenizes f with Variable x
CFList FpSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over
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 )
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.
gmp_float sqrt(const gmp_float &a)
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
int cf_getBigPrime(int i)
CFFList sqrFreeZ(const CanonicalForm &a)
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
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)
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)
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
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))
TIMING_START(fac_alg_resultant)
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)
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,...
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)
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 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)
CFList get_Terms(const CanonicalForm &f)
CFFList sortCFFList(CFFList &F)
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
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 sort(CFArray &A, int l=0)
quick sort A
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
void(* factoryError)(const char *s)
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
factory's class for variables
static CanonicalForm bound(const CFMatrix &M)
CanonicalForm Farey(const CanonicalForm &f, const CanonicalForm &q)
Farey rational reconstruction.
bool matrix_in_Z(const CFMatrix &M, int rows)
bool solve(int **extmat, int nrows, int ncols)
CFList GFSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over GF
int determinant(int **extmat, int n)
#define DEBOUTENDL(stream)
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
const Variable & v
< [in] a sqrfree bivariate poly
const CanonicalForm int s
#define DEBOUT(stream, objects)
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
fq_nmod_poly_clear(prod, fq_con)
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
bool getReduce(const Variable &alpha)
bool isPurePoly_m(const CanonicalForm &f)
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
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.
void sort(int(*)(const T &, const T &))
static bool fill_int_mat(const CFMatrix &M, int **m, int rows)