Functions
facAlgFuncUtil.cc File Reference

This file provides utility functions to factorize polynomials over alg. More...

#include "config.h"
#include "cf_assert.h"
#include "canonicalform.h"
#include "facAlgFuncUtil.h"
#include "cfCharSetsUtil.h"
#include "cf_random.h"
#include "cf_irred.h"
#include "cf_algorithm.h"
#include "cf_util.h"
#include "cf_iter.h"

Go to the source code of this file.

Functions

CFFList append (const CFFList &Inputlist, const CFFactor &TheFactor)
 
CFFList merge (const CFFList &Inputlist1, const CFFList &Inputlist2)
 
Varlist varsInAs (const Varlist &uord, const CFList &Astar)
 
CanonicalForm generateMipo (int degOfExt)
 
CanonicalForm alg_lc (const CanonicalForm &f)
 
CanonicalForm alg_LC (const CanonicalForm &f, int lev)
 
CanonicalForm subst (const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
 
CanonicalForm backSubst (const CanonicalForm &F, const CFList &a, const CFList &b)
 
void deflateDegree (const CanonicalForm &F, int &pExp, int n)
 
CanonicalForm deflatePoly (const CanonicalForm &F, int exp)
 
CanonicalForm deflatePoly (const CanonicalForm &F, int exps, int n)
 
CanonicalForm inflatePoly (const CanonicalForm &F, int exp)
 
CanonicalForm inflatePoly (const CanonicalForm &F, int exps, int n)
 
void multiplicity (CFFList &factors, const CanonicalForm &F, const CFList &as)
 
int hasAlgVar (const CanonicalForm &f, const Variable &v)
 
int hasVar (const CanonicalForm &f, const Variable &v)
 
int hasAlgVar (const CanonicalForm &f)
 
void psqr (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, CanonicalForm &multiplier, const Variable &x)
 pseudo division of f and g wrt. x s.t. multiplier*f=q*g+r More...
 
CanonicalForm Sprem (const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &m, CanonicalForm &q)
 
CanonicalForm divide (const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
 
bool isInseparable (const CFList &Astar)
 
int getDegOfExt (IntList &degreelist, int n)
 
CanonicalForm QuasiInverse (const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
 
CanonicalForm evaluate (const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &h, const CanonicalForm &powH)
 
CanonicalForm evaluate (const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &h, const CanonicalForm &powH, const Variable &v)
 evaluate f at g/h at v such that powH*f is integral i.e. powH is assumed to be h^degree(f,v) More...
 

Detailed Description

This file provides utility functions to factorize polynomials over alg.

function fields

Note
some of the code is code from libfac or derived from code from libfac. Libfac is written by M. Messollen. See also COPYING for license information and README for general information on characteristic sets.
Author
Martin Lee

Definition in file facAlgFuncUtil.cc.

Function Documentation

◆ alg_lc()

Definition at line 100 of file facAlgFuncUtil.cc.

101 {
102  if (f.level()>0)
103  {
104  return alg_lc(f.LC());
105  }
106 
107  return f;
108 }
CanonicalForm alg_lc(const CanonicalForm &f)
FILE * f
Definition: checklibs.c:9
int level() const
level() returns the level of CO.
CanonicalForm LC() const

◆ alg_LC()

CanonicalForm alg_LC ( const CanonicalForm f,
int  lev 
)

Definition at line 110 of file facAlgFuncUtil.cc.

111 {
113  while (result.level() > lev)
114  result= LC (result);
115  return result;
116 }
factory's main class
Definition: canonicalform.h:75
FILE * f
Definition: checklibs.c:9
int level() const
level() returns the level of CO.
CanonicalForm LC(const CanonicalForm &f)
return result
Definition: facAbsBiFact.cc:76

◆ append()

CFFList append ( const CFFList Inputlist,
const CFFactor TheFactor 
)

Definition at line 32 of file facAlgFuncUtil.cc.

33 {
34  CFFList Outputlist;
35  CFFactor copy;
37  int exp=0;
38 
39  for (i= Inputlist; i.hasItem() ; i++)
40  {
41  copy= i.getItem();
42  if (copy.factor() == TheFactor.factor())
43  exp += copy.exp();
44  else
45  Outputlist.append(copy);
46  }
47  Outputlist.append (CFFactor (TheFactor.factor(), exp + TheFactor.exp()));
48  return Outputlist;
49 }
int exp() const
Definition: ftmpl_factor.h:33
CFArray copy(const CFList &list)
write elements of list into an array
T factor() const
Definition: ftmpl_factor.h:32
T & getItem() const
Definition: ftmpl_list.cc:431
int i
Definition: cfEzgcd.cc:123
p exp[i]
Definition: DebugPrint.cc:39
void append(const T &)
Definition: ftmpl_list.cc:256

◆ backSubst()

CanonicalForm backSubst ( const CanonicalForm F,
const CFList a,
const CFList b 
)

Definition at line 178 of file facAlgFuncUtil.cc.

179 {
180  ASSERT (a.length() == b.length() - 1, "wrong length of lists in backSubst");
182  Variable tmp;
183  CFList tmp2= b;
184  tmp= tmp2.getLast().mvar();
185  tmp2.removeLast();
186  for (CFListIterator iter= a; iter.hasItem(); iter++)
187  {
188  result= result (tmp+iter.getItem()*tmp2.getLast().mvar(), tmp);
189  tmp= tmp2.getLast().mvar();
190  tmp2.removeLast();
191  }
192  return result;
193 }
factory's class for variables
Definition: factory.h:115
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory's main class
Definition: canonicalform.h:75
void removeLast()
Definition: ftmpl_list.cc:317
T & getItem() const
Definition: ftmpl_list.cc:431
T getLast() const
Definition: ftmpl_list.cc:309
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CFList tmp2
Definition: facFqBivar.cc:70
int length() const
Definition: ftmpl_list.cc:273
#define ASSERT(expression, message)
Definition: cf_assert.h:99
const poly b
Definition: syzextra.cc:213
return result
Definition: facAbsBiFact.cc:76

◆ deflateDegree()

void deflateDegree ( const CanonicalForm F,
int &  pExp,
int  n 
)

Definition at line 195 of file facAlgFuncUtil.cc.

196 {
197  if (n == 0 || n > F.level())
198  {
199  pExp= -1;
200  return;
201  }
202  if (F.level() == n)
203  {
204  ASSERT (F.deriv().isZero(), "derivative of F is not zero");
205  CFIterator i= F;
206  int g= 0;
207  for (; i.hasTerms(); i++)
208  g= igcd (g, i.exp());
209 
210  int count= 0;
211  int p= getCharacteristic();
212  while ((g >= p) && (g != 0) && (g % p == 0))
213  {
214  g /= p;
215  count++;
216  }
217  pExp= count;
218  }
219  else
220  {
221  CFIterator i= F;
222  deflateDegree (i.coeff(), pExp, n);
223  i++;
224  int tmp= pExp;
225  for (; i.hasTerms(); i++)
226  {
227  deflateDegree (i.coeff(), pExp, n);
228  if (tmp == -1)
229  tmp= pExp;
230  else if (tmp != -1 && pExp != -1)
231  pExp= (pExp < tmp) ? pExp : tmp;
232  else
233  pExp= tmp;
234  }
235  }
236 }
int status int void size_t count
Definition: si_signals.h:59
return P p
Definition: myNF.cc:203
int igcd(int a, int b)
Definition: cf_util.cc:51
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
g
Definition: cfModGcd.cc:4031
CanonicalForm deriv() const
deriv() - return the formal derivation of CO.
int getCharacteristic()
Definition: cf_char.cc:51
void deflateDegree(const CanonicalForm &F, int &pExp, int n)
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.
#define ASSERT(expression, message)
Definition: cf_assert.h:99

◆ deflatePoly() [1/2]

CanonicalForm deflatePoly ( const CanonicalForm F,
int  exp 
)

Definition at line 238 of file facAlgFuncUtil.cc.

239 {
240  if (exp == 0)
241  return F;
242  int p= getCharacteristic();
243  int pToExp= ipower (p, exp);
244  Variable x=F.mvar();
246  for (CFIterator i= F; i.hasTerms(); i++)
247  result += i.coeff()*power (x, i.exp()/pToExp);
248  return result;
249 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
return P p
Definition: myNF.cc:203
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
int getCharacteristic()
Definition: cf_char.cc:51
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
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:25
Variable x
Definition: cfModGcd.cc:4023
p exp[i]
Definition: DebugPrint.cc:39
return result
Definition: facAbsBiFact.cc:76

◆ deflatePoly() [2/2]

CanonicalForm deflatePoly ( const CanonicalForm F,
int  exps,
int  n 
)

Definition at line 251 of file facAlgFuncUtil.cc.

252 {
253  if (n == 0 || exps <= 0 || F.level() < n)
254  return F;
255  if (F.level() == n)
256  return deflatePoly (F, exps);
257  else
258  {
260  for (CFIterator i= F; i.hasTerms(); i++)
261  result += deflatePoly (i.coeff(), exps, n)*power(F.mvar(), i.exp());
262  return result;
263  }
264 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
factory&#39;s main class
Definition: canonicalform.h:75
CanonicalForm deflatePoly(const CanonicalForm &F, int exp)
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
int level() const
level() returns the level of CO.
return result
Definition: facAbsBiFact.cc:76

◆ divide()

CanonicalForm divide ( const CanonicalForm ff,
const CanonicalForm f,
const CFList as 
)

Definition at line 500 of file facAlgFuncUtil.cc.

501 {
502  CanonicalForm r, m, q;
503 
504  if (f.inCoeffDomain())
505  {
506  bool isRat= isOn(SW_RATIONAL);
507  if (getCharacteristic() == 0)
508  On(SW_RATIONAL);
509  q= ff/f;
510  if (!isRat && getCharacteristic() == 0)
511  Off(SW_RATIONAL);
512  }
513  else
514  r= Sprem (ff, f, m, q);
515 
516  r= Prem (q, as);
517  return r;
518 }
void Off(int sw)
switches
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
int m
Definition: cfEzgcd.cc:119
bool isOn(int sw)
switches
void On(int sw)
switches
FILE * f
Definition: checklibs.c:9
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
CanonicalForm Sprem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &m, CanonicalForm &q)
bool inCoeffDomain() const

◆ evaluate() [1/2]

Definition at line 640 of file facAlgFuncUtil.cc.

642 {
643  if (f.inCoeffDomain())
644  return f;
645  CFIterator i= f;
646  int lastExp = i.exp();
647  CanonicalForm result = i.coeff()*powH;
648  i++;
649  while (i.hasTerms())
650  {
651  int i_exp= i.exp();
652  if ((lastExp - i_exp) == 1)
653  {
654  result *= g;
655  result /= h;
656  }
657  else
658  {
659  result *= power (g, lastExp - i_exp);
660  result /= power (h, lastExp - i_exp);
661  }
662  result += i.coeff()*powH;
663  lastExp = i_exp;
664  i++;
665  }
666  if (lastExp != 0)
667  {
668  result *= power (g, lastExp);
669  result /= power (h, lastExp);
670  }
671  return result;
672 }
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
g
Definition: cfModGcd.cc:4031
FILE * f
Definition: checklibs.c:9
int i
Definition: cfEzgcd.cc:123
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
CF_NO_INLINE int exp() const
get the current exponent
static Poly * h
Definition: janet.cc:978
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const

◆ evaluate() [2/2]

evaluate f at g/h at v such that powH*f is integral i.e. powH is assumed to be h^degree(f,v)

Definition at line 677 of file facAlgFuncUtil.cc.

680 {
681  if (f.inCoeffDomain())
682  {
683  return f*powH;
684  }
685 
686  Variable x = f.mvar();
687  if ( v > x )
688  return f*powH;
689  else if ( v == x )
690  return evaluate (f, g, h, powH);
691 
692  // v is less than main variable of f
694  for (CFIterator i= f; i.hasTerms(); i++)
695  result += evaluate (i.coeff(), g, h, powH, v)*power (x, i.exp());
696  return result;
697 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm evaluate(const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &h, const CanonicalForm &powH)
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
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
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
Variable x
Definition: cfModGcd.cc:4023
static Poly * h
Definition: janet.cc:978
return result
Definition: facAbsBiFact.cc:76
bool inCoeffDomain() const

◆ generateMipo()

CanonicalForm generateMipo ( int  degOfExt)

Definition at line 90 of file facAlgFuncUtil.cc.

91 {
92 #ifndef HAVE_NTL
93  FFRandom gen;
94  return find_irreducible (degOfExt, gen, Variable (1));
95 #else
96  return randomIrredpoly (degOfExt, Variable (1));
97 #endif
98 }
factory&#39;s class for variables
Definition: factory.h:115
generate random elements in F_p
Definition: cf_random.h:43
CanonicalForm find_irreducible(int deg, CFRandom &gen, const Variable &x)
generate a random irreducible polynomial in x of degree deg
Definition: cf_irred.cc:26
CanonicalForm randomIrredpoly(int i, const Variable &x)
computes a random monic irreducible univariate polynomial in x over Fp of degree i via NTL ...
Definition: cf_irred.cc:42

◆ getDegOfExt()

int getDegOfExt ( IntList degreelist,
int  n 
)

Definition at line 543 of file facAlgFuncUtil.cc.

544 {
545  int charac= getCharacteristic();
546  setCharacteristic(0); // need it for k !
547  int k= 1, m= 1, length= degreelist.length();
549 
550  for (i= degreelist; i.hasItem(); i++)
551  m= m*i.getItem();
552  int q= charac;
553  while (q <= ((n*m)*(n*m)/2))
554  {
555  k= k+1;
556  q= q*charac;
557  }
558  int l= 0;
559  do
560  {
561  for (i= degreelist; i.hasItem(); i++)
562  {
563  l= l + 1;
564  if (igcd (k, i.getItem()) == 1)
565  {
566  if (l == length)
567  {
568  setCharacteristic (charac);
569  return k;
570  }
571  }
572  else
573  break;
574  }
575  k= k + 1;
576  l= 0;
577  }
578  while (1);
579 }
int igcd(int a, int b)
Definition: cf_util.cc:51
int k
Definition: cfEzgcd.cc:93
void setCharacteristic(int c)
Definition: cf_char.cc:23
int getCharacteristic()
Definition: cf_char.cc:51
T & getItem() const
Definition: ftmpl_list.cc:431
int m
Definition: cfEzgcd.cc:119
int i
Definition: cfEzgcd.cc:123
int length() const
Definition: ftmpl_list.cc:273
int l
Definition: cfEzgcd.cc:94

◆ hasAlgVar() [1/2]

int hasAlgVar ( const CanonicalForm f,
const Variable v 
)

Definition at line 322 of file facAlgFuncUtil.cc.

323 {
324  if (f.inBaseDomain())
325  return 0;
326  if (f.inCoeffDomain())
327  {
328  if (f.mvar() == v)
329  return 1;
330  return hasAlgVar (f.LC(), v);
331  }
332  if (f.inPolyDomain())
333  {
334  if (hasAlgVar(f.LC(), v))
335  return 1;
336  for (CFIterator i= f; i.hasTerms(); i++)
337  {
338  if (hasAlgVar (i.coeff(), v))
339  return 1;
340  }
341  }
342  return 0;
343 }
bool inBaseDomain() const
bool inPolyDomain() const
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
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int hasAlgVar(const CanonicalForm &f, const Variable &v)
bool inCoeffDomain() const
CanonicalForm LC() const

◆ hasAlgVar() [2/2]

int hasAlgVar ( const CanonicalForm f)

Definition at line 370 of file facAlgFuncUtil.cc.

371 {
372  if (f.inBaseDomain())
373  return 0;
374  if (f.inCoeffDomain())
375  {
376  if (f.level() != 0)
377  return 1;
378  return hasAlgVar(f.LC());
379  }
380  if (f.inPolyDomain())
381  {
382  if (hasAlgVar(f.LC()))
383  return 1;
384  for (CFIterator i= f; i.hasTerms(); i++)
385  {
386  if (hasAlgVar (i.coeff()))
387  return 1;
388  }
389  }
390  return 0;
391 }
bool inBaseDomain() const
bool inPolyDomain() 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.
int hasAlgVar(const CanonicalForm &f, const Variable &v)
bool inCoeffDomain() const
CanonicalForm LC() const

◆ hasVar()

int hasVar ( const CanonicalForm f,
const Variable v 
)

Definition at line 345 of file facAlgFuncUtil.cc.

346 {
347  if (f.inBaseDomain())
348  return 0;
349  if (f.inCoeffDomain())
350  {
351  if (f.mvar() == v)
352  return 1;
353  return hasAlgVar (f.LC(), v);
354  }
355  if (f.inPolyDomain())
356  {
357  if (f.mvar() == v)
358  return 1;
359  if (hasVar (f.LC(), v))
360  return 1;
361  for (CFIterator i= f; i.hasTerms(); i++)
362  {
363  if (hasVar (i.coeff(), v))
364  return 1;
365  }
366  }
367  return 0;
368 }
bool inBaseDomain() const
bool inPolyDomain() const
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
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int hasAlgVar(const CanonicalForm &f, const Variable &v)
int hasVar(const CanonicalForm &f, const Variable &v)
bool inCoeffDomain() const
CanonicalForm LC() const

◆ inflatePoly() [1/2]

CanonicalForm inflatePoly ( const CanonicalForm F,
int  exp 
)

Definition at line 266 of file facAlgFuncUtil.cc.

267 {
268  if (exp == 0)
269  return F;
270  int p= getCharacteristic();
271  int pToExp= ipower (p, exp);
272  Variable x=F.mvar();
274  for (CFIterator i= F; i.hasTerms(); i++)
275  result += i.coeff()*power (x, i.exp()*pToExp);
276  return result;
277 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
return P p
Definition: myNF.cc:203
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
int getCharacteristic()
Definition: cf_char.cc:51
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
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:25
Variable x
Definition: cfModGcd.cc:4023
p exp[i]
Definition: DebugPrint.cc:39
return result
Definition: facAbsBiFact.cc:76

◆ inflatePoly() [2/2]

CanonicalForm inflatePoly ( const CanonicalForm F,
int  exps,
int  n 
)

Definition at line 279 of file facAlgFuncUtil.cc.

280 {
281  if (n == 0 || exps <= 0 || F.level() < n)
282  return F;
283  if (F.level() == n)
284  return inflatePoly (F, exps);
285  else
286  {
288  for (CFIterator i= F; i.hasTerms(); i++)
289  result += inflatePoly (i.coeff(), exps, n)*power(F.mvar(), i.exp());
290  return result;
291  }
292 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
factory&#39;s main class
Definition: canonicalform.h:75
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 inflatePoly(const CanonicalForm &F, int exp)
int level() const
level() returns the level of CO.
return result
Definition: facAbsBiFact.cc:76

◆ isInseparable()

bool isInseparable ( const CFList Astar)

Definition at line 522 of file facAlgFuncUtil.cc.

523 {
524  CanonicalForm elem;
525 
526  if (Astar.length() == 0)
527  return false;
528  for (CFListIterator i= Astar; i.hasItem(); i++)
529  {
530  elem= i.getItem();
531  if (elem.deriv().isZero())
532  return true;
533  }
534  return false;
535 }
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
factory&#39;s main class
Definition: canonicalform.h:75
CanonicalForm deriv() const
deriv() - return the formal derivation of CO.
int i
Definition: cfEzgcd.cc:123
int length() const
Definition: ftmpl_list.cc:273

◆ merge()

CFFList merge ( const CFFList Inputlist1,
const CFFList Inputlist2 
)

Definition at line 52 of file facAlgFuncUtil.cc.

53 {
54  CFFList Outputlist;
56 
57  for (i= Inputlist1; i.hasItem(); i++)
58  Outputlist= append (Outputlist, i.getItem());
59  for (i= Inputlist2; i.hasItem() ; i++)
60  Outputlist= append (Outputlist, i.getItem());
61 
62  return Outputlist;
63 }
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
T & getItem() const
Definition: ftmpl_list.cc:431
int i
Definition: cfEzgcd.cc:123

◆ multiplicity()

void multiplicity ( CFFList factors,
const CanonicalForm F,
const CFList as 
)

Definition at line 295 of file facAlgFuncUtil.cc.

296 {
297  CanonicalForm G= F;
298  Variable x= F.mvar();
299  CanonicalForm q, r;
300  int count= -1;
301  for (CFFListIterator iter=factors; iter.hasItem(); iter++)
302  {
303  count= -1;
304  if (iter.getItem().factor().inCoeffDomain())
305  continue;
306  while (1)
307  {
308  psqr (G, iter.getItem().factor(), q, r, x);
309 
310  q= Prem (q, as);
311  r= Prem (r, as);
312  if (!r.isZero())
313  break;
314  count++;
315  G= q;
316  }
317  iter.getItem()= CFFactor (iter.getItem().factor(),
318  iter.getItem().exp() + count);
319  }
320 }
int status int void size_t count
Definition: si_signals.h:59
factory&#39;s class for variables
Definition: factory.h:115
CFFListIterator iter
Definition: facAbsBiFact.cc:54
factory&#39;s main class
Definition: canonicalform.h:75
void psqr(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, CanonicalForm &multiplier, const Variable &x)
pseudo division of f and g wrt. x s.t. multiplier*f=q*g+r
static TreeM * G
Definition: janet.cc:38
const ring r
Definition: syzextra.cc:208
T & getItem() const
Definition: ftmpl_list.cc:431
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Factor< CanonicalForm > CFFactor
Variable x
Definition: cfModGcd.cc:4023
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled

◆ psqr()

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

pseudo division of f and g wrt. x s.t. multiplier*f=q*g+r

Definition at line 395 of file facAlgFuncUtil.cc.

397 {
398  ASSERT( x.level() > 0, "type error: polynomial variable expected" );
399  ASSERT( ! g.isZero(), "math error: division by zero" );
400 
401  // swap variables such that x's level is larger or equal
402  // than both f's and g's levels.
403  Variable X;
404  if (f.level() > g.level())
405  X= f.mvar();
406  else
407  X= g.mvar();
408  if (X.level() < x.level())
409  X= x;
410  CanonicalForm F= swapvar (f, x, X);
411  CanonicalForm G= swapvar (g, x, X);
412 
413  // now, we have to calculate the pseudo remainder of F and G
414  // w.r.t. X
415  int fDegree= degree (F, X);
416  int gDegree= degree (G, X);
417  if (fDegree < 0 || fDegree < gDegree)
418  {
419  q= 0;
420  r= f;
421  }
422  else
423  {
424  CanonicalForm LCG= LC (G, X);
425  multiplier= power (LCG, fDegree - gDegree + 1);
426  divrem (multiplier*F, G, q, r);
427  q= swapvar (q, x, X);
428  r= swapvar (r, x, X);
429  }
430 }
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
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:9
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
int level() const
level() returns the level of CO.
#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)

◆ QuasiInverse()

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

Definition at line 582 of file facAlgFuncUtil.cc.

584 {
585  CanonicalForm pi, pi1, q, t0, t1, Hi, bi, pi2;
586  bool isRat= isOn (SW_RATIONAL);
587  pi= f;
588  pi1= g;
589  if (isRat)
590  {
591  pi *= bCommonDen (pi);
592  pi1 *= bCommonDen (pi1);
593  }
594  CanonicalForm m,tmp;
595  if (isRat && getCharacteristic() == 0)
596  Off (SW_RATIONAL);
597 
598  pi= pi/content (pi,x);
599  pi1= pi1/content (pi1,x);
600 
601  t0= 0;
602  t1= 1;
603  bi= 1;
604 
605  int delta= degree (f, x) - degree (g, x);
606  Hi= power (LC (pi1, x), delta);
607  if ( (delta+1) % 2 )
608  bi = 1;
609  else
610  bi = -1;
611 
612  while (degree (pi1,x) > 0)
613  {
614  psqr (pi, pi1, q, pi2, m, x);
615  pi2 /= bi;
616 
617  tmp= t1;
618  t1= t0*m - t1*q;
619  t0= tmp;
620  t1 /= bi;
621  pi= pi1;
622  pi1= pi2;
623  if (degree (pi1, x) > 0)
624  {
625  delta= degree (pi, x) - degree (pi1, x);
626  if ((delta + 1) % 2)
627  bi= LC (pi, x)*power (Hi, delta);
628  else
629  bi= -LC (pi, x)*power (Hi, delta);
630  Hi= power (LC (pi1, x), delta)/power (Hi, delta - 1);
631  }
632  }
633  t1 /= gcd (pi1, t1);
634  if (isRat && getCharacteristic() == 0)
635  On (SW_RATIONAL);
636  return t1;
637 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
void Off(int sw)
switches
factory&#39;s main class
Definition: canonicalform.h:75
g
Definition: cfModGcd.cc:4031
void psqr(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &q, CanonicalForm &r, CanonicalForm &multiplier, const Variable &x)
pseudo division of f and g wrt. x s.t. multiplier*f=q*g+r
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
int getCharacteristic()
Definition: cf_char.cc:51
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
int m
Definition: cfEzgcd.cc:119
bool isOn(int sw)
switches
void On(int sw)
switches
FILE * f
Definition: checklibs.c:9
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
#define pi
Definition: libparse.cc:1143
int gcd(int a, int b)
Definition: walkSupport.cc:839
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)

◆ Sprem()

Definition at line 433 of file facAlgFuncUtil.cc.

435 {
436  CanonicalForm ff, gg, l, test, retvalue;
437  int df, dg,n;
438  bool reord;
439  Variable vf, vg, v;
440 
441  if ((vf = f.mvar()) < (vg = g.mvar()))
442  {
443  m= 0;
444  q= 0;
445  return f;
446  }
447  else
448  {
449  if ( vf == vg )
450  {
451  ff= f;
452  gg= g;
453  reord= false;
454  v= vg; // == x
455  }
456  else
457  {
458  v= Variable (f.level() + 1);
459  ff= swapvar (f, vg, v); // == r
460  gg= swapvar (g, vg, v); // == v
461  reord=true;
462  }
463  dg= degree (gg, v); // == dv
464  df= degree (ff, v); // == dr
465  if (dg <= df)
466  {
467  l= LC (gg);
468  gg= gg - LC(gg)*power(v,dg);
469  }
470  else
471  l = 1;
472  n= 0;
473  while ((dg <= df) && (!ff.isZero()))
474  {
475  test= gg*LC (ff)*power (v, df - dg);
476  if (df == 0)
477  ff= 0;
478  else
479  ff= ff - LC(ff)*power(v,df);
480  ff= l*ff - test;
481  df= degree (ff, v);
482  n++;
483  }
484 
485  if (reord)
486  retvalue= swapvar (ff, vg, v);
487  else
488  retvalue= ff;
489 
490  m= power (l, n);
491  if (fdivides (g, m*f - retvalue))
492  q= (m*f - retvalue)/g;
493  else
494  q= 0;
495  return retvalue;
496  }
497 }
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
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
FILE * f
Definition: checklibs.c:9
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CanonicalForm test
Definition: cfModGcd.cc:4037
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
int level() const
level() returns the level of CO.
int degree(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
int l
Definition: cfEzgcd.cc:94

◆ subst()

CanonicalForm subst ( const CanonicalForm f,
const CFList a,
const CFList b,
const CanonicalForm Rstar,
bool  isFunctionField 
)

Definition at line 120 of file facAlgFuncUtil.cc.

122 {
123  if (isFunctionField)
124  ASSERT ((a.length() - 1)*4 == b.length() || (a.length() == 1 && b.length() == 2), "wrong length of lists");
125  else
126  ASSERT ((a.length() - 1)*2 == b.length() || (a.length() == 1 && b.length() == 1), "lists of equal length expected");
127  CFListIterator j= b;
128  CanonicalForm result= f, tmp, powj, tmp3;
129  CFListIterator i= a;
131  i++;
133  j++;
134  for (;i.hasItem() && j.hasItem(); i++, j++)
135  {
136  if (!isFunctionField)
137  {
138  result= result (j.getItem(), i.getItem().mvar());
139  result= result (tmp2, tmp1.mvar());
140  tmp1= i.getItem();
141  j++;
142  if (j.hasItem())
143  tmp2= j.getItem();
144  }
145  else
146  {
147  tmp= j.getItem();
148  j++;
149  tmp3= j.getItem();
150  j++;
151  powj= power (j.getItem(), degree (result, i.getItem().mvar()));
152  result= evaluate (result, tmp3, j.getItem(), powj, i.getItem().mvar());
153 
154  if (fdivides (powj, result, tmp3))
155  result= tmp3;
156 
157  result /= vcontent (result, Variable (i.getItem().level() + 1));
158 
159  powj= power (tmp, degree (result, tmp1.mvar()));
160  result= evaluate (result, tmp2, tmp, powj, tmp1.mvar());
161 
162  if (fdivides (powj, result, tmp))
163  result= tmp;
164 
165  result /= vcontent (result, Variable (tmp1.level() + 1));
166  tmp1= i.getItem();
167  j++;
168  if (j.hasItem())
169  tmp2= j.getItem();
170  }
171  }
172  result= Prem (result, CFList (Rstar));
173  result /= vcontent (result, Variable (Rstar.level() + 1));
174  return result;
175 }
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
const poly a
Definition: syzextra.cc:212
CanonicalForm evaluate(const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &h, const CanonicalForm &powH)
factory&#39;s class for variables
Definition: factory.h:115
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:230
factory&#39;s main class
Definition: canonicalform.h:75
int j
Definition: myNF.cc:70
T & getItem() const
Definition: ftmpl_list.cc:431
FILE * f
Definition: checklibs.c:9
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.
CFList tmp2
Definition: facFqBivar.cc:70
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
int length() const
Definition: ftmpl_list.cc:273
CFList tmp1
Definition: facFqBivar.cc:70
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
int level() const
level() returns the level of CO.
#define ASSERT(expression, message)
Definition: cf_assert.h:99
int degree(const CanonicalForm &f)
const poly b
Definition: syzextra.cc:213
return result
Definition: facAbsBiFact.cc:76

◆ varsInAs()

Varlist varsInAs ( const Varlist uord,
const CFList Astar 
)

Definition at line 66 of file facAlgFuncUtil.cc.

67 {
68  Varlist output;
69  CanonicalForm elem;
70  Variable x;
71 
72  for (VarlistIterator i= uord; i.hasItem(); i++)
73  {
74  x= i.getItem();
75  for (CFListIterator j= Astar; j.hasItem(); j++ )
76  {
77  elem= j.getItem();
78  if (degree (elem, x) > 0) // x actually occures in Astar
79  {
80  output.append (x);
81  break;
82  }
83  }
84  }
85  return output;
86 }
factory&#39;s class for variables
Definition: factory.h:115
factory&#39;s main class
Definition: canonicalform.h:75
int j
Definition: myNF.cc:70
int i
Definition: cfEzgcd.cc:123
Variable x
Definition: cfModGcd.cc:4023
void append(const T &)
Definition: ftmpl_list.cc:256
int degree(const CanonicalForm &f)