My Project
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 FACTORY_PUBLIC 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 FACTORY_PUBLIC chineseRemainder (const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
 void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2, const CanonicalForm & q2, CanonicalForm & xnew, CanonicalForm & qnew ) More...
 
void FACTORY_PUBLIC chineseRemainder (const CFArray &x, const CFArray &q, CanonicalForm &xnew, CanonicalForm &qnew)
 void chineseRemainder ( const CFArray & x, const CFArray & q, CanonicalForm & xnew, CanonicalForm & qnew ) More...
 
void FACTORY_PUBLIC chineseRemainderCached (const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew, CFArray &inv)
 
void FACTORY_PUBLIC chineseRemainderCached (const CFArray &a, const CFArray &n, CanonicalForm &xnew, CanonicalForm &prod, CFArray &inv)
 
CanonicalForm Farey (const CanonicalForm &f, const CanonicalForm &q)
 Farey rational reconstruction. More...
 
bool isPurePoly (const CanonicalForm &f)
 
bool isPurePoly_m (const CanonicalForm &f)
 
CFFList FACTORY_PUBLIC factorize (const CanonicalForm &f, bool issqrfree=false)
 factorization over $ F_p $ or $ Q $ More...
 
CFFList FACTORY_PUBLIC factorize (const CanonicalForm &f, const Variable &alpha)
 factorization over $ F_p(\alpha) $ or $ Q(\alpha) $ More...
 
CFFList FACTORY_PUBLIC 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 FACTORY_PUBLIC determinant (const CFMatrix &M, int n)
 
CFArray subResChain (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x ) More...
 
CanonicalForm FACTORY_PUBLIC 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

EXTERN_VAR 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 117 of file cf_algorithm.h.

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

◆ bCommonDen()

CanonicalForm bCommonDen ( const CanonicalForm & f )

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

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

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

Type info:

f: CurrentPP

Definition at line 293 of file cf_algorithm.cc.

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

◆ chineseRemainder() [1/2]

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

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

chineseRemainder - integer chinese remaindering.

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

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

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

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

Definition at line 57 of file cf_chinese.cc.

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

◆ chineseRemainder() [2/2]

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

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

chineseRemainder - integer chinese remaindering.

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

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

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

Definition at line 124 of file cf_chinese.cc.

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

◆ chineseRemainderCached() [1/2]

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

Definition at line 308 of file cf_chinese.cc.

309 {
310  CFArray A(2); A[0]=a; A[1]=b;
311  CFArray Q(2); Q[0]=q1; Q[1]=q2;
312  chineseRemainderCached(A,Q,xnew,qnew,inv);
313 }
CanonicalForm b
Definition: cfModGcd.cc:4103
void chineseRemainderCached(const CFArray &a, const CFArray &n, CanonicalForm &xnew, CanonicalForm &prod, CFArray &inv)
Definition: cf_chinese.cc:290
#define A
Definition: sirandom.c:24

◆ chineseRemainderCached() [2/2]

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

Definition at line 290 of file cf_chinese.cc.

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

◆ determinant()

CanonicalForm FACTORY_PUBLIC determinant ( const CFMatrix M,
int  n 
)

Definition at line 222 of file cf_linsys.cc.

223 {
224  typedef int* int_ptr;
225 
226  ASSERT( rows <= M.rows() && rows <= M.columns() && rows > 0, "undefined determinant" );
227  if ( rows == 1 )
228  return M(1,1);
229  else if ( rows == 2 )
230  return M(1,1)*M(2,2)-M(2,1)*M(1,2);
231  else if ( matrix_in_Z( M, rows ) )
232  {
233  int ** mm = new int_ptr[rows];
234  CanonicalForm x, q, Qhalf, B;
235  int n, i, intdet, p, pno;
236  for ( i = 0; i < rows; i++ )
237  {
238  mm[i] = new int[rows];
239  }
240  pno = 0; n = 0;
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 }
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
int m
Definition: cfEzgcd.cc:128
int k
Definition: cfEzgcd.cc:99
void FACTORY_PUBLIC chineseRemainder(const CanonicalForm &x1, const CanonicalForm &q1, const CanonicalForm &x2, const CanonicalForm &q2, CanonicalForm &xnew, CanonicalForm &qnew)
void chineseRemainder ( const CanonicalForm & x1, const CanonicalForm & q1, const CanonicalForm & x2,...
Definition: cf_chinese.cc:57
bool matrix_in_Z(const CFMatrix &M, int rows)
Definition: cf_linsys.cc:39
bool betterpivot(const CanonicalForm &oldpivot, const CanonicalForm &newpivot)
Definition: cf_linsys.cc:61
CanonicalForm detbound(const CFMatrix &M, int rows)
Definition: cf_linsys.cc:486
int determinant(int **extmat, int n)
Definition: cf_linsys.cc:556
static bool fill_int_mat(const CFMatrix &M, int **m, int rows)
Definition: cf_linsys.cc:203
int cf_getBigPrime(int i)
Definition: cf_primes.cc:39
int cf_getNumBigPrimes()
Definition: cf_primes.cc:45
#define DEBOUT(stream, objects)
Definition: debug.h:47
TIMING_START(fac_alg_resultant)
b *CanonicalForm B
Definition: facBivar.cc:52
bool isZero(const CFArray &A)
checks if entries of A are zero
bool pivot(const matrix aMat, const int r1, const int r2, const int c1, const int c2, int *bestR, int *bestC, const ring R)
This code computes a score for each non-zero matrix entry in aMat[r1..r2, c1..c2].
#define M
Definition: sirandom.c:25
int * int_ptr
Definition: structs.h:54
#define TIMING_END(t)
Definition: timing.h:93

◆ euclideanNorm()

CanonicalForm euclideanNorm ( const CanonicalForm f)

CanonicalForm euclideanNorm ( const CanonicalForm & f )

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

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

Type info:

f: UVPoly( Z )

Definition at line 565 of file cf_algorithm.cc.

566 {
567  ASSERT( (f.inBaseDomain() || f.isUnivariate()) && f.LC().inZ(),
568  "type error: univariate poly over Z expected" );
569 
570  CanonicalForm result = 0;
571  for ( CFIterator i = f; i.hasTerms(); i++ ) {
572  CanonicalForm coeff = i.coeff();
573  result += coeff*coeff;
574  }
575  return sqrt( result );
576 }
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
gmp_float sqrt(const gmp_float &a)
Definition: mpr_complex.cc:327

◆ factorize() [1/2]

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

factorization over $ F_p $ or $ Q $

Definition at line 405 of file cf_factor.cc.

406 {
407  if ( f.inCoeffDomain() )
408  return CFFList( f );
409 #ifndef NOASSERT
410  Variable a;
411  ASSERT (!hasFirstAlgVar (f, a), "f has an algebraic variable use factorize \
412  ( const CanonicalForm & f, const Variable & alpha ) instead");
413 #endif
414  //out_cf("factorize:",f,"==================================\n");
415  if (! f.isUnivariate() ) // preprocess homog. polys
416  {
417  if ( singular_homog_flag && f.isHomogeneous())
418  {
420  int d_xn = degree(f,xn);
421  CFMap n;
422  CanonicalForm F = compress(f(1,xn),n);
423  CFFList Intermediatelist;
424  Intermediatelist = factorize(F);
425  CFFList Homoglist;
427  for ( j=Intermediatelist; j.hasItem(); j++ )
428  {
429  Homoglist.append(
430  CFFactor( n(j.getItem().factor()), j.getItem().exp()) );
431  }
432  CFFList Unhomoglist;
433  CanonicalForm unhomogelem;
434  for ( j=Homoglist; j.hasItem(); j++ )
435  {
436  unhomogelem= homogenize(j.getItem().factor(),xn);
437  Unhomoglist.append(CFFactor(unhomogelem,j.getItem().exp()));
438  d_xn -= (degree(unhomogelem,xn)*j.getItem().exp());
439  }
440  if ( d_xn != 0 ) // have to append xn^(d_xn)
441  Unhomoglist.append(CFFactor(CanonicalForm(xn),d_xn));
442  if(isOn(SW_USE_NTL_SORT)) Unhomoglist.sort(cmpCF);
443  return Unhomoglist;
444  }
445  }
446  CFFList F;
447  if ( getCharacteristic() > 0 )
448  {
449  if (f.isUnivariate())
450  {
451 #ifdef HAVE_FLINT
452 #ifdef HAVE_NTL
453  if (degree (f) < 300)
454 #endif
455  {
456  // use FLINT: char p, univariate
457  nmod_poly_t f1;
459  nmod_poly_factor_t result;
460  nmod_poly_factor_init (result);
461  mp_limb_t leadingCoeff= nmod_poly_factor (result, f1);
462  F= convertFLINTnmod_poly_factor2FacCFFList (result, leadingCoeff, f.mvar());
463  nmod_poly_factor_clear (result);
464  nmod_poly_clear (f1);
465  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
466  return F;
467  }
468 #endif
469 #ifdef HAVE_NTL
470  { // NTL char 2, univariate
471  if (getCharacteristic()==2)
472  {
473  // Specialcase characteristic==2
474  if (fac_NTL_char != 2)
475  {
476  fac_NTL_char = 2;
477  zz_p::init(2);
478  }
479  // convert to NTL using the faster conversion routine for characteristic 2
480  GF2X f1=convertFacCF2NTLGF2X(f);
481  // no make monic necessary in GF2
482  //factorize
483  vec_pair_GF2X_long factors;
484  CanZass(factors,f1);
485 
486  // convert back to factory again using the faster conversion routine for vectors over GF2X
487  F=convertNTLvec_pair_GF2X_long2FacCFFList(factors,LeadCoeff(f1),f.mvar());
488  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
489  return F;
490  }
491  }
492 #endif
493 #ifdef HAVE_NTL
494  {
495  // use NTL char p, univariate
497  {
500  }
501 
502  // convert to NTL
503  zz_pX f1=convertFacCF2NTLzzpX(f);
504  zz_p leadcoeff = LeadCoeff(f1);
505 
506  //make monic
507  f1=f1 / LeadCoeff(f1);
508  // factorize
509  vec_pair_zz_pX_long factors;
510  CanZass(factors,f1);
511 
512  F=convertNTLvec_pair_zzpX_long2FacCFFList(factors,leadcoeff,f.mvar());
513  //test_cff(F,f);
514  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
515  return F;
516  }
517 #endif
518 #if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
519  // Use Factory without NTL and without FLINT: char p, univariate
520  {
521  if ( isOn( SW_BERLEKAMP ) )
522  F=FpFactorizeUnivariateB( f, issqrfree );
523  else
524  F=FpFactorizeUnivariateCZ( f, issqrfree, 0, Variable(), Variable() );
525  return F;
526  }
527 #endif
528  }
529  else // char p, multivariate
530  {
532  {
533  #if defined(HAVE_NTL)
534  if (issqrfree)
535  {
536  CFList factors;
537  Variable alpha;
538  factors= GFSqrfFactorize (f);
539  for (CFListIterator i= factors; i.hasItem(); i++)
540  F.append (CFFactor (i.getItem(), 1));
541  }
542  else
543  {
544  Variable alpha;
545  F= GFFactorize (f);
546  }
547  #else
548  factoryError ("multivariate factorization over GF depends on NTL(missing)");
549  return CFFList (CFFactor (f, 1));
550  #endif
551  }
552  else
553  {
554  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
555  if (!isOn(SW_USE_FL_FAC_P))
556  {
557  #endif
558  #if defined(HAVE_NTL)
559  if (issqrfree)
560  {
561  CFList factors;
562  Variable alpha;
563  factors= FpSqrfFactorize (f);
564  for (CFListIterator i= factors; i.hasItem(); i++)
565  F.append (CFFactor (i.getItem(), 1));
566  goto end_charp;
567  }
568  else
569  {
570  Variable alpha;
571  F= FpFactorize (f);
572  goto end_charp;
573  }
574  #endif
575  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700) && defined(HAVE_NTL)
576  }
577  #endif
578  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
579  nmod_mpoly_ctx_t ctx;
580  nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,getCharacteristic());
581  nmod_mpoly_t Flint_f;
582  nmod_mpoly_init(Flint_f,ctx);
583  convFactoryPFlintMP(f,Flint_f,ctx,f.level());
584  nmod_mpoly_factor_t factors;
585  nmod_mpoly_factor_init(factors,ctx);
586  int okay;
587  if (issqrfree) okay=nmod_mpoly_factor_squarefree(factors,Flint_f,ctx);
588  else okay=nmod_mpoly_factor(factors,Flint_f,ctx);
589  nmod_mpoly_t fac;
590  nmod_mpoly_init(fac,ctx);
591  CanonicalForm cf_fac;
592  int cf_exp;
593  cf_fac=nmod_mpoly_factor_get_constant_ui(factors,ctx);
594  F.append(CFFactor(cf_fac,1));
595  for(int i=nmod_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
596  {
597  nmod_mpoly_factor_get_base(fac,factors,i,ctx);
598  cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
599  cf_exp=nmod_mpoly_factor_get_exp_si(factors,i,ctx);
600  F.append(CFFactor(cf_fac,cf_exp));
601  }
602  nmod_mpoly_factor_clear(factors,ctx);
603  nmod_mpoly_clear(Flint_f,ctx);
604  nmod_mpoly_ctx_clear(ctx);
605  if (okay==0)
606  {
609  F=factorize(f,issqrfree);
612  }
613  #endif
614  #if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
615  #ifndef HAVE_NTL
616  factoryError ("multivariate factorization depends on NTL/FLINT(missing)");
617  return CFFList (CFFactor (f, 1));
618  #endif
619  #endif
620  }
621  }
622  }
623  else // char 0
624  {
625  bool on_rational = isOn(SW_RATIONAL);
626  On(SW_RATIONAL);
628  CanonicalForm fz = f * cd;
629  Off(SW_RATIONAL);
630  if ( f.isUnivariate() )
631  {
632  CanonicalForm ic=icontent(fz);
633  fz/=ic;
634  if (fz.degree()==1)
635  {
636  F=CFFList(CFFactor(fz,1));
637  F.insert(CFFactor(ic,1));
638  }
639  else
640  #if defined(HAVE_FLINT) && (__FLINT_RELEASE>=20503) && (__FLINT_RELEASE!= 20600)
641  {
642  // FLINT 2.6.0 has a bug:
643  // factorize x^12-13*x^10-13*x^8+13*x^4+13*x^2-1 runs forever
644  // use FLINT: char 0, univariate
645  fmpz_poly_t f1;
646  convertFacCF2Fmpz_poly_t (f1, fz);
647  fmpz_poly_factor_t result;
648  fmpz_poly_factor_init (result);
649  fmpz_poly_factor(result, f1);
651  fmpz_poly_factor_clear (result);
652  fmpz_poly_clear (f1);
653  if ( ! ic.isOne() )
654  {
655  // according to convertFLINTfmpz_polyfactor2FcaCFFlist,
656  // first entry is in CoeffDomain
657  CFFactor new_first( F.getFirst().factor() * ic );
658  F.removeFirst();
659  F.insert( new_first );
660  }
661  }
662  goto end_char0;
663  #elif defined(HAVE_NTL)
664  {
665  //use NTL
666  ZZ c;
667  vec_pair_ZZX_long factors;
668  //factorize the converted polynomial
669  factor(c,factors,convertFacCF2NTLZZX(fz));
670 
671  //convert the result back to Factory
673  if ( ! ic.isOne() )
674  {
675  // according to convertNTLvec_pair_ZZX_long2FacCFFList
676  // first entry is in CoeffDomain
677  CFFactor new_first( F.getFirst().factor() * ic );
678  F.removeFirst();
679  F.insert( new_first );
680  }
681  }
682  goto end_char0;
683  #else
684  {
685  //Use Factory without NTL: char 0, univariate
686  F = ZFactorizeUnivariate( fz, issqrfree );
687  goto end_char0;
688  }
689  #endif
690  }
691  else // multivariate, char 0
692  {
693  #if defined(HAVE_FLINT) && (__FLINT_RELEASE >= 20700)
694  if (isOn(SW_USE_FL_FAC_0))
695  {
696  On (SW_RATIONAL);
697  fmpz_mpoly_ctx_t ctx;
698  fmpz_mpoly_ctx_init(ctx,f.level(),ORD_LEX);
699  fmpz_mpoly_t Flint_f;
700  fmpz_mpoly_init(Flint_f,ctx);
701  convFactoryPFlintMP(fz,Flint_f,ctx,fz.level());
702  fmpz_mpoly_factor_t factors;
703  fmpz_mpoly_factor_init(factors,ctx);
704  int rr;
705  if (issqrfree) rr=fmpz_mpoly_factor_squarefree(factors,Flint_f,ctx);
706  else rr=fmpz_mpoly_factor(factors,Flint_f,ctx);
707  if (rr==0) printf("fail\n");
708  fmpz_mpoly_t fac;
709  fmpz_mpoly_init(fac,ctx);
710  CanonicalForm cf_fac;
711  int cf_exp;
712  fmpz_t c;
713  fmpz_init(c);
714  fmpz_mpoly_factor_get_constant_fmpz(c,factors,ctx);
715  cf_fac=convertFmpz2CF(c);
716  fmpz_clear(c);
717  F.append(CFFactor(cf_fac,1));
718  for(int i=fmpz_mpoly_factor_length(factors,ctx)-1; i>=0; i--)
719  {
720  fmpz_mpoly_factor_get_base(fac,factors,i,ctx);
721  cf_fac=convFlintMPFactoryP(fac,ctx,f.level());
722  cf_exp=fmpz_mpoly_factor_get_exp_si(factors,i,ctx);
723  F.append(CFFactor(cf_fac,cf_exp));
724  }
725  fmpz_mpoly_factor_clear(factors,ctx);
726  fmpz_mpoly_clear(Flint_f,ctx);
727  fmpz_mpoly_ctx_clear(ctx);
728  goto end_char0;
729  }
730  #endif
731  #if defined(HAVE_NTL)
732  On (SW_RATIONAL);
733  if (issqrfree)
734  {
735  CFList factors= ratSqrfFactorize (fz);
736  for (CFListIterator i= factors; i.hasItem(); i++)
737  F.append (CFFactor (i.getItem(), 1));
738  }
739  else
740  {
741  F = ratFactorize (fz);
742  }
743  #endif
744  #if !defined(HAVE_FLINT) || (__FLINT_RELEASE < 20700)
745  #ifndef HAVE_NTL
746  F=ZFactorizeMultivariate(fz, issqrfree);
747  #endif
748  #endif
749  }
750 
751 end_char0:
752  if ( on_rational )
753  On(SW_RATIONAL);
754  else
755  Off(SW_RATIONAL);
756  if ( ! cd.isOne() )
757  {
758  CFFactor new_first( F.getFirst().factor() / cd );
759  F.removeFirst();
760  F.insert( new_first );
761  }
762  }
763 
764 #if defined(HAVE_NTL)
765 end_charp:
766 #endif
767  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
768  return F;
769 }
CanonicalForm convertFmpz2CF(const fmpz_t coefficient)
conversion of a FLINT integer to CanonicalForm
CFFList convertFLINTnmod_poly_factor2FacCFFList(const nmod_poly_factor_t fac, const mp_limb_t leadingCoeff, const Variable &x)
conversion of a FLINT factorization over Z/p (for word size p) to a CFFList
void convertFacCF2Fmpz_poly_t(fmpz_poly_t result, const CanonicalForm &f)
conversion of a factory univariate polynomial over Z to a fmpz_poly_t
CFFList convertFLINTfmpz_poly_factor2FacCFFList(const fmpz_poly_factor_t fac, const Variable &x)
conversion of a FLINT factorization over Z to a CFFList
CFFList convertNTLvec_pair_GF2X_long2FacCFFList(const vec_pair_GF2X_long &e, GF2, const Variable &x)
NAME: convertNTLvec_pair_GF2X_long2FacCFFList.
Definition: NTLconvert.cc:446
ZZX convertFacCF2NTLZZX(const CanonicalForm &f)
Definition: NTLconvert.cc:691
CFFList convertNTLvec_pair_zzpX_long2FacCFFList(const vec_pair_zz_pX_long &e, const zz_p cont, const Variable &x)
Definition: NTLconvert.cc:399
zz_pX convertFacCF2NTLzzpX(const CanonicalForm &f)
Definition: NTLconvert.cc:105
VAR long fac_NTL_char
Definition: NTLconvert.cc:46
GF2X convertFacCF2NTLGF2X(const CanonicalForm &f)
NAME: convertFacCF2NTLGF2X.
Definition: NTLconvert.cc:184
CFFList convertNTLvec_pair_ZZX_long2FacCFFList(const vec_pair_ZZX_long &e, const ZZ &cont, const Variable &x)
NAME: convertNTLvec_pair_ZZX_long2FacCFFList.
Definition: NTLconvert.cc:753
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
int degree(const CanonicalForm &f)
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
List< CFFactor > CFFList
Factor< CanonicalForm > CFFactor
CanonicalForm cd(bCommonDen(FF))
Definition: cfModGcd.cc:4089
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
static const int SW_USE_FL_GCD_P
set to 1 to use Flints gcd over F_p
Definition: cf_defs.h:47
static const int SW_USE_NTL_SORT
set to 1 to sort factors in a factorization
Definition: cf_defs.h:39
static const int SW_USE_FL_FAC_0
set to 1 to prefer flints multivariate factorization over Z/p
Definition: cf_defs.h:57
static const int SW_USE_FL_FAC_P
set to 1 to prefer flints multivariate factorization over Z/p
Definition: cf_defs.h:55
static const int SW_BERLEKAMP
set to 1 to use Factorys Berlekamp alg.
Definition: cf_defs.h:51
#define GaloisFieldDomain
Definition: cf_defs.h:18
Variable get_max_degree_Variable(const CanonicalForm &f)
get_max_degree_Variable returns Variable with highest degree.
Definition: cf_factor.cc:260
int cmpCF(const CFFactor &f, const CFFactor &g)
Definition: cf_factor.cc:394
VAR int singular_homog_flag
Definition: cf_factor.cc:392
CanonicalForm homogenize(const CanonicalForm &f, const Variable &x)
homogenize homogenizes f with Variable x
Definition: cf_factor.cc:313
CFFList factorize(const CanonicalForm &f, bool issqrfree)
factorization over or
Definition: cf_factor.cc:405
CanonicalForm compress(const CanonicalForm &f, CFMap &m)
CanonicalForm compress ( const CanonicalForm & f, CFMap & m )
Definition: cf_map.cc:210
VAR void(* factoryError)(const char *s)
Definition: cf_util.cc:80
static int gettype()
Definition: cf_factory.h:28
class CFMap
Definition: cf_map.h:85
int degree() const
Returns -1 for the zero polynomial and 0 if CO is in a base domain.
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CF_NO_INLINE bool isOne() const
int level() const
level() returns the level of CO.
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
void sort(int(*)(const T &, const T &))
Definition: ftmpl_list.cc:339
void append(const T &)
Definition: ftmpl_list.cc:256
void insert(const T &)
Definition: ftmpl_list.cc:193
factory's class for variables
Definition: factory.h:127
Variable alpha
Definition: facAbsBiFact.cc:51
CanonicalForm factor
Definition: facAbsFact.cc:97
CFFList ratFactorize(const CanonicalForm &G, const Variable &v=Variable(1), bool substCheck=true)
factorize a multivariate polynomial over
Definition: facFactorize.h:79
CFList ratSqrfFactorize(const CanonicalForm &G, const Variable &v=Variable(1))
factorize a squarefree multivariate polynomial over
Definition: facFactorize.h:53
CFList FpSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over
CFFList FpFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over
CFFList GFFactorize(const CanonicalForm &G, bool substCheck=true)
factorize a multivariate polynomial over GF
CFList GFSqrfFactorize(const CanonicalForm &F)
factorize a squarefree multivariate polynomial over GF
convertFacCF2nmod_poly_t(FLINTmipo, M)
nmod_poly_clear(FLINTmipo)
CFFList FpFactorizeUnivariateB(const CanonicalForm &f, bool issqrfree=false)
CFFList FpFactorizeUnivariateCZ(const CanonicalForm &f, bool issqrfree, int numext, const Variable alpha, const Variable beta)
CFFList ZFactorizeMultivariate(const CanonicalForm &f, bool issqrfree)
CFFList ZFactorizeUnivariate(const CanonicalForm &ff, bool issqrfree=false)
void init()
Definition: lintree.cc:864
VAR int xn
Definition: walk.cc:4508

◆ factorize() [2/2]

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

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

Definition at line 774 of file cf_factor.cc.

775 {
776  if ( f.inCoeffDomain() )
777  return CFFList( f );
778  //out_cf("factorize:",f,"==================================\n");
779  //out_cf("mipo:",getMipo(alpha),"\n");
780 
781  CFFList F;
782  ASSERT( alpha.level() < 0 && getReduce (alpha), "not an algebraic extension" );
783 #ifndef NOASSERT
784  Variable beta;
785  if (hasFirstAlgVar(f, beta))
786  ASSERT (beta == alpha, "f has an algebraic variable that \
787  does not coincide with alpha");
788 #endif
789  int ch=getCharacteristic();
790  if (ch>0)
791  {
792  if (f.isUnivariate())
793  {
794 #ifdef HAVE_NTL
795  if (/*getCharacteristic()*/ch==2)
796  {
797  // special case : GF2
798 
799  // remainder is two ==> nothing to do
800 
801  // set minimal polynomial in NTL using the optimized conversion routines for characteristic 2
802  GF2X minPo=convertFacCF2NTLGF2X(getMipo(alpha,f.mvar()));
803  GF2E::init (minPo);
804 
805  // convert to NTL again using the faster conversion routines
806  GF2EX f1;
807  if (isPurePoly(f))
808  {
809  GF2X f_tmp=convertFacCF2NTLGF2X(f);
810  f1=to_GF2EX(f_tmp);
811  }
812  else
813  f1=convertFacCF2NTLGF2EX(f,minPo);
814 
815  // make monic (in Z/2(a))
816  GF2E f1_coef=LeadCoeff(f1);
817  MakeMonic(f1);
818 
819  // factorize using NTL
820  vec_pair_GF2EX_long factors;
821  CanZass(factors,f1);
822 
823  // return converted result
824  F=convertNTLvec_pair_GF2EX_long2FacCFFList(factors,f1_coef,f.mvar(),alpha);
825  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
826  return F;
827  }
828 #endif
829 #if (HAVE_FLINT && __FLINT_RELEASE >= 20400)
830  {
831  // use FLINT
832  nmod_poly_t FLINTmipo, leadingCoeff;
833  fq_nmod_ctx_t fq_con;
834 
835  nmod_poly_init (FLINTmipo, ch);
836  nmod_poly_init (leadingCoeff, ch);
837  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
838 
839  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
840  fq_nmod_poly_t FLINTF;
842  fq_nmod_poly_factor_t res;
843  fq_nmod_poly_factor_init (res, fq_con);
844  fq_nmod_poly_factor (res, leadingCoeff, FLINTF, fq_con);
846  F.insert (CFFactor (Lc (f), 1));
847 
848  fq_nmod_poly_factor_clear (res, fq_con);
849  fq_nmod_poly_clear (FLINTF, fq_con);
850  nmod_poly_clear (FLINTmipo);
851  nmod_poly_clear (leadingCoeff);
853  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
854  return F;
855  }
856 #endif
857 #ifdef HAVE_NTL
858  {
859  // use NTL
860  if (fac_NTL_char != ch)
861  {
862  fac_NTL_char = ch;
863  zz_p::init(ch);
864  }
865 
866  // set minimal polynomial in NTL
867  zz_pX minPo=convertFacCF2NTLzzpX(getMipo(alpha));
868  zz_pE::init (minPo);
869 
870  // convert to NTL
871  zz_pEX f1=convertFacCF2NTLzz_pEX(f,minPo);
872  zz_pE leadcoeff= LeadCoeff(f1);
873 
874  //make monic
875  f1=f1 / leadcoeff; //leadcoeff==LeadCoeff(f1);
876 
877  // factorize
878  vec_pair_zz_pEX_long factors;
879  CanZass(factors,f1);
880 
881  // return converted result
882  F=convertNTLvec_pair_zzpEX_long2FacCFFList(factors,leadcoeff,f.mvar(),alpha);
883  //test_cff(F,f);
884  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
885  return F;
886  }
887 #endif
888 #if !defined(HAVE_NTL) && !defined(HAVE_FLINT)
889  // char p, extension, univariate
890  CanonicalForm c=Lc(f);
891  CanonicalForm fc=f/c;
892  F=FpFactorizeUnivariateCZ( fc, false, 1, alpha, Variable() );
893  F.insert (CFFactor (c, 1));
894 #endif
895  }
896  else // char p, multivariate
897  {
898  #if (HAVE_FLINT && __FLINT_RELEASE >= 20700)
899  // use FLINT
900  nmod_poly_t FLINTmipo;
901  fq_nmod_ctx_t fq_con;
902  fq_nmod_mpoly_ctx_t ctx;
903 
904  nmod_poly_init (FLINTmipo, ch);
905  convertFacCF2nmod_poly_t (FLINTmipo, getMipo (alpha));
906 
907  fq_nmod_ctx_init_modulus (fq_con, FLINTmipo, "Z");
908  fq_nmod_mpoly_ctx_init(ctx,f.level(),ORD_LEX,fq_con);
909 
910  fq_nmod_mpoly_t FLINTF;
911  fq_nmod_mpoly_init(FLINTF,ctx);
912  convertFacCF2Fq_nmod_mpoly_t(FLINTF,f,ctx,f.level(),fq_con);
913  fq_nmod_mpoly_factor_t res;
914  fq_nmod_mpoly_factor_init (res, ctx);
915  fq_nmod_mpoly_factor (res, FLINTF, ctx);
916  F= convertFLINTFq_nmod_mpoly_factor2FacCFFList (res, ctx,f.level(),fq_con,alpha);
917  //F.insert (CFFactor (Lc (f), 1));
918 
919  fq_nmod_mpoly_factor_clear (res, ctx);
920  fq_nmod_mpoly_clear (FLINTF, ctx);
921  nmod_poly_clear (FLINTmipo);
922  fq_nmod_mpoly_ctx_clear (ctx);
924  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
925  return F;
926  #elif defined(HAVE_NTL)
927  F= FqFactorize (f, alpha);
928  #else
929  factoryError ("multivariate factorization over Z/pZ(alpha) depends on NTL/Flint(missing)");
930  return CFFList (CFFactor (f, 1));
931  #endif
932  }
933  }
934  else // Q(a)[x]
935  {
936  if (f.isUnivariate())
937  {
938  F= AlgExtFactorize (f, alpha);
939  }
940  else //Q(a)[x1,...,xn]
941  {
942  #if defined(HAVE_NTL) || defined(HAVE_FLINT)
943  F= ratFactorize (f, alpha);
944  #else
945  factoryError ("multivariate factorization over Q(alpha) depends on NTL or FLINT (missing)");
946  return CFFList (CFFactor (f, 1));
947  #endif
948  }
949  }
950  if(isOn(SW_USE_NTL_SORT)) F.sort(cmpCF);
951  return F;
952 }
CFFList convertFLINTFq_nmod_poly_factor2FacCFFList(const fq_nmod_poly_factor_t fac, const Variable &x, const Variable &alpha, const fq_nmod_ctx_t fq_con)
conversion of a FLINT factorization over Fq (for word size p) to a CFFList
void convertFacCF2Fq_nmod_poly_t(fq_nmod_poly_t result, const CanonicalForm &f, const fq_nmod_ctx_t ctx)
conversion of a factory univariate poly over F_q to a FLINT fq_nmod_poly_t
zz_pEX convertFacCF2NTLzz_pEX(const CanonicalForm &f, const zz_pX &mipo)
Definition: NTLconvert.cc:1064
CFFList convertNTLvec_pair_zzpEX_long2FacCFFList(const vec_pair_zz_pEX_long &e, const zz_pE &cont, const Variable &x, const Variable &alpha)
Definition: NTLconvert.cc:870
CFFList convertNTLvec_pair_GF2EX_long2FacCFFList(const vec_pair_GF2EX_long &e, const GF2E &cont, const Variable &x, const Variable &alpha)
NAME: convertNTLvec_pair_GF2EX_long2FacCFFList.
Definition: NTLconvert.cc:959
GF2EX convertFacCF2NTLGF2EX(const CanonicalForm &f, const GF2X &mipo)
CanonicalForm in Z_2(a)[X] to NTL GF2EX.
Definition: NTLconvert.cc:1007
CanonicalForm Lc(const CanonicalForm &f)
bool isPurePoly(const CanonicalForm &f)
Definition: cf_factor.cc:244
int level() const
Definition: factory.h:143
CanonicalForm res
Definition: facAbsFact.cc:60
Variable beta
Definition: facAbsFact.cc:95
CFFList AlgExtFactorize(const CanonicalForm &F, const Variable &alpha)
factorize a univariate polynomial over algebraic extension of Q
Definition: facAlgExt.cc:370
CFFList FqFactorize(const CanonicalForm &G, const Variable &alpha, bool substCheck=true)
factorize a multivariate polynomial over
fq_nmod_ctx_t fq_con
Definition: facHensel.cc:99
fq_nmod_ctx_clear(fq_con)
nmod_poly_init(FLINTmipo, getCharacteristic())
fq_nmod_ctx_init_modulus(fq_con, FLINTmipo, "Z")
fq_nmod_poly_clear(prod, fq_con)
CanonicalForm getMipo(const Variable &alpha, const Variable &x)
Definition: variable.cc:207
bool getReduce(const Variable &alpha)
Definition: variable.cc:232

◆ Farey()

Farey rational reconstruction.

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

Definition at line 202 of file cf_chinese.cc.

203 {
204  int is_rat=isOn(SW_RATIONAL);
205  Off(SW_RATIONAL);
206  Variable x = f.mvar();
207  CanonicalForm result = 0;
208  CanonicalForm c;
209  CFIterator i;
210 #ifdef HAVE_FLINT
211  fmpz_t FLINTq;
212  fmpz_init(FLINTq);
213  convertCF2initFmpz(FLINTq,q);
214  fmpz_t FLINTc;
215  fmpz_init(FLINTc);
216  fmpq_t FLINTres;
217  fmpq_init(FLINTres);
218 #elif defined(HAVE_NTL)
219  ZZ NTLq= convertFacCF2NTLZZ (q);
220  ZZ bound;
221  SqrRoot (bound, NTLq/2);
222 #else
223  factoryError("NTL/FLINT missing:Farey");
224 #endif
225  for ( i = f; i.hasTerms(); i++ )
226  {
227  c = i.coeff();
228  if ( c.inCoeffDomain())
229  {
230 #ifdef HAVE_FLINT
231  if (c.inZ())
232  {
233  convertCF2initFmpz(FLINTc,c);
234  fmpq_reconstruct_fmpz(FLINTres,FLINTc,FLINTq);
235  result += power (x, i.exp())*(convertFmpq2CF(FLINTres));
236  }
237 #elif defined(HAVE_NTL)
238  if (c.inZ())
239  {
240  ZZ NTLc= convertFacCF2NTLZZ (c);
241  bool lessZero= (sign (NTLc) == -1);
242  if (lessZero)
243  NTL::negate (NTLc, NTLc);
244  ZZ NTLnum, NTLden;
245  if (ReconstructRational (NTLnum, NTLden, NTLc, NTLq, bound, bound))
246  {
247  if (lessZero)
248  NTL::negate (NTLnum, NTLnum);
249  CanonicalForm num= convertNTLZZX2CF (to_ZZX (NTLnum), Variable (1));
250  CanonicalForm den= convertNTLZZX2CF (to_ZZX (NTLden), Variable (1));
251  On (SW_RATIONAL);
252  result += power (x, i.exp())*(num/den);
253  Off (SW_RATIONAL);
254  }
255  }
256 #else
257  if (c.inZ())
258  result += power (x, i.exp()) * Farey_n(c,q);
259 #endif
260  else
261  result += power( x, i.exp() ) * Farey(c,q);
262  }
263  else
264  result += power( x, i.exp() ) * Farey(c,q);
265  }
266  if (is_rat) On(SW_RATIONAL);
267 #ifdef HAVE_FLINT
268  fmpq_clear(FLINTres);
269  fmpz_clear(FLINTc);
270  fmpz_clear(FLINTq);
271 #endif
272  return result;
273 }
CanonicalForm convertFmpq2CF(const fmpq_t q)
conversion of a FLINT rational to CanonicalForm
void convertCF2initFmpz(fmpz_t result, const CanonicalForm &f)
conversion of a factory integer to fmpz_t(init.)
CanonicalForm convertNTLZZX2CF(const ZZX &polynom, const Variable &x)
Definition: NTLconvert.cc:285
ZZ convertFacCF2NTLZZ(const CanonicalForm &f)
NAME: convertFacCF2NTLZZX.
Definition: NTLconvert.cc:670
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm num(const CanonicalForm &f)
CanonicalForm den(const CanonicalForm &f)
CanonicalForm Farey(const CanonicalForm &f, const CanonicalForm &q)
Farey rational reconstruction.
Definition: cf_chinese.cc:202
static CanonicalForm bound(const CFMatrix &M)
Definition: cf_linsys.cc:460
bool inCoeffDomain() const
bool inZ() const
predicates

◆ fdivides() [1/2]

bool fdivides ( const CanonicalForm f,
const CanonicalForm g 
)

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

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

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

Type info:

f, g: Current

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

Developers note:

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

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

Definition at line 340 of file cf_algorithm.cc.

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

◆ fdivides() [2/2]

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

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

Definition at line 390 of file cf_algorithm.cc.

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

◆ 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 260 of file cf_factor.cc.

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

◆ get_Terms()

CFList get_Terms ( const CanonicalForm f)

Definition at line 289 of file cf_factor.cc.

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

◆ 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 279 of file cf_factor.cc.

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

◆ homogenize() [1/2]

CanonicalForm homogenize ( const CanonicalForm f,
const Variable x 
)

homogenize homogenizes f with Variable x

Definition at line 313 of file cf_factor.cc.

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

◆ homogenize() [2/2]

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

Definition at line 353 of file cf_factor.cc.

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

◆ isPurePoly()

bool isPurePoly ( const CanonicalForm f)

Definition at line 244 of file cf_factor.cc.

245 {
246  if (f.level()<=0) return false;
247  for (CFIterator i=f;i.hasTerms();i++)
248  {
249  if (!(i.coeff().inBaseDomain())) return false;
250  }
251  return true;
252 }

◆ isPurePoly_m()

bool isPurePoly_m ( const CanonicalForm f)

Definition at line 234 of file cf_factor.cc.

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

◆ 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 }
CanonicalForm mapinto(const CanonicalForm &f)
int int ncols
Definition: cf_linsys.cc:32
VAR bool fuzzy_result
Definition: cf_linsys.cc:75
int nrows
Definition: cf_linsys.cc:32
bool solve(int **extmat, int nrows, int ncols)
Definition: cf_linsys.cc:504
long intval() const
conversion functions
#define DEBOUTENDL(stream)
Definition: debug.h:48
#define DEBOUTSL(stream)
Definition: debug.h:46

◆ 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 536 of file cf_algorithm.cc.

537 {
538  if ( f.inBaseDomain() )
539  return abs( f );
540  else {
541  CanonicalForm result = 0;
542  for ( CFIterator i = f; i.hasTerms(); i++ ) {
543  CanonicalForm coeffMaxNorm = maxNorm( i.coeff() );
544  if ( coeffMaxNorm > result )
545  result = coeffMaxNorm;
546  }
547  return result;
548  }
549 }
Rational abs(const Rational &a)
Definition: GMPrat.cc:436
CanonicalForm maxNorm(const CanonicalForm &f)
CanonicalForm maxNorm ( const CanonicalForm & f )

◆ 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 FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
CanonicalForm LC(const CanonicalForm &f)
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
STATIC_VAR TreeM * G
Definition: janet.cc:31

◆ 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 }
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 }
int l
Definition: cfEzgcd.cc:100
CanonicalForm test
Definition: cfModGcd.cc:4096
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
static CanonicalForm * retvalue
Definition: readcf.cc:126

◆ resultant()

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

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

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

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

Definition at line 173 of file cf_resultant.cc.

174 {
175  ASSERT( x.level() > 0, "cannot calculate resultant with respect to algebraic variables" );
176 
177  // some checks on triviality. We will not use degree( v )
178  // here because this may involve variable swapping.
179  if ( f.isZero() || g.isZero() )
180  return 0;
181  if ( f.mvar() < x )
182  return power( f, g.degree( x ) );
183  if ( g.mvar() < x )
184  return power( g, f.degree( x ) );
185 
186  // make x main variale
187  CanonicalForm F, G;
188  Variable X;
189  if ( f.mvar() > x || g.mvar() > x ) {
190  if ( f.mvar() > g.mvar() )
191  X = f.mvar();
192  else
193  X = g.mvar();
194  F = swapvar( f, X, x );
195  G = swapvar( g, X, x );
196  }
197  else {
198  X = x;
199  F = f;
200  G = g;
201  }
202  // at this point, we have to calculate resultant( F, G, X )
203  // where X is equal to or greater than the main variables
204  // of F and G
205 
206  int m = degree( F, X );
207  int n = degree( G, X );
208  // catch trivial cases
209  if ( m+n <= 2 || m == 0 || n == 0 )
210  return swapvar( trivialResultant( F, G, X ), X, x );
211 
212  // exchange F and G if necessary
213  int flipFactor;
214  if ( m < n ) {
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 }
#define swap(_i, _j)
CFArray subResChain(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CFArray subResChain ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
Definition: cf_resultant.cc:42
static CanonicalForm trivialResultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
static CanonicalForm trivialResultant ( const CanonicalForm & f, const CanonicalForm & g,...

◆ sqrFree()

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

squarefree factorization

Definition at line 957 of file cf_factor.cc.

958 {
959 // ASSERT( f.isUnivariate(), "multivariate factorization not implemented" );
960  CFFList result;
961 
962  if ( getCharacteristic() == 0 )
963  result = sqrFreeZ( f );
964  else
965  {
966  Variable alpha;
967  if (hasFirstAlgVar (f, alpha))
968  result = FqSqrf( f, alpha );
969  else
970  result= FpSqrf (f);
971  }
972  if (sort)
973  {
974  CFFactor buf= result.getFirst();
975  result.removeFirst();
977  result.insert (buf);
978  }
979  return result;
980 }
CFFList FqSqrf(const CanonicalForm &F, const Variable &alpha, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
CFFList FpSqrf(const CanonicalForm &F, bool sort=true)
squarefree factorization over . If input is not monic, the leading coefficient is dropped
void sort(CFArray &A, int l=0)
quick sort A
CFFList sqrFreeZ(const CanonicalForm &a)
Definition: fac_sqrfree.cc:49
CFFList sortCFFList(CFFList &F)
Definition: fac_sqrfree.cc:25
int status int void * buf
Definition: si_signals.h:59

◆ 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 psr(const CanonicalForm &rr, const CanonicalForm &vv, const Variable &x)
CanonicalForm psr ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
#define R
Definition: sirandom.c:27

◆ tryFdivides()

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

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

Definition at line 456 of file cf_algorithm.cc.

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

Variable Documentation

◆ singular_homog_flag

EXTERN_VAR int singular_homog_flag

Definition at line 65 of file cf_algorithm.h.