My Project
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:86
return result
Definition: facAbsBiFact.cc:75

◆ 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:132
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:357

◆ 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:4105
#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:134
CFFListIterator iter
Definition: facAbsBiFact.cc:53
CFList tmp2
Definition: facFqBivar.cc:72

◆ 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 FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int p
Definition: cfModGcd.cc:4080
g
Definition: cfModGcd.cc:4092
int igcd(int a, int b)
Definition: cf_util.cc:56
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
CF_NO_INLINE bool isZero() const
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 496 of file facAlgFuncUtil.cc.

497 {
498  CanonicalForm r, m, q;
499 
500  if (f.inCoeffDomain())
501  {
502  bool isRat= isOn(SW_RATIONAL);
503  if (getCharacteristic() == 0)
504  On(SW_RATIONAL);
505  q= ff/f;
506  if (!isRat && getCharacteristic() == 0)
507  Off(SW_RATIONAL);
508  }
509  else
510  r= Sprem (ff, f, m, q);
511 
512  r= Prem (q, as);
513  return r;
514 }
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:128
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:30
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 673 of file facAlgFuncUtil.cc.

676 {
677  if (f.inCoeffDomain())
678  {
679  return f*powH;
680  }
681 
682  Variable x = f.mvar();
683  if ( v > x )
684  return f*powH;
685  else if ( v == x )
686  return evaluate (f, g, h, powH);
687 
688  // v is less than main variable of f
690  for (CFIterator i= f; i.hasTerms(); i++)
691  result += evaluate (i.coeff(), g, h, powH, v)*power (x, i.exp());
692  return result;
693 }
Variable x
Definition: cfModGcd.cc:4084
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:39
STATIC_VAR Poly * h
Definition: janet.cc:971

◆ generateMipo()

CanonicalForm generateMipo ( int  degOfExt)

Definition at line 90 of file facAlgFuncUtil.cc.

91 {
92 #if defined(HAVE_NTL) || defined(HAVE_FLINT)
93  return randomIrredpoly (degOfExt, Variable (1));
94 #else
95  FFRandom gen;
96  return find_irreducible (degOfExt, gen, 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/FLINT
Definition: cf_irred.cc:26
CanonicalForm find_irreducible(int deg, CFRandom &gen, const Variable &x)
generate a random irreducible polynomial in x of degree deg
generate random elements in F_p
Definition: cf_random.h:44

◆ getDegOfExt()

int getDegOfExt ( IntList degreelist,
int  n 
)

Definition at line 539 of file facAlgFuncUtil.cc.

540 {
541  int charac= getCharacteristic();
542  setCharacteristic(0); // need it for k !
543  int k= 1, m= 1, length= degreelist.length();
545 
546  for (i= degreelist; i.hasItem(); i++)
547  m= m*i.getItem();
548  int q= charac;
549  while (q <= ((n*m)*(n*m)/2))
550  {
551  k= k+1;
552  q= q*charac;
553  }
554  int l= 0;
555  do
556  {
557  for (i= degreelist; i.hasItem(); i++)
558  {
559  l= l + 1;
560  if (igcd (k, i.getItem()) == 1)
561  {
562  if (l == length)
563  {
564  setCharacteristic (charac);
565  return k;
566  }
567  }
568  else
569  break;
570  }
571  k= k + 1;
572  l= 0;
573  }
574  while (1);
575 }
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
int l
Definition: cfEzgcd.cc:100
int k
Definition: cfEzgcd.cc:99
static BOOLEAN length(leftv result, leftv arg)
Definition: interval.cc:257

◆ 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.inExtension())
375  {
376  return 1;
377  }
378  if (f.inPolyDomain())
379  {
380  for (CFIterator i= f; i.hasTerms(); i++)
381  {
382  if (hasAlgVar (i.coeff()))
383  return 1;
384  }
385  }
386  return 0;
387 }
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 518 of file facAlgFuncUtil.cc.

519 {
520  CanonicalForm elem;
521 
522  if (Astar.length() == 0)
523  return false;
524  for (CFListIterator i= Astar; i.hasItem(); i++)
525  {
526  elem= i.getItem();
527  if (elem.deriv().isZero())
528  return true;
529  }
530  return false;
531 }

◆ 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_VAR TreeM * G
Definition: janet.cc:31

◆ QuasiInverse()

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

Definition at line 578 of file facAlgFuncUtil.cc.

580 {
581  CanonicalForm pi, pi1, q, t0, t1, Hi, bi, pi2;
582  bool isRat= isOn (SW_RATIONAL);
583  pi= f;
584  pi1= g;
585  if (isRat)
586  {
587  pi *= bCommonDen (pi);
588  pi1 *= bCommonDen (pi1);
589  }
590  CanonicalForm m,tmp;
591  if (isRat && getCharacteristic() == 0)
592  Off (SW_RATIONAL);
593 
594  pi= pi/content (pi,x);
595  pi1= pi1/content (pi1,x);
596 
597  t0= 0;
598  t1= 1;
599  bi= 1;
600 
601  int delta= degree (f, x) - degree (g, x);
602  Hi= power (LC (pi1, x), delta);
603  if ( (delta+1) % 2 )
604  bi = 1;
605  else
606  bi = -1;
607 
608  while (degree (pi1,x) > 0)
609  {
610  psqr (pi, pi1, q, pi2, m, x);
611  pi2 /= bi;
612 
613  tmp= t1;
614  t1= t0*m - t1*q;
615  t0= tmp;
616  t1 /= bi;
617  pi= pi1;
618  pi1= pi2;
619  if (degree (pi1, x) > 0)
620  {
621  delta= degree (pi, x) - degree (pi1, x);
622  if ((delta + 1) % 2)
623  bi= LC (pi, x)*power (Hi, delta);
624  else
625  bi= -LC (pi, x)*power (Hi, delta);
626  Hi= power (LC (pi1, x), delta)/power (Hi, delta - 1);
627  }
628  }
629  t1 /= gcd (pi1, t1);
630  if (isRat && getCharacteristic() == 0)
631  On (SW_RATIONAL);
632  return t1;
633 }
int degree(const CanonicalForm &f)
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
#define pi
Definition: libparse.cc:1145
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:653
bool fdivides(const CanonicalForm &f, const CanonicalForm &g)
bool fdivides ( const CanonicalForm & f, const CanonicalForm & g )
CFList tmp1
Definition: facFqBivar.cc:72
int j
Definition: facHensel.cc:110

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