My Project  UNKNOWN_GIT_VERSION
Functions
facAlgFuncUtil.h File Reference

Utility functions for factorization over algebraic function fields. More...

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 &As)
 
int hasVar (const CanonicalForm &f, const Variable &v)
 
int hasAlgVar (const CanonicalForm &f)
 
CanonicalForm generateMipo (int degOfExt)
 
CanonicalForm alg_lc (const CanonicalForm &f)
 
CanonicalForm alg_LC (const CanonicalForm &f, int lev)
 
void deflateDegree (const CanonicalForm &F, int &pExp, int n)
 
CanonicalForm deflatePoly (const CanonicalForm &F, int exps, int n)
 
CanonicalForm inflatePoly (const CanonicalForm &F, int exps, int n)
 
void multiplicity (CFFList &factors, const CanonicalForm &F, const CFList &as)
 
CanonicalForm backSubst (const CanonicalForm &F, const CFList &a, const CFList &b)
 
CanonicalForm subst (const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
 
CanonicalForm divide (const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
 
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, 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...
 
int getDegOfExt (IntList &degreelist, int n)
 
bool isInseparable (const CFList &Astar)
 

Detailed Description

Utility functions for factorization over algebraic 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.h.

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 }
FILE * f
Definition: checklibs.c:9
CanonicalForm alg_lc(const CanonicalForm &f)

◆ 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 }
CanonicalForm LC(const CanonicalForm &f)
factory's main class
Definition: canonicalform.h:83
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 i
Definition: cfEzgcd.cc:125
int exp() const
Definition: ftmpl_factor.h:31
T factor() const
Definition: ftmpl_factor.h:30
void append(const T &)
Definition: ftmpl_list.cc:256
CFArray copy(const CFList &list)
write elements of list into an array
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:358

◆ 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 }
CanonicalForm b
Definition: cfModGcd.cc:4044
#define ASSERT(expression, message)
Definition: cf_assert.h:99
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
T & getItem() const
Definition: ftmpl_list.cc:431
int length() const
Definition: ftmpl_list.cc:273
T getLast() const
Definition: ftmpl_list.cc:309
void removeLast()
Definition: ftmpl_list.cc:317
factory's class for variables
Definition: factory.h:118
CFFListIterator iter
Definition: facAbsBiFact.cc:54
CFList tmp2
Definition: facFqBivar.cc:70

◆ 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 getCharacteristic()
Definition: cf_char.cc:51
int p
Definition: cfModGcd.cc:4019
g
Definition: cfModGcd.cc:4031
int igcd(int a, int b)
Definition: cf_util.cc:51
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
CanonicalForm deriv() const
deriv() - return the formal derivation of CO.
int level() const
level() returns the level of CO.
void deflateDegree(const CanonicalForm &F, int &pExp, int n)
int status int void size_t count
Definition: si_signals.h:59

◆ deflatePoly()

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
CanonicalForm deflatePoly(const CanonicalForm &F, int exp)

◆ 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 }
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
int m
Definition: cfEzgcd.cc:121
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
CanonicalForm Sprem(const CanonicalForm &f, const CanonicalForm &g, CanonicalForm &m, CanonicalForm &q)

◆ evaluate()

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 }
Variable x
Definition: cfModGcd.cc:4023
CanonicalForm evaluate(const CanonicalForm &f, const CanonicalForm &g, const CanonicalForm &h, const CanonicalForm &powH)
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
static Poly * h
Definition: janet.cc:972

◆ 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 }
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
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
generate random elements in F_p
Definition: cf_random.h:44

◆ 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 }
void setCharacteristic(int c)
Definition: cf_char.cc:23
int l
Definition: cfEzgcd.cc:93
int k
Definition: cfEzgcd.cc:92
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:263

◆ hasAlgVar()

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 }
int hasAlgVar(const CanonicalForm &f, const Variable &v)

◆ 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 }
int hasVar(const CanonicalForm &f, const Variable &v)

◆ inflatePoly()

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 inflatePoly(const CanonicalForm &F, int exp)

◆ 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 }

◆ 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)

◆ 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 }
Factor< CanonicalForm > CFFactor
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:32

◆ 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 }
int degree(const CanonicalForm &f)
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:175
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
#define pi
Definition: libparse.cc:1143
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ 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;
130  CanonicalForm tmp1= i.getItem();
131  i++;
132  CanonicalForm tmp2= j.getItem();
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 vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:225
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CFList tmp1
Definition: facFqBivar.cc:70
int j
Definition: facHensel.cc:105

◆ varsInAs()

Varlist varsInAs ( const Varlist uord,
const CFList As 
)

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 }