My Project
Loading...
Searching...
No Matches
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;
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();
186 for (CFListIterator iter= a; iter.hasItem(); iter++)
187 {
188 result= result (tmp+iter.getItem()*tmp2.getLast().mvar(), tmp);
189 tmp= tmp2.getLast().mvar();
191 }
192 return result;
193}
CanonicalForm b
Definition: cfModGcd.cc:4103
#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: variable.h:33
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:4078
g
Definition: cfModGcd.cc:4090
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)
505 q= ff/f;
506 if (!isRat && getCharacteristic() == 0)
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:31
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:4082
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)
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}
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
int degree(const CanonicalForm &f)
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");
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 FACTORY_PUBLIC 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}