Functions | Variables
cf_algorithm.h File Reference

declarations of higher level algorithms. More...

#include "canonicalform.h"
#include "variable.h"

Go to the source code of this file.

Functions

CanonicalForm psr (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
 
CanonicalForm psq (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CanonicalForm psq ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
 
void psqr (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, const Variable &x)
 void psqr ( const CanonicalForm & f, const CanonicalForm & g, CanonicalForm & q, CanonicalForm & r, const Variable & x ) More...
 
CanonicalForm bCommonDen (const CanonicalForm &f)
 CanonicalForm bCommonDen ( const CanonicalForm & f ) More...
 
bool fdivides (const CanonicalForm &f, const CanonicalForm &g)
 bool fdivides ( const CanonicalForm & f, const CanonicalForm & g ) More...
 
bool fdivides (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &quot)
 same as fdivides if true returns quotient quot of g by f otherwise quot == 0 More...
 
bool tryFdivides (const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &M, bool &fail)
 same as fdivides but handles zero divisors in Z_p[t]/(f)[x1,...,xn] for reducible f More...
 
CanonicalForm maxNorm (const CanonicalForm &f)
 CanonicalForm maxNorm ( const CanonicalForm & f ) More...
 
CanonicalForm euclideanNorm (const CanonicalForm &f)
 CanonicalForm euclideanNorm ( const CanonicalForm & f ) More...
 
void chineseRemainder (const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
 void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew ) More...
 
void chineseRemainder (const CFArray &x, const CFArray &q, CanonicalForm &xnew, CanonicalForm &qnew)
 void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew ) More...
 
void chineseRemainderCached (CFArray &a, CFArray &n, CanonicalForm &xnew, CanonicalForm &prod, CFArray &inv)
 
CanonicalForm Farey (const CanonicalForm &f, const CanonicalForm &q)
 Farey rational reconstruction. More...
 
bool isPurePoly (const CanonicalForm &f)
 
bool isPurePoly_m (const CanonicalForm &f)
 
CFFList factorize (const CanonicalForm &f, bool issqrfree=false)
 factorization over $ F_p $ or $ Q $ More...
 
CFFList factorize (const CanonicalForm &f, const Variable &alpha)
 factorization over $ F_p(\alpha) $ or $ Q(\alpha) $ More...
 
CFFList sqrFree (const CanonicalForm &f, bool sort=false)
 squarefree factorization More...
 
CanonicalForm homogenize (const CanonicalForm &f, const Variable &x)
 homogenize homogenizes f with Variable x More...
 
CanonicalForm homogenize (const CanonicalForm &f, const Variable &x, const Variable &v1, const Variable &v2)
 
Variable get_max_degree_Variable (const CanonicalForm &f)
 get_max_degree_Variable returns Variable with highest degree. More...
 
CFList get_Terms (const CanonicalForm &f)
 
void getTerms (const CanonicalForm &f, const CanonicalForm &t, CFList &result)
 get_Terms: Split the polynomial in the containing terms. More...
 
bool linearSystemSolve (CFMatrix &M)
 
CanonicalForm determinant (const CFMatrix &M, int n)
 
CFArray subResChain (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
 
CanonicalForm resultant (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
 
CanonicalForm abs (const CanonicalForm &f)
 inline CanonicalForm abs ( const CanonicalForm & f ) More...
 

Variables

int singular_homog_flag
 

Detailed Description

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.

Function Documentation

§ abs()

CanonicalForm abs ( const CanonicalForm f)
inline

inline CanonicalForm abs ( const CanonicalForm & f )

abs() - return absolute value of `f'.

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

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

Type info:

f: CurrentPP

Definition at line 116 of file cf_algorithm.h.

117 {
118  // it is not only more general to use `sign()' instead of a
119  // direct comparison `f < 0', it is faster, too
120  if ( sign( f ) < 0 )
121  return -f;
122  else
123  return f;
124 }
FILE * f
Definition: checklibs.c:7
static int sign(int x)
Definition: ring.cc:3412

§ bCommonDen()

CanonicalForm bCommonDen ( const CanonicalForm f)

CanonicalForm bCommonDen ( const CanonicalForm & f )

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

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

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

Type info:

f: CurrentPP

Definition at line 293 of file cf_algorithm.cc.

294 {
295  if ( getCharacteristic() == 0 && isOn( SW_RATIONAL ) ) {
296  // otherwise `bgcd()' returns one
297  Off( SW_RATIONAL );
299  On( SW_RATIONAL );
300  return result;
301  } else
302  return CanonicalForm( 1 );
303 }
void Off(int sw)
switches
factory&#39;s main class
Definition: canonicalform.h:75
int getCharacteristic()
Definition: cf_char.cc:51
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
static CanonicalForm internalBCommonDen(const CanonicalForm &f)
static CanonicalForm internalBCommonDen ( const CanonicalForm & f )
return result
Definition: facAbsBiFact.cc:76

§ chineseRemainder() [1/2]

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

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

chineseRemainder - integer chinese remaindering.

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

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

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

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

Definition at line 52 of file cf_chinese.cc.

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

§ chineseRemainder() [2/2]

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

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

chineseRemainder - integer chinese remaindering.

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

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

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

Definition at line 119 of file cf_chinese.cc.

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

§ chineseRemainderCached()

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

Definition at line 264 of file cf_chinese.cc.

265 {
266  CanonicalForm p, sum = 0; prod=1;
267  int i;
268  int len=n.size();
269 
270  for (i = 0; i < len; i++) prod *= n[i];
271 
272  for (i = 0; i < len; i++)
273  {
274  p = prod / n[i];
275  sum += a[i] * chin_mul_inv(p, n[i], i, inv) * p;
276  }
277 
278  xnew = mod(sum , prod);
279 }
CF_NO_INLINE CanonicalForm mod(const CanonicalForm &, const CanonicalForm &)
Definition: cf_inline.cc:564
return P p
Definition: myNF.cc:203
factory&#39;s main class
Definition: canonicalform.h:75
int size() const
Definition: ftmpl_array.cc:92
int i
Definition: cfEzgcd.cc:123
static CanonicalForm chin_mul_inv(CanonicalForm a, CanonicalForm b, int ind, CFArray &inv)
Definition: cf_chinese.cc:251

§ determinant()

CanonicalForm determinant ( const CFMatrix M,
int  n 
)

Definition at line 222 of file cf_linsys.cc.

223 {
224  typedef int* int_ptr;
225 
226  ASSERT( rows <= M.rows() && rows <= M.columns() && rows > 0, "undefined determinant" );
227  if ( rows == 1 )
228  return M(1,1);
229  else if ( rows == 2 )
230  return M(1,1)*M(2,2)-M(2,1)*M(1,2);
231  else if ( matrix_in_Z( M, rows ) )
232  {
233  int ** mm = new int_ptr[rows];
234  CanonicalForm x, q, Qhalf, B;
235  int n, i, intdet, p, pno;
236  for ( i = 0; i < rows; i++ )
237  {
238  mm[i] = new int[rows];
239  }
240  pno = 0; n = 0;
241  TIMING_START(det_bound);
242  B = detbound( M, rows );
243  TIMING_END(det_bound);
244  q = 1;
245  TIMING_START(det_numprimes);
246  while ( B > q && n < cf_getNumBigPrimes() )
247  {
248  q *= cf_getBigPrime( n );
249  n++;
250  }
251  TIMING_END(det_numprimes);
252 
253  CFArray X(1,n), Q(1,n);
254 
255  while ( pno < n )
256  {
257  p = cf_getBigPrime( pno );
258  setCharacteristic( p );
259  // map matrix into char p
260  TIMING_START(det_mapping);
261  fill_int_mat( M, mm, rows );
262  TIMING_END(det_mapping);
263  pno++;
264  DEBOUT( cerr, "." );
265  TIMING_START(det_determinant);
266  intdet = determinant( mm, rows );
267  TIMING_END(det_determinant);
268  setCharacteristic( 0 );
269  X[pno] = intdet;
270  Q[pno] = p;
271  }
272  TIMING_START(det_chinese);
273  chineseRemainder( X, Q, x, q );
274  TIMING_END(det_chinese);
275  Qhalf = q / 2;
276  if ( x > Qhalf )
277  x = x - q;
278  for ( i = 0; i < rows; i++ )
279  delete [] mm[i];
280  delete [] mm;
281  return x;
282  }
283  else
284  {
285  CFMatrix m( M );
286  CanonicalForm divisor = 1, pivot, mji;
287  int i, j, k, sign = 1;
288  for ( i = 1; i <= rows; i++ ) {
289  pivot = m(i,i); k = i;
290  for ( j = i+1; j <= rows; j++ ) {
291  if ( betterpivot( pivot, m(j,i) ) ) {
292  pivot = m(j,i);
293  k = j;
294  }
295  }
296  if ( pivot.isZero() )
297  return 0;
298  if ( i != k )
299  {
300  m.swapRow( i, k );
301  sign = -sign;
302  }
303  for ( j = i+1; j <= rows; j++ )
304  {
305  if ( ! m(j,i).isZero() )
306  {
307  divisor *= pivot;
308  mji = m(j,i);
309  m(j,i) = 0;
310  for ( k = i+1; k <= rows; k++ )
311  m(j,k) = m(j,k) * pivot - m(i,k)*mji;
312  }
313  }
314  }
315  pivot = sign;
316  for ( i = 1; i <= rows; i++ )
317  pivot *= m(i,i);
318  return pivot / divisor;
319  }
320 }
int cf_getNumBigPrimes()
Definition: cf_primes.cc:45
CanonicalForm detbound(const CFMatrix &M, int rows)
Definition: cf_linsys.cc:486
bool betterpivot(const CanonicalForm &oldpivot, const CanonicalForm &newpivot)
Definition: cf_linsys.cc:61
return P p
Definition: myNF.cc:203
#define DEBOUT(stream, objects)
Definition: debug.h:47
factory&#39;s main class
Definition: canonicalform.h:75
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].
int k
Definition: cfEzgcd.cc:93
#define Q
Definition: sirandom.c:25
int determinant(int **extmat, int n)
Definition: cf_linsys.cc:556
void setCharacteristic(int c)
Definition: cf_char.cc:23
#define M
Definition: sirandom.c:24
#define TIMING_END(t)
Definition: timing.h:88
int j
Definition: myNF.cc:70
static bool fill_int_mat(const CFMatrix &M, int **m, int rows)
Definition: cf_linsys.cc:203
int rows() const
Definition: ftmpl_matrix.h:45
int columns() const
Definition: ftmpl_matrix.h:46
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
void chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2...
Definition: cf_chinese.cc:52
b *CanonicalForm B
Definition: facBivar.cc:51
#define TIMING_START(t)
Definition: timing.h:87
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
Variable x
Definition: cfModGcd.cc:4023
bool isZero(const CFArray &A)
checks if entries of A are zero
#define ASSERT(expression, message)
Definition: cf_assert.h:99
bool matrix_in_Z(const CFMatrix &M, int rows)
Definition: cf_linsys.cc:39
int * int_ptr
Definition: structs.h:57
static int sign(int x)
Definition: ring.cc:3412

§ euclideanNorm()

CanonicalForm euclideanNorm ( const CanonicalForm f)

CanonicalForm euclideanNorm ( const CanonicalForm & f )

euclideanNorm() - return Euclidean norm of `f'.

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

Type info:

f: UVPoly( Z )

Definition at line 563 of file cf_algorithm.cc.

564 {
565  ASSERT( (f.inBaseDomain() || f.isUnivariate()) && f.LC().inZ(),
566  "type error: univariate poly over Z expected" );
567 
568  CanonicalForm result = 0;
569  for ( CFIterator i = f; i.hasTerms(); i++ ) {
570  CanonicalForm coeff = i.coeff();
571  result += coeff*coeff;
572  }
573  return sqrt( result );
574 }
factory&#39;s main class
Definition: canonicalform.h:75
bool inBaseDomain() const
bool isUnivariate() const
gmp_float sqrt(const gmp_float &a)
Definition: mpr_complex.cc:329
int i
Definition: cfEzgcd.cc:123
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
bool inZ() const
predicates
#define ASSERT(expression, message)
Definition: cf_assert.h:99
return result
Definition: facAbsBiFact.cc:76
CanonicalForm LC() const

§ factorize() [1/2]

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

factorization over $ F_p $ or $ Q $

Definition at line 390 of file cf_factor.cc.

391 {
392  if ( f.inCoeffDomain() )
393  return CFFList( f );
394 #ifndef NOASSERT
395  Variable a;
396  ASSERT (!hasFirstAlgVar (f, a), "f has an algebraic variable use factorize \
397  ( const CanonicalForm & f, const Variable & alpha ) instead");
398 #endif
399  //out_cf("factorize:",f,"==================================\n");
400  if (! f.isUnivariate() )
401  {
403  {
405  int d_xn = degree(f,xn);
406  CFMap n;
407  CanonicalForm F = compress(f(1,xn),n);
408  CFFList Intermediatelist;
409  Intermediatelist = factorize(F);
410  CFFList Homoglist;
412  for ( j=Intermediatelist; j.hasItem(); j++ )
413  {
414  Homoglist.append(
415  CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
416  }
417  CFFList Unhomoglist;
418  CanonicalForm unhomogelem;
419  for ( j=Homoglist; j.hasItem(); j++ )
420  {
421  unhomogelem= homogenize(j.getItem().factor(),xn);
422  Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
423  d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
424  }
425  if ( d_xn != 0 ) // have to append xn^(d_xn)
426  Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
427  if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF);
428  return Unhomoglist;
429  }
430  }
431  CFFList F;
432  if ( getCharacteristic() > 0 )
433  {
434  if (f.isUnivariate())
435  {
436 #ifdef HAVE_NTL
437 #ifdef HAVE_FLINT
438  if (degree (f) < 300)
439  {
440  nmod_poly_t f1;
441  convertFacCF2nmod_poly_t (f1, f);
442  nmod_poly_factor_t result;
443  nmod_poly_factor_init (result);
444  mp_limb_t leadingCoeff= nmod_poly_factor (result, f1);
445  F= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, f.mvar());
446  nmod_poly_factor_clear (result);
447  nmod_poly_clear (f1);
448  }
449  else
450 #endif
451  {
452  // USE NTL
453  if (getCharacteristic()!=2)
454  {
456  {
458  zz_p::init(getCharacteristic());
459  }
460 
461  // convert to NTL
462  zz_pX f1=convertFacCF2NTLzzpX(f);
463  zz_p leadcoeff = LeadCoeff(f1);
464 
465  //make monic
466  f1=f1 / LeadCoeff(f1);
467  // factorize
468  vec_pair_zz_pX_long factors;
469  CanZass(factors,f1);
470 
471  F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
472  //test_cff(F,f);
473  }
474  else /*getCharacteristic()==2*/
475  {
476  // Specialcase characteristic==2
477  if (fac_NTL_char != 2)
478  {
479  fac_NTL_char = 2;
480  zz_p::init(2);
481  }
482  // convert to NTL using the faster conversion routine for characteristic 2
483  GF2X f1=convertFacCF2NTLGF2X(f);
484  // no make monic necessary in GF2
485  //factorize
486  vec_pair_GF2X_long factors;
487  CanZass(factors,f1);
488 
489  // convert back to factory again using the faster conversion routine for vectors over GF2X
490  F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
491  }
492  }
493 #else
494  // Use Factory without NTL
495  factoryError ("univariate factorization depends on NTL(missing)");
496  return CFFList (CFFactor (f, 1));
497 #endif //HAVE_NTL
498  }
499  else
500  {
501  #ifdef HAVE_NTL
502  if (issqrfree)
503  {
504  CFList factors;
505  Variable alpha;
507  factors= GFSqrfFactorize (f);
508  else
509  factors= FpSqrfFactorize (f);
510  for (CFListIterator i= factors; i.hasItem(); i++)
511  F.append (CFFactor (i.getItem(), 1));
512  }
513  else
514  {
515  Variable alpha;
517  F= GFFactorize (f);
518  else
519  F= FpFactorize (f);
520  }
521  #else
522  ASSERT( f.isUnivariate(), "multivariate factorization depends on NTL(missing)" );
523  factoryError ("multivariate factorization depends on NTL(missing)");
524  return CFFList (CFFactor (f, 1));
525  #endif
526  }
527  }
528  else
529  {
530  bool on_rational = isOn(SW_RATIONAL);
531  On(SW_RATIONAL);
532  CanonicalForm cd = bCommonDen( f );
533  CanonicalForm fz = f * cd;
534  Off(SW_RATIONAL);
535  if ( f.isUnivariate() )
536  {
537  #ifdef HAVE_NTL
538  //USE NTL
539  CanonicalForm ic=icontent(fz);
540  fz/=ic;
541  ZZ c;
542  vec_pair_ZZX_long factors;
543  //factorize the converted polynomial
544  factor(c,factors,convertFacCF2NTLZZX(fz));
545 
546  //convert the result back to Factory
548  if ( ! ic.isOne() )
549  {
550  if ( F.getFirst().factor().inCoeffDomain() )
551  {
552  CFFactor new_first( F.getFirst().factor() * ic );
553  F.removeFirst();
554  F.insert( new_first );
555  }
556  else
557  F.insert( CFFactor( ic ) );
558  }
559  else
560  {
561  if ( !F.getFirst().factor().inCoeffDomain() )
562  {
563  CFFactor new_first( 1 );
564  F.insert( new_first );
565  }
566  }
567  #else
568  factoryError ("univariate factorization over Z depends on NTL(missing)");
569  return CFFList (CFFactor (f, 1));
570  #endif
571  }
572  else
573  {
574  #ifdef HAVE_NTL
575  On (SW_RATIONAL);
576  if (issqrfree)
577  {
578  CFList factors;
579  factors= ratSqrfFactorize (fz);
580  for (CFListIterator i= factors; i.hasItem(); i++)
581  F.append (CFFactor (i.getItem(), 1));
582  }
583  else
584  F = ratFactorize (fz);
585  Off (SW_RATIONAL);
586  #else
587  factoryError ("multivariate factorization depends on NTL(missing)");
588  return CFFList (CFFactor (f, 1));
589  #endif
590  }
591 
592  if ( on_rational )
593  On(SW_RATIONAL);
594  if ( ! cd.isOne() )
595  {
596  if ( F.getFirst().factor().inCoeffDomain() )
597  {
598  CFFactor new_first( F.getFirst().factor() / cd );
599  F.removeFirst();
600  F.insert( new_first );
601  }
602  else
603  {
604  F.insert( CFFactor( 1/cd ) );
605  }
606  }
607  }
608 
609  //out_cff(F);
610  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
611  return F;
612 }
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:71
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
Definition: NTLconvert.cc:442
const poly a
Definition: syzextra.cc:212
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFactorize.h:77
void Off(int sw)
switches
CanonicalForm cd(bCommonDen(FF))
Definition: cfModGcd.cc:4030
int cmpCF(const CFFactor &f, const CFFactor &g)
Definition: cf_factor.cc:379
int singular_homog_flag
Definition: cf_factor.cc:377
factory&#39;s class for variables
Definition: factory.h:115
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Definition: NTLconvert.cc:180
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p multi, const Variable &x)
Definition: NTLconvert.cc:395
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition: cf_defs.h:36
factory&#39;s main class
Definition: canonicalform.h:75
nmod_poly_clear(FLINTmipo)
List< CFFactor > CFFList
CFList ratSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree multivariate polynomial over
Definition: facFactorize.h:53
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:687
CFList FpSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over
Variable alpha
Definition: facAbsBiFact.cc:52
void insert(const T &)
Definition: ftmpl_list.cc:193
CFList GFSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over GF
int xn
Definition: walk.cc:4466
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
int getCharacteristic()
Definition: cf_char.cc:51
void removeFirst()
Definition: ftmpl_list.cc:287
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
T getFirst() const
Definition: ftmpl_list.cc:279
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
int j
Definition: myNF.cc:70
Variable get_max_degree_Variable(const CanonicalForm &f)
get_max_degree_Variable returns Variable with highest degree.
Definition: cf_factor.cc:245
convertFacCF2nmod_poly_t(FLINTmipo, M)
bool isUnivariate() const
T & getItem() const
Definition: ftmpl_list.cc:431
CanonicalForm homogenize(const CanonicalForm &f, const Variable &x)
homogenize homogenizes f with Variable x
Definition: cf_factor.cc:298
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
FILE * f
Definition: checklibs.c:7
int i
Definition: cfEzgcd.cc:123
CanonicalForm factor
Definition: facAbsFact.cc:101
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CFFList factorize(const CanonicalForm &f, bool issqrfree)
factorization over or
Definition: cf_factor.cc:390
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
class CFMap
Definition: cf_map.h:84
static int gettype()
Definition: cf_factory.h:27
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:103
Factor< CanonicalForm > CFFactor
bool isHomogeneous() const
#define GaloisFieldDomain
Definition: cf_defs.h:22
#define ASSERT(expression, message)
Definition: cf_assert.h:99
void append(const T &)
Definition: ftmpl_list.cc:256
long fac_NTL_char
Definition: NTLconvert.cc:44
int degree(const CanonicalForm &f)
CFFList convertNTLvec_pair_ZZX_long2FacCFFList(const vec_pair_ZZX_long &e, const ZZ &multi, const Variable &x)
NAME: convertNTLvec_pair_ZZX_long2FacCFFList.
Definition: NTLconvert.cc:749
return result
Definition: facAbsBiFact.cc:76
void(* factoryError)(const char *s)
Definition: cf_util.cc:75
void sort(int(*)(const T &, const T &))
Definition: ftmpl_list.cc:339
bool inCoeffDomain() const

§ factorize() [2/2]

CFFList factorize ( const CanonicalForm f,
const Variable alpha 
)

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

Definition at line 617 of file cf_factor.cc.

618 {
619  if ( f.inCoeffDomain() )
620  return CFFList( f );
621  //out_cf("factorize:",f,"==================================\n");
622  //out_cf("mipo:",getMipo(alpha),"\n");
623 
624  CFFList F;
625  ASSERT( alpha.level() < 0 && getReduce (alpha), "not an algebraic extension" );
626 #ifndef NOASSERT
627  Variable beta;
628  if (hasFirstAlgVar(f, beta))
629  ASSERT (beta == alpha, "f has an algebraic variable that \
630  does not coincide with alpha");
631 #endif
632  int ch=getCharacteristic();
633  if (f.isUnivariate()&& (ch>0))
634  {
635 #ifdef HAVE_NTL
636  //USE NTL
637  if (ch>2)
638  {
639 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
640  nmod_poly_t FLINTmipo, leadingCoeff;
641  fq_nmod_ctx_t fq_con;
642 
643  nmod_poly_init (FLINTmipo, getCharacteristic());
644  nmod_poly_init (leadingCoeff, getCharacteristic());
645  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
646 
647  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
648  fq_nmod_poly_t FLINTF;
649  convertFacCF2Fq_nmod_poly_t (FLINTF, f, fq_con);
650  fq_nmod_poly_factor_t res;
651  fq_nmod_poly_factor_init (res, fq_con);
652  fq_nmod_poly_factor (res, leadingCoeff, FLINTF, fq_con);
654  F.insert (CFFactor (Lc (f), 1));
655 
656  fq_nmod_poly_factor_clear (res, fq_con);
657  fq_nmod_poly_clear (FLINTF, fq_con);
658  nmod_poly_clear (FLINTmipo);
659  nmod_poly_clear (leadingCoeff);
660  fq_nmod_ctx_clear (fq_con);
661 #else
662  // First all cases with characteristic !=2
663  // set remainder
665  {
667  zz_p::init(getCharacteristic());
668  }
669 
670  // set minimal polynomial in NTL
671  zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
672  zz_pE::init (minPo);
673 
674  // convert to NTL
675  zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
676  zz_pE leadcoeff= LeadCoeff(f1);
677 
678  //make monic
679  f1=f1 / leadcoeff;
680 
681  // factorize using NTL
682  vec_pair_zz_pEX_long factors;
683  CanZass(factors,f1);
684 
685  // return converted result
686  F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
687 #endif
688  }
689  else if (/*getCharacteristic()*/ch==2)
690  {
691  // special case : GF2
692 
693  // remainder is two ==> nothing to do
694 
695  // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
696  GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
697  GF2E::init (minPo);
698 
699  // convert to NTL again using the faster conversion routines
700  GF2EX f1;
701  if (isPurePoly(f))
702  {
703  GF2X f_tmp=convertFacCF2NTLGF2X(f);
704  f1=to_GF2EX(f_tmp);
705  }
706  else
707  f1=convertFacCF2NTLGF2EX(f,minPo);
708 
709  // make monic (in Z/2(a))
710  GF2E f1_coef=LeadCoeff(f1);
711  MakeMonic(f1);
712 
713  // factorize using NTL
714  vec_pair_GF2EX_long factors;
715  CanZass(factors,f1);
716 
717  // return converted result
718  F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
719  }
720 #else
721  factoryError ("univariate factorization depends on NTL(missing)");
722  return CFFList (CFFactor (f, 1));
723 #endif //HAVE_NTL
724  }
725  else if (ch>0)
726  {
727  #ifdef HAVE_NTL
728  F= FqFactorize (f, alpha);
729  #else
730  ASSERT( f.isUnivariate(), "multivariate factorization depends on NTL(missing)" );
731  factoryError ("multivariate factorization depends on NTL(missing)");
732  return CFFList (CFFactor (f, 1));
733  #endif
734 
735  }
736  else if (f.isUnivariate() && (ch == 0)) // Q(a)[x]
737  {
738  F= AlgExtFactorize (f, alpha);
739  }
740  else //Q(a)[x1,...,xn]
741  {
742 #ifdef HAVE_NTL
743  F= ratFactorize (f, alpha);
744 #else
745  ASSERT( f.isUnivariate(), "multivariate factorization depends on NTL(missing)" );
746  factoryError ("multivariate factorization depends on NTL(missing)");
747  return CFFList (CFFactor (f, 1));
748 #endif
749  }
750  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
751  return F;
752 }
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
Definition: NTLconvert.cc:1008
nmod_poly_init(FLINTmipo, getCharacteristic())
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &multi, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
Definition: NTLconvert.cc:956
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFactorize.h:77
int cmpCF(const CFFactor &f, const CFFactor &g)
Definition: cf_factor.cc:379
factory&#39;s class for variables
Definition: factory.h:115
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Definition: NTLconvert.cc:180
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
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
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition: cf_defs.h:36
nmod_poly_clear(FLINTmipo)
List< CFFactor > CFFList
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:94
Variable alpha
Definition: facAbsBiFact.cc:52
void insert(const T &)
Definition: ftmpl_list.cc:193
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
int getCharacteristic()
Definition: cf_char.cc:51
fq_nmod_ctx_clear(fq_con)
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &multi, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:867
poly res
Definition: myNF.cc:322
CFFList AlgExtFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a univariate polynomial over algebraic extension of Q
Definition: facAlgExt.cc:364
convertFacCF2nmod_poly_t(FLINTmipo, M)
int level() const
Definition: factory.h:132
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1065
bool isUnivariate() const
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
bool getReduce(const Variable &alpha)
Definition: variable.cc:232
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
bool isOn(int sw)
switches
bool isPurePoly(const CanonicalForm &f)
Definition: cf_factor.cc:229
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
fq_nmod_poly_clear(prod, fq_con)
Variable beta
Definition: facAbsFact.cc:99
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:103
#define ASSERT(expression, message)
Definition: cf_assert.h:99
long fac_NTL_char
Definition: NTLconvert.cc:44
void(* factoryError)(const char *s)
Definition: cf_util.cc:75
void sort(int(*)(const T &, const T &))
Definition: ftmpl_list.cc:339
bool inCoeffDomain() const
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")

§ Farey()

Farey rational reconstruction.

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

Definition at line 197 of file cf_chinese.cc.

198 {
199  int is_rat=isOn(SW_RATIONAL);
200  Off(SW_RATIONAL);
201  Variable x = f.mvar();
202  CanonicalForm result = 0;
203  CanonicalForm c;
204  CFIterator i;
205 #ifdef HAVE_NTL
206  ZZ NTLq= convertFacCF2NTLZZ (q);
207  ZZ bound;
208  SqrRoot (bound, NTLq/2);
209 #endif
210  for ( i = f; i.hasTerms(); i++ )
211  {
212  c = i.coeff();
213  if ( c.inCoeffDomain())
214  {
215 #ifdef HAVE_NTL
216  if (c.inZ())
217  {
218  ZZ NTLc= convertFacCF2NTLZZ (c);
219  bool lessZero= (sign (NTLc) == -1);
220  if (lessZero)
221  NTL::negate (NTLc, NTLc);
222  ZZ NTLnum, NTLden;
223  if (ReconstructRational (NTLnum, NTLden, NTLc, NTLq, bound, bound))
224  {
225  if (lessZero)
226  NTL::negate (NTLnum, NTLnum);
227  CanonicalForm num= convertNTLZZX2CF (to_ZZX (NTLnum), Variable (1));
228  CanonicalForm den= convertNTLZZX2CF (to_ZZX (NTLden), Variable (1));
229  On (SW_RATIONAL);
230  result += power (x, i.exp())*(num/den);
231  Off (SW_RATIONAL);
232  }
233  }
234  else
235  result += power( x, i.exp() ) * Farey(c,q);
236 #else
237  if (c.inZ())
238  result += power( x, i.exp() ) * Farey_n(c,q);
239  else
240  result += power( x, i.exp() ) * Farey(c,q);
241 #endif
242  }
243  else
244  result += power( x, i.exp() ) * Farey(c,q);
245  }
246  if (is_rat) On(SW_RATIONAL);
247  return result;
248 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Definition: NTLconvert.cc:666
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
void Off(int sw)
switches
CanonicalForm num(const CanonicalForm &f)
factory&#39;s class for variables
Definition: factory.h:115
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
factory&#39;s main class
Definition: canonicalform.h:75
CanonicalForm Farey(const CanonicalForm &f, const CanonicalForm &q)
Farey rational reconstruction.
Definition: cf_chinese.cc:197
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
void On(int sw)
switches
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CanonicalForm den(const CanonicalForm &f)
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
bool inZ() const
predicates
Variable x
Definition: cfModGcd.cc:4023
CF_NO_INLINE int exp() const
get the current exponent
static int sign(int x)
Definition: ring.cc:3412
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition: NTLconvert.cc:281
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const

§ fdivides() [1/2]

bool fdivides ( const CanonicalForm f,
const CanonicalForm g 
)

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

fdivides() - check whether `f' divides `g'.

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

Type info:

f, g: Current

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

Developers note:

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

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

Definition at line 338 of file cf_algorithm.cc.

339 {
340  // trivial cases
341  if ( g.isZero() )
342  return true;
343  else if ( f.isZero() )
344  return false;
345 
346  if ( (f.inCoeffDomain() || g.inCoeffDomain())
347  && ((getCharacteristic() == 0 && isOn( SW_RATIONAL ))
348  || (getCharacteristic() > 0) ))
349  {
350  // if we are in a field all elements not equal to zero are units
351  if ( f.inCoeffDomain() )
352  return true;
353  else
354  // g.inCoeffDomain()
355  return false;
356  }
357 
358  // we may assume now that both levels either equal LEVELBASE
359  // or are greater zero
360  int fLevel = f.level();
361  int gLevel = g.level();
362  if ( (gLevel > 0) && (fLevel == gLevel) )
363  // f and g are polynomials in the same main variable
364  if ( degree( f ) <= degree( g )
365  && fdivides( f.tailcoeff(), g.tailcoeff() )
366  && fdivides( f.LC(), g.LC() ) )
367  {
368  CanonicalForm q, r;
369  return divremt( g, f, q, r ) && r.isZero();
370  }
371  else
372  return false;
373  else if ( gLevel < fLevel )
374  // g is a coefficient w.r.t. f
375  return false;
376  else
377  {
378  // either f is a coefficient w.r.t. polynomial g or both
379  // f and g are from a base domain (should be Z or Z/p^n,
380  // then)
381  CanonicalForm q, r;
382  return divremt( g, f, q, r ) && r.isZero();
383  }
384 }
bool divremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:75
int getCharacteristic()
Definition: cf_char.cc:51
const ring r
Definition: syzextra.cc:208
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
CanonicalForm tailcoeff() const
tailcoeff() - return least coefficient
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)
bool inCoeffDomain() const
CanonicalForm LC() const

§ fdivides() [2/2]

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

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

Definition at line 388 of file cf_algorithm.cc.

389 {
390  quot= 0;
391  // trivial cases
392  if ( g.isZero() )
393  return true;
394  else if ( f.isZero() )
395  return false;
396 
397  if ( (f.inCoeffDomain() || g.inCoeffDomain())
398  && ((getCharacteristic() == 0 && isOn( SW_RATIONAL ))
399  || (getCharacteristic() > 0) ))
400  {
401  // if we are in a field all elements not equal to zero are units
402  if ( f.inCoeffDomain() )
403  {
404  quot= g/f;
405  return true;
406  }
407  else
408  // g.inCoeffDomain()
409  return false;
410  }
411 
412  // we may assume now that both levels either equal LEVELBASE
413  // or are greater zero
414  int fLevel = f.level();
415  int gLevel = g.level();
416  if ( (gLevel > 0) && (fLevel == gLevel) )
417  // f and g are polynomials in the same main variable
418  if ( degree( f ) <= degree( g )
419  && fdivides( f.tailcoeff(), g.tailcoeff() )
420  && fdivides( f.LC(), g.LC() ) )
421  {
422  CanonicalForm q, r;
423  if (divremt( g, f, q, r ) && r.isZero())
424  {
425  quot= q;
426  return true;
427  }
428  else
429  return false;
430  }
431  else
432  return false;
433  else if ( gLevel < fLevel )
434  // g is a coefficient w.r.t. f
435  return false;
436  else
437  {
438  // either f is a coefficient w.r.t. polynomial g or both
439  // f and g are from a base domain (should be Z or Z/p^n,
440  // then)
441  CanonicalForm q, r;
442  if (divremt( g, f, q, r ) && r.isZero())
443  {
444  quot= q;
445  return true;
446  }
447  else
448  return false;
449  }
450 }
bool divremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:75
int getCharacteristic()
Definition: cf_char.cc:51
const ring r
Definition: syzextra.cc:208
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
bool isOn(int sw)
switches
FILE * f
Definition: checklibs.c:7
CanonicalForm tailcoeff() const
tailcoeff() - return least coefficient
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)
bool inCoeffDomain() const
CanonicalForm LC() const

§ get_max_degree_Variable()

Variable get_max_degree_Variable ( const CanonicalForm f)

get_max_degree_Variable returns Variable with highest degree.

We assume f is not a constant!

Definition at line 245 of file cf_factor.cc.

246 {
247  ASSERT( ( ! f.inCoeffDomain() ), "no constants" );
248  int max=0, maxlevel=0, n=level(f);
249  for ( int i=1; i<=n; i++ )
250  {
251  if (degree(f,Variable(i)) >= max)
252  {
253  max= degree(f,Variable(i)); maxlevel= i;
254  }
255  }
256  return Variable(maxlevel);
257 }
int level(const CanonicalForm &f)
factory&#39;s class for variables
Definition: factory.h:115
static int max(int a, int b)
Definition: fast_mult.cc:264
int i
Definition: cfEzgcd.cc:123
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int degree(const CanonicalForm &f)
bool inCoeffDomain() const

§ get_Terms()

CFList get_Terms ( const CanonicalForm f)

Definition at line 274 of file cf_factor.cc.

274  {
275  CFList result,dummy,dummy2;
276  CFIterator i;
278 
279  if ( getNumVars(f) == 0 ) result.append(f);
280  else{
281  Variable _x(level(f));
282  for ( i=f; i.hasTerms(); i++ ){
283  getTerms(i.coeff(), 1, dummy);
284  for ( j=dummy; j.hasItem(); j++ )
285  result.append(j.getItem() * power(_x, i.exp()));
286 
287  dummy= dummy2; // have to initalize new
288  }
289  }
290  return result;
291 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int level(const CanonicalForm &f)
factory&#39;s class for variables
Definition: factory.h:115
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
int j
Definition: myNF.cc:70
T & getItem() const
Definition: ftmpl_list.cc:431
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
Definition: cf_factor.cc:264
int i
Definition: cfEzgcd.cc:123
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
void append(const T &)
Definition: ftmpl_list.cc:256
CF_NO_INLINE int exp() const
get the current exponent
return result
Definition: facAbsBiFact.cc:76

§ getTerms()

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

get_Terms: Split the polynomial in the containing terms.

getTerms: the real work is done here.

Definition at line 264 of file cf_factor.cc.

265 {
266  if ( getNumVars(f) == 0 ) result.append(f*t);
267  else{
268  Variable x(level(f));
269  for ( CFIterator i=f; i.hasTerms(); i++ )
270  getTerms( i.coeff(), t*power(x,i.exp()), result);
271  }
272 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int level(const CanonicalForm &f)
factory&#39;s class for variables
Definition: factory.h:115
void getTerms(const CanonicalForm &f, const CanonicalForm &t, CFList &result)
get_Terms: Split the polynomial in the containing terms.
Definition: cf_factor.cc:264
int i
Definition: cfEzgcd.cc:123
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
int getNumVars(const CanonicalForm &f)
int getNumVars ( const CanonicalForm & f )
Definition: cf_ops.cc:314
Variable x
Definition: cfModGcd.cc:4023
void append(const T &)
Definition: ftmpl_list.cc:256

§ homogenize() [1/2]

CanonicalForm homogenize ( const CanonicalForm f,
const Variable x 
)

homogenize homogenizes f with Variable x

Definition at line 298 of file cf_factor.cc.

299 {
300 #if 0
301  int maxdeg=totaldegree(f), deg;
302  CFIterator i;
303  CanonicalForm elem, result(0);
304 
305  for (i=f; i.hasTerms(); i++)
306  {
307  elem= i.coeff()*power(f.mvar(),i.exp());
308  deg = totaldegree(elem);
309  if ( deg < maxdeg )
310  result += elem * power(x,maxdeg-deg);
311  else
312  result+=elem;
313  }
314  return result;
315 #else
316  CFList Newlist, Termlist= get_Terms(f);
317  int maxdeg=totaldegree(f), deg;
319  CanonicalForm elem, result(0);
320 
321  for (i=Termlist; i.hasItem(); i++)
322  {
323  elem= i.getItem();
324  deg = totaldegree(elem);
325  if ( deg < maxdeg )
326  Newlist.append(elem * power(x,maxdeg-deg));
327  else
328  Newlist.append(elem);
329  }
330  for (i=Newlist; i.hasItem(); i++) // rebuild
331  result += i.getItem();
332 
333  return result;
334 #endif
335 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
factory&#39;s main class
Definition: canonicalform.h:75
CFList get_Terms(const CanonicalForm &f)
Definition: cf_factor.cc:274
T & getItem() const
Definition: ftmpl_list.cc:431
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
void append(const T &)
Definition: ftmpl_list.cc:256
CF_NO_INLINE int exp() const
get the current exponent
return result
Definition: facAbsBiFact.cc:76

§ homogenize() [2/2]

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

Definition at line 338 of file cf_factor.cc.

339 {
340 #if 0
341  int maxdeg=totaldegree(f), deg;
342  CFIterator i;
343  CanonicalForm elem, result(0);
344 
345  for (i=f; i.hasTerms(); i++)
346  {
347  elem= i.coeff()*power(f.mvar(),i.exp());
348  deg = totaldegree(elem);
349  if ( deg < maxdeg )
350  result += elem * power(x,maxdeg-deg);
351  else
352  result+=elem;
353  }
354  return result;
355 #else
356  CFList Newlist, Termlist= get_Terms(f);
357  int maxdeg=totaldegree(f), deg;
359  CanonicalForm elem, result(0);
360 
361  for (i=Termlist; i.hasItem(); i++)
362  {
363  elem= i.getItem();
364  deg = totaldegree(elem,v1,v2);
365  if ( deg < maxdeg )
366  Newlist.append(elem * power(x,maxdeg-deg));
367  else
368  Newlist.append(elem);
369  }
370  for (i=Newlist; i.hasItem(); i++) // rebuild
371  result += i.getItem();
372 
373  return result;
374 #endif
375 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
factory&#39;s main class
Definition: canonicalform.h:75
CFList get_Terms(const CanonicalForm &f)
Definition: cf_factor.cc:274
T & getItem() const
Definition: ftmpl_list.cc:431
int i
Definition: cfEzgcd.cc:123
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
CF_NO_INLINE int hasTerms() const
check if iterator has reached < the end of CanonicalForm
int totaldegree(const CanonicalForm &f)
int totaldegree ( const CanonicalForm & f )
Definition: cf_ops.cc:523
void append(const T &)
Definition: ftmpl_list.cc:256
CF_NO_INLINE int exp() const
get the current exponent
return result
Definition: facAbsBiFact.cc:76

§ isPurePoly()

bool isPurePoly ( const CanonicalForm f)

Definition at line 229 of file cf_factor.cc.

230 {
231  if (f.level()<=0) return false;
232  for (CFIterator i=f;i.hasTerms();i++)
233  {
234  if (!(i.coeff().inBaseDomain())) return false;
235  }
236  return true;
237 }
int i
Definition: cfEzgcd.cc:123
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
int level() const
level() returns the level of CO.

§ isPurePoly_m()

bool isPurePoly_m ( const CanonicalForm f)

Definition at line 219 of file cf_factor.cc.

220 {
221  if (f.inBaseDomain()) return true;
222  if (f.level()<0) return false;
223  for (CFIterator i=f;i.hasTerms();i++)
224  {
225  if (!isPurePoly_m(i.coeff())) return false;
226  }
227  return true;
228 }
bool isPurePoly_m(const CanonicalForm &f)
Definition: cf_factor.cc:219
bool inBaseDomain() const
int i
Definition: cfEzgcd.cc:123
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
int level() const
level() returns the level of CO.

§ linearSystemSolve()

bool linearSystemSolve ( CFMatrix M)

Definition at line 78 of file cf_linsys.cc.

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

§ maxNorm()

CanonicalForm maxNorm ( const CanonicalForm f)

CanonicalForm maxNorm ( const CanonicalForm & f )

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

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

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

Type info:

f: CurrentPP

Definition at line 534 of file cf_algorithm.cc.

535 {
536  if ( f.inBaseDomain() )
537  return abs( f );
538  else {
539  CanonicalForm result = 0;
540  for ( CFIterator i = f; i.hasTerms(); i++ ) {
541  CanonicalForm coeffMaxNorm = maxNorm( i.coeff() );
542  if ( coeffMaxNorm > result )
543  result = coeffMaxNorm;
544  }
545  return result;
546  }
547 }
factory&#39;s main class
Definition: canonicalform.h:75
Rational abs(const Rational &a)
Definition: GMPrat.cc:443
bool inBaseDomain() const
int i
Definition: cfEzgcd.cc:123
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )
class to iterate through CanonicalForm&#39;s
Definition: cf_iter.h:44
return result
Definition: facAbsBiFact.cc:76

§ psq()

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

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

`g' must not equal zero.

Type info:

f, g: Current x: Polynomial

Developers note:

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

See also
psr(), psqr()

Definition at line 172 of file cf_algorithm.cc.

173 {
174  ASSERT( x.level() > 0, "type error: polynomial variable expected" );
175  ASSERT( ! g.isZero(), "math error: division by zero" );
176 
177  // swap variables such that x's level is larger or equal
178  // than both f's and g's levels.
179  Variable X = tmax( tmax( f.mvar(), g.mvar() ), x );
180  CanonicalForm F = swapvar( f, x, X );
181  CanonicalForm G = swapvar( g, x, X );
182 
183  // now, we have to calculate the pseudo remainder of F and G
184  // w.r.t. X
185  int fDegree = degree( F, X );
186  int gDegree = degree( G, X );
187  if ( fDegree < 0 || fDegree < gDegree )
188  return 0;
189  else {
190  CanonicalForm result = (power( LC( G, X ), fDegree-gDegree+1 ) * F) / G;
191  return swapvar( result, x, X );
192  }
193 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
factory&#39;s class for variables
Definition: factory.h:115
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:75
static TreeM * G
Definition: janet.cc:38
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int level() const
Definition: factory.h:132
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76

§ psqr()

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

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

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

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

See `psr()' for more detailed information.

Type info:

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

Developers note:

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

See also
psr(), psq()

Definition at line 223 of file cf_algorithm.cc.

224 {
225  ASSERT( x.level() > 0, "type error: polynomial variable expected" );
226  ASSERT( ! g.isZero(), "math error: division by zero" );
227 
228  // swap variables such that x's level is larger or equal
229  // than both f's and g's levels.
230  Variable X = tmax( tmax( f.mvar(), g.mvar() ), x );
231  CanonicalForm F = swapvar( f, x, X );
232  CanonicalForm G = swapvar( g, x, X );
233 
234  // now, we have to calculate the pseudo remainder of F and G
235  // w.r.t. X
236  int fDegree = degree( F, X );
237  int gDegree = degree( G, X );
238  if ( fDegree < 0 || fDegree < gDegree ) {
239  q = 0; r = f;
240  } else {
241  divrem( power( LC( G, X ), fDegree-gDegree+1 ) * F, G, q, r );
242  q = swapvar( q, x, X );
243  r = swapvar( r, x, X );
244  }
245 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
factory&#39;s class for variables
Definition: factory.h:115
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:75
static TreeM * G
Definition: janet.cc:38
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int level() const
Definition: factory.h:132
FILE * f
Definition: checklibs.c:7
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
void divrem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r)

§ psr()

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

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

`g' must not equal zero.

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

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

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

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

Type info:

f, g: Current x: Polynomial

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

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

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

Developers note:

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

See also
psq(), psqr()

Definition at line 117 of file cf_algorithm.cc.

118 {
119  CanonicalForm r=rr, v=vv, l, test, lu, lv, t, retvalue;
120  int dr, dv, d,n=0;
121 
122 
123  dr = degree( r, x );
124  if (dr>0)
125  {
126  dv = degree( v, x );
127  if (dv <= dr) {l=LC(v,x); v = v -l*power(x,dv);}
128  else { l = 1; }
129  d= dr-dv+1;
130  //out_cf("psr(",rr," ");
131  //out_cf("",vv," ");
132  //printf(" var=%d\n",x.level());
133  while ( ( dv <= dr ) && ( !r.isZero()) )
134  {
135  test = power(x,dr-dv)*v*LC(r,x);
136  if ( dr == 0 ) { r= CanonicalForm(0); }
137  else { r= r - LC(r,x)*power(x,dr); }
138  r= l*r -test;
139  dr= degree(r,x);
140  n+=1;
141  }
142  r= power(l, d-n)*r;
143  }
144  return r;
145 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:75
const ring r
Definition: syzextra.cc:208
CanonicalForm test
Definition: cfModGcd.cc:4037
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
int l
Definition: cfEzgcd.cc:94

§ resultant()

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

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

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

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

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

Definition at line 173 of file cf_resultant.cc.

174 {
175  ASSERT( x.level() > 0, "cannot calculate resultant with respect to algebraic variables" );
176 
177  // some checks on triviality. We will not use degree( v )
178  // here because this may involve variable swapping.
179  if ( f.isZero() || g.isZero() )
180  return 0;
181  if ( f.mvar() < x )
182  return power( f, g.degree( x ) );
183  if ( g.mvar() < x )
184  return power( g, f.degree( x ) );
185 
186  // make x main variale
187  CanonicalForm F, G;
188  Variable X;
189  if ( f.mvar() > x || g.mvar() > x ) {
190  if ( f.mvar() > g.mvar() )
191  X = f.mvar();
192  else
193  X = g.mvar();
194  F = swapvar( f, X, x );
195  G = swapvar( g, X, x );
196  }
197  else {
198  X = x;
199  F = f;
200  G = g;
201  }
202  // at this point, we have to calculate resultant( F, G, X )
203  // where X is equal to or greater than the main variables
204  // of F and G
205 
206  int m = degree( F, X );
207  int n = degree( G, X );
208  // catch trivial cases
209  if ( m+n <= 2 || m == 0 || n == 0 )
210  return swapvar( trivialResultant( F, G, X ), X, x );
211 
212  // exchange F and G if necessary
213  int flipFactor;
214  if ( m < n ) {
215  CanonicalForm swap = F;
216  F = G; G = swap;
217  int degswap = m;
218  m = n; n = degswap;
219  if ( m & 1 && n & 1 )
220  flipFactor = -1;
221  else
222  flipFactor = 1;
223  } else
224  flipFactor = 1;
225 
226  // this is not an effective way to calculate the resultant!
227  CanonicalForm extFactor;
228  if ( m == n ) {
229  if ( n & 1 )
230  extFactor = -LC( G, X );
231  else
232  extFactor = LC( G, X );
233  } else
234  extFactor = power( LC( F, X ), m-n-1 );
235 
237  result = subResChain( F, G, X )[0] / extFactor;
238 
239  return swapvar( result, X, x ) * flipFactor;
240 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
factory&#39;s class for variables
Definition: factory.h:115
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
static TreeM * G
Definition: janet.cc:38
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
int level() const
Definition: factory.h:132
CFArray subResChain(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) ...
Definition: cf_resultant.cc:42
int m
Definition: cfEzgcd.cc:119
FILE * f
Definition: checklibs.c:7
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
#define swap(_i, _j)
Variable x
Definition: cfModGcd.cc:4023
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
static CanonicalForm trivialResultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
static CanonicalForm trivialResultant ( const CanonicalForm & f, const CanonicalForm & g...
return result
Definition: facAbsBiFact.cc:76

§ sqrFree()

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

squarefree factorization

Definition at line 757 of file cf_factor.cc.

758 {
759 // ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
760  CFFList result;
761 
762  if ( getCharacteristic() == 0 )
763  result = sqrFreeZ( f );
764  else
765  {
766  Variable alpha;
767  if (hasFirstAlgVar (f, alpha))
768  result = FqSqrf( f, alpha );
769  else
770  result= FpSqrf (f);
771  }
772  if (sort)
773  {
774  CFFactor buf= result.getFirst();
775  result.removeFirst();
776  result= sortCFFList (result);
777  result.insert (buf);
778  }
779  return result;
780 }
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped ...
CFFList sqrFreeZ(const CanonicalForm &a)
Definition: fac_sqrfree.cc:45
factory&#39;s class for variables
Definition: factory.h:115
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped ...
Variable alpha
Definition: facAbsBiFact.cc:52
void insert(const T &)
Definition: ftmpl_list.cc:193
int getCharacteristic()
Definition: cf_char.cc:51
void removeFirst()
Definition: ftmpl_list.cc:287
T getFirst() const
Definition: ftmpl_list.cc:279
int status int void * buf
Definition: si_signals.h:59
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
CFFList sortCFFList(CFFList &F)
Definition: fac_sqrfree.cc:21
void sort(CFArray &A, int l=0)
quick sort A
return result
Definition: facAbsBiFact.cc:76

§ subResChain()

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

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

subResChain() - caculate extended subresultant chain.

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

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

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

Definition at line 42 of file cf_resultant.cc.

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

§ tryFdivides()

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

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

Definition at line 454 of file cf_algorithm.cc.

455 {
456  fail= false;
457  // trivial cases
458  if ( g.isZero() )
459  return true;
460  else if ( f.isZero() )
461  return false;
462 
463  if (f.inCoeffDomain() || g.inCoeffDomain())
464  {
465  // if we are in a field all elements not equal to zero are units
466  if ( f.inCoeffDomain() )
467  {
468  CanonicalForm inv;
469  tryInvert (f, M, inv, fail);
470  return !fail;
471  }
472  else
473  {
474  return false;
475  }
476  }
477 
478  // we may assume now that both levels either equal LEVELBASE
479  // or are greater zero
480  int fLevel = f.level();
481  int gLevel = g.level();
482  if ( (gLevel > 0) && (fLevel == gLevel) )
483  {
484  if (degree( f ) > degree( g ))
485  return false;
486  bool dividestail= tryFdivides (f.tailcoeff(), g.tailcoeff(), M, fail);
487 
488  if (fail || !dividestail)
489  return false;
490  bool dividesLC= tryFdivides (f.LC(),g.LC(), M, fail);
491  if (fail || !dividesLC)
492  return false;
493  CanonicalForm q,r;
494  bool divides= tryDivremt (g, f, q, r, M, fail);
495  if (fail || !divides)
496  return false;
497  return r.isZero();
498  }
499  else if ( gLevel < fLevel )
500  {
501  // g is a coefficient w.r.t. f
502  return false;
503  }
504  else
505  {
506  // either f is a coefficient w.r.t. polynomial g or both
507  // f and g are from a base domain (should be Z or Z/p^n,
508  // then)
509  CanonicalForm q, r;
510  bool divides= tryDivremt (g, f, q, r, M, fail);
511  if (fail || !divides)
512  return false;
513  return r.isZero();
514  }
515 }
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:75
void tryInvert(const CanonicalForm &F, const CanonicalForm &M, CanonicalForm &inv, bool &fail)
Definition: cfGcdAlgExt.cc:219
#define M
Definition: sirandom.c:24
const ring r
Definition: syzextra.cc:208
CanonicalForm tailcoeff() const
tailcoeff() - return least coefficient
bool tryDivremt(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, const CanonicalForm &M, bool &fail)
same as divremt but handles zero divisors in case we are in Z_p[x]/(f) where f is not irreducible ...
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)
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 ...
bool inCoeffDomain() const
CanonicalForm LC() const

Variable Documentation

§ singular_homog_flag

int singular_homog_flag

Definition at line 377 of file cf_factor.cc.