My Project  debian-1:4.1.2-p1+ds-2
facAlgFunc.cc
Go to the documentation of this file.
1 /*****************************************************************************\
2  * Computer Algebra System SINGULAR
3 \*****************************************************************************/
4 /** @file facAlgFunc.cc
5  *
6  * This file provides functions to factorize polynomials over alg. function
7  * fields
8  *
9  * @note some of the code is code from libfac or derived from code from libfac.
10  * Libfac is written by M. Messollen. See also COPYING for license information
11  * and README for general information on characteristic sets.
12  *
13  * ABSTRACT: Descriptions can be found in B. Trager "Algebraic Factoring and
14  * Rational Function Integration" and A. Steel "Conquering Inseparability:
15  * Primary decomposition and multivariate factorization over algebraic function
16  * fields of positive characteristic"
17  *
18  * @author Martin Lee
19  *
20  **/
21 /*****************************************************************************/
22 
23 #include "config.h"
24 
25 #include "cf_assert.h"
26 #include "debug.h"
27 
28 #include "cf_generator.h"
29 #include "cf_iter.h"
30 #include "cf_util.h"
31 #include "cf_algorithm.h"
33 #include "cf_map.h"
34 #include "cfModResultant.h"
35 #include "cfCharSets.h"
36 #include "facAlgFunc.h"
37 #include "facAlgFuncUtil.h"
38 
39 void out_cf(const char *s1,const CanonicalForm &f,const char *s2);
40 
42 alg_content (const CanonicalForm& f, const CFList& as)
43 {
44  if (!f.inCoeffDomain())
45  {
46  CFIterator i= f;
47  CanonicalForm result= abs (i.coeff());
48  i++;
49  while (i.hasTerms() && !result.isOne())
50  {
51  result= alg_gcd (i.coeff(), result, as);
52  i++;
53  }
54  return result;
55  }
56 
57  return abs (f);
58 }
59 
61 alg_gcd (const CanonicalForm & fff, const CanonicalForm &ggg, const CFList &as)
62 {
63  if (fff.inCoeffDomain() || ggg.inCoeffDomain())
64  return 1;
65  CanonicalForm f=fff;
66  CanonicalForm g=ggg;
67  f=Prem(f,as);
68  g=Prem(g,as);
69  if ( f.isZero() )
70  {
71  if ( g.lc().sign() < 0 ) return -g;
72  else return g;
73  }
74  else if ( g.isZero() )
75  {
76  if ( f.lc().sign() < 0 ) return -f;
77  else return f;
78  }
79 
80  int v= as.getLast().level();
81  if (f.level() <= v || g.level() <= v)
82  return 1;
83 
85 
86  // does as appear in f and g ?
87  bool has_alg_var=false;
88  for ( CFListIterator j=as;j.hasItem(); j++ )
89  {
90  Variable v=j.getItem().mvar();
91  if (hasVar (f, v))
92  has_alg_var=true;
93  if (hasVar (g, v))
94  has_alg_var=true;
95  }
96  if (!has_alg_var)
97  {
98  /*if ((hasAlgVar(f))
99  || (hasAlgVar(g)))
100  {
101  Varlist ord;
102  for ( CFListIterator j=as;j.hasItem(); j++ )
103  ord.append(j.getItem().mvar());
104  res=algcd(f,g,as,ord);
105  }
106  else*/
107  if (!hasAlgVar (f) && !hasAlgVar (g))
108  return res=gcd(f,g);
109  }
110 
111  int mvf=f.level();
112  int mvg=g.level();
113  if (mvg > mvf)
114  {
115  CanonicalForm tmp=f; f=g; g=tmp;
116  int tmp2=mvf; mvf=mvg; mvg=tmp2;
117  }
118  if (g.inBaseDomain() || f.inBaseDomain())
119  return CanonicalForm(1);
120 
121  CanonicalForm c_f= alg_content (f, as);
122 
123  if (mvf != mvg)
124  {
125  res= alg_gcd (g, c_f, as);
126  return res;
127  }
128  Variable x= f.mvar();
129 
130  // now: mvf==mvg, f.level()==g.level()
131  CanonicalForm c_g= alg_content (g, as);
132 
133  int delta= degree (f) - degree (g);
134 
135  f= divide (f, c_f, as);
136  g= divide (g, c_g, as);
137 
138  // gcd of contents
139  CanonicalForm c_gcd= alg_gcd (c_f, c_g, as);
140  CanonicalForm tmp;
141 
142  if (delta < 0)
143  {
144  tmp= f;
145  f= g;
146  g= tmp;
147  delta= -delta;
148  }
149 
150  CanonicalForm r= 1;
151 
152  while (degree (g, x) > 0)
153  {
154  r= Prem (f, g);
155  r= Prem (r, as);
156  if (!r.isZero())
157  {
158  r= divide (r, alg_content (r,as), as);
159  r /= vcontent (r,Variable (v+1));
160  }
161  f= g;
162  g= r;
163  }
164 
165  if (degree (g, x) == 0)
166  return c_gcd;
167 
168  c_f= alg_content (f, as);
169 
170  f= divide (f, c_f, as);
171 
172  f *= c_gcd;
173  f /= vcontent (f, Variable (v+1));
174 
175  return f;
176 }
177 
178 static CanonicalForm
179 resultante (const CanonicalForm & f, const CanonicalForm& g, const Variable & v)
180 {
181  bool on_rational = isOn(SW_RATIONAL);
182  if (!on_rational && getCharacteristic() == 0)
183  On(SW_RATIONAL);
185  CanonicalForm fz = f * cd;
186  cd = bCommonDen( g );
187  CanonicalForm gz = g * cd;
188  if (!on_rational && getCharacteristic() == 0)
189  Off(SW_RATIONAL);
191 #ifdef HAVE_NTL
192  if (getCharacteristic() == 0)
193  result= resultantZ (fz, gz,v);
194  else
195 #endif
196  result= resultant (fz,gz,v);
197 
198  return result;
199 }
200 
201 /// compute the norm R of f over PPalpha, g= f (x-s*alpha)
202 /// if proof==true, R is squarefree and if in addition getCharacteristic() > 0
203 /// the squarefree factors of R are returned.
204 /// Based on Trager's sqrf_norm algorithm.
205 static CFFList
206 norm (const CanonicalForm & f, const CanonicalForm & PPalpha,
207  CFGenerator & myrandom, CanonicalForm & s, CanonicalForm & g,
208  CanonicalForm & R, bool proof)
209 {
210  Variable y= PPalpha.mvar(), vf= f.mvar();
211  CanonicalForm temp, Palpha= PPalpha, t;
212  int sqfreetest= 0;
213  CFFList testlist;
215 
216  if (proof)
217  {
218  myrandom.reset();
219  s= myrandom.item();
220  g= f;
221  R= CanonicalForm(0);
222  }
223  else
224  {
225  if (getCharacteristic() == 0)
226  t= CanonicalForm (mapinto (myrandom.item()));
227  else
228  t= CanonicalForm (myrandom.item());
229  s= t;
230  g= f (vf - t*Palpha.mvar(), vf);
231  }
232 
233  // Norm, resultante taken with respect to y
234  while (!sqfreetest)
235  {
236  R= resultante (Palpha, g, y);
237  R= R* bCommonDen(R);
238  R /= content (R);
239  if (proof)
240  {
241  // sqfree check ; R is a polynomial in K[x]
242  if (getCharacteristic() == 0)
243  {
244  temp= gcd (R, R.deriv (vf));
245  if (degree(temp,vf) != 0 || temp == temp.genZero())
246  sqfreetest= 0;
247  else
248  sqfreetest= 1;
249  }
250  else
251  {
252  Variable X;
253  testlist= sqrFree (R);
254 
255  if (testlist.getFirst().factor().inCoeffDomain())
256  testlist.removeFirst();
257  sqfreetest= 1;
258  for (i= testlist; i.hasItem(); i++)
259  {
260  if (i.getItem().exp() > 1 && degree (i.getItem().factor(),R.mvar()) > 0)
261  {
262  sqfreetest= 0;
263  break;
264  }
265  }
266  }
267  if (!sqfreetest)
268  {
269  myrandom.next();
270  if (getCharacteristic() == 0)
271  t= CanonicalForm (mapinto (myrandom.item()));
272  else
273  t= CanonicalForm (myrandom.item());
274  s= t;
275  g= f (vf - t*Palpha.mvar(), vf);
276  }
277  }
278  else
279  break;
280  }
281  return testlist;
282 }
283 
284 /// see @a norm, R is guaranteed to be squarefree
285 /// Based on Trager's sqrf_norm algorithm.
286 static CFFList
287 sqrfNorm (const CanonicalForm & f, const CanonicalForm & PPalpha,
288  const Variable & Extension, CanonicalForm & s, CanonicalForm & g,
289  CanonicalForm & R)
290 {
291  CFFList result;
292  if (getCharacteristic() == 0)
293  {
294  IntGenerator myrandom;
295  result= norm (f, PPalpha, myrandom, s, g, R, true);
296  }
297  else if (degree (Extension) > 0)
298  {
299  AlgExtGenerator myrandom (Extension);
300  result= norm (f, PPalpha, myrandom, s, g, R, true);
301  }
302  else
303  {
304  FFGenerator myrandom;
305  result= norm (f, PPalpha, myrandom, s, g, R, true);
306  }
307  return result;
308 }
309 
310 // calculate a "primitive element"
311 // K must have more than S elements (-> getDegOfExt)
312 static CFList
314  const Variable & Extension, bool& isFunctionField,
315  CanonicalForm & R)
316 {
317  CFList Returnlist, Bstar= Astar;
318  CanonicalForm s, g, ra, rb, oldR, h, denra, denrb= 1;
319  Variable alpha;
320  CFList tmp;
321 
322  bool isRat= isOn (SW_RATIONAL);
323 
325  if (Astar.length() == 1)
326  {
327  R= Astar.getFirst();
328  rb= R.mvar();
329  Returnlist.append (rb);
330  if (isFunctionField)
331  Returnlist.append (denrb);
332  }
333  else
334  {
335  R=Bstar.getFirst();
336  Bstar.removeFirst();
337  for (CFListIterator i= Bstar; i.hasItem(); i++)
338  {
339  j= i;
340  j++;
341  if (getCharacteristic() == 0)
342  Off (SW_RATIONAL);
343  R /= icontent (R);
344  if (getCharacteristic() == 0)
345  On (SW_RATIONAL);
346  oldR= R;
347  //TODO normalize i.getItem over K(R)?
348  (void) sqrfNorm (i.getItem(), R, Extension, s, g, R);
349 
350  backSubst.insert (s);
351 
352  if (getCharacteristic() == 0)
353  Off (SW_RATIONAL);
354  R /= icontent (R);
355 
356  if (getCharacteristic() == 0)
357  On (SW_RATIONAL);
358 
359  if (!isFunctionField)
360  {
361  alpha= rootOf (R);
362  h= replacevar (g, g.mvar(), alpha);
363  if (getCharacteristic() == 0)
364  On (SW_RATIONAL); //needed for GCD
365  h= gcd (h, oldR);
366  h /= Lc (h);
367  ra= -h[0];
368  ra= replacevar(ra, alpha, g.mvar());
369  rb= R.mvar()-s*ra;
370  for (; j.hasItem(); j++)
371  {
372  j.getItem()= j.getItem() (rb, i.getItem().mvar());
373  j.getItem()= j.getItem() (ra, oldR.mvar());
374  }
375  prune (alpha);
376  }
377  else
378  {
379  if (getCharacteristic() == 0)
380  On (SW_RATIONAL);
381  Variable v= Variable (tmax (g.level(), oldR.level()) + 1);
382  h= swapvar (g, oldR.mvar(), v);
383  tmp= CFList (R);
384  h= alg_gcd (h, swapvar (oldR, oldR.mvar(), v), tmp);
385 
386  CanonicalForm numinv, deninv;
387  numinv= QuasiInverse (tmp.getFirst(), LC (h), tmp.getFirst().mvar());
388  h *= numinv;
389  h= Prem (h, tmp);
390  deninv= LC(h);
391 
392  ra= -h[0];
393  denra= gcd (ra, deninv);
394  ra /= denra;
395  denra= deninv/denra;
396  rb= R.mvar()*denra-s*ra;
397  denrb= denra;
398  for (; j.hasItem(); j++)
399  {
400  CanonicalForm powdenra= power (denra, degree (j.getItem(),
401  i.getItem().mvar()));
402  j.getItem()= evaluate (j.getItem(), rb, denrb, powdenra,
403  i.getItem().mvar());
404  powdenra= power (denra, degree (j.getItem(), oldR.mvar()));
405  j.getItem()= evaluate (j.getItem(),ra, denra, powdenra, oldR.mvar());
406 
407  }
408  }
409 
410  Returnlist.append (ra);
411  if (isFunctionField)
412  Returnlist.append (denra);
413  Returnlist.append (rb);
414  if (isFunctionField)
415  Returnlist.append (denrb);
416  }
417  }
418 
419  if (isRat && getCharacteristic() == 0)
420  On (SW_RATIONAL);
421  else if (!isRat && getCharacteristic() == 0)
422  Off (SW_RATIONAL);
423 
424  return Returnlist;
425 }
426 
427 /// Trager's algorithm, i.e. convert to one field extension and
428 /// factorize over this field extension
429 static CFFList
430 Trager (const CanonicalForm & F, const CFList & Astar,
431  const Variable & vminpoly, const CFList & as, bool isFunctionField)
432 {
433  bool isRat= isOn (SW_RATIONAL);
434  CFFList L, normFactors, tmp;
435  CFFListIterator iter, iter2;
436  CanonicalForm R, Rstar, s, g, h, f= F;
437  CFList substlist, backSubsts;
438 
439  substlist= simpleExtension (backSubsts, Astar, vminpoly, isFunctionField,
440  Rstar);
441 
442  f= subst (f, Astar, substlist, Rstar, isFunctionField);
443 
444  Variable alpha;
445  if (!isFunctionField)
446  {
447  alpha= rootOf (Rstar);
448  g= replacevar (f, Rstar.mvar(), alpha);
449 
450  if (!isRat && getCharacteristic() == 0)
451  On (SW_RATIONAL);
452  tmp= factorize (g, alpha); // factorization over number field
453 
454  for (iter= tmp; iter.hasItem(); iter++)
455  {
456  h= iter.getItem().factor();
457  if (!h.inCoeffDomain())
458  {
459  h= replacevar (h, alpha, Rstar.mvar());
460  h *= bCommonDen(h);
461  h= backSubst (h, backSubsts, Astar);
462  h= Prem (h, as);
463  L.append (CFFactor (h, iter.getItem().exp()));
464  }
465  }
466  if (!isRat && getCharacteristic() == 0)
467  Off (SW_RATIONAL);
468  prune (alpha);
469  return L;
470  }
471  // after here we are over an extension of a function field
472 
473  // make quasi monic
474  CFList Rstarlist= CFList (Rstar);
475  int algExtLevel= Astar.getLast().level(); //highest level of algebraic variables
476  CanonicalForm numinv;
477  if (!isRat && getCharacteristic() == 0)
478  On (SW_RATIONAL);
479  numinv= QuasiInverse (Rstar, alg_LC (f, algExtLevel), Rstar.mvar());
480 
481  f *= numinv;
482  f= Prem (f, Rstarlist);
483  f /= vcontent (f, Rstar.mvar());
484  // end quasi monic
485 
486  if (degree (f) == 1)
487  {
488  f= backSubst (f, backSubsts, Astar);
489  f *= bCommonDen (f);
490  f= Prem (f, as);
491  f /= vcontent (f, as.getFirst().mvar());
492 
493  return CFFList (CFFactor (f, 1));
494  }
495 
496  CFGenerator * Gen;
497  if (getCharacteristic() == 0)
498  Gen= CFGenFactory::generate();
499  else if (degree (vminpoly) > 0)
500  Gen= AlgExtGenerator (vminpoly).clone();
501  else
502  Gen= CFGenFactory::generate();
503 
504  CFFList LL= CFFList (CFFactor (f, 1));
505 
506  Variable X;
507  do
508  {
509  tmp= CFFList();
510  for (iter= LL; iter.hasItem(); iter++)
511  {
512  f= iter.getItem().factor();
513  (void) norm (f, Rstar, *Gen, s, g, R, false);
514 
515  if (hasFirstAlgVar (R, X))
516  normFactors= factorize (R, X);
517  else
518  normFactors= factorize (R);
519 
520  if (normFactors.getFirst().factor().inCoeffDomain())
521  normFactors.removeFirst();
522  if (normFactors.length() < 1 || (normFactors.length() == 1 && normFactors.getLast().exp() == 1))
523  {
524  f= backSubst (f, backSubsts, Astar);
525  f *= bCommonDen (f);
526  f= Prem (f, as);
527  f /= vcontent (f, as.getFirst().mvar());
528 
529  L.append (CFFactor (f, 1));
530  }
531  else
532  {
533  g= f;
534  int count= 0;
535  for (iter2= normFactors; iter2.hasItem(); iter2++)
536  {
537  CanonicalForm fnew= iter2.getItem().factor();
538  if (fnew.level() <= Rstar.level()) //factor is a constant from the function field
539  continue;
540  else
541  {
542  fnew= fnew (g.mvar() + s*Rstar.mvar(), g.mvar());
543  fnew= Prem (fnew, CFList (Rstar));
544  }
545 
546  h= alg_gcd (g, fnew, Rstarlist);
547  numinv= QuasiInverse (Rstar, alg_LC (h, algExtLevel), Rstar.mvar());
548  h *= numinv;
549  h= Prem (h, Rstarlist);
550  h /= vcontent (h, Rstar.mvar());
551 
552  if (h.level() > Rstar.level())
553  {
554  g= divide (g, h, Rstarlist);
555  if (degree (h) == 1 || iter2.getItem().exp() == 1)
556  {
557  h= backSubst (h, backSubsts, Astar);
558  h= Prem (h, as);
559  h *= bCommonDen (h);
560  h /= vcontent (h, as.getFirst().mvar());
561  L.append (CFFactor (h, 1));
562  }
563  else
564  tmp.append (CFFactor (h, iter2.getItem().exp()));
565  }
566  count++;
567  if (g.level() <= Rstar.level())
568  break;
569  if (count == normFactors.length() - 1)
570  {
571  if (normFactors.getLast().exp() == 1 && g.level() > Rstar.level())
572  {
573  g= backSubst (g, backSubsts, Astar);
574  g= Prem (g, as);
575  g *= bCommonDen (g);
576  g /= vcontent (g, as.getFirst().mvar());
577  L.append (CFFactor (g, 1));
578  }
579  else if (normFactors.getLast().exp() > 1 &&
580  g.level() > Rstar.level())
581  {
582  g /= vcontent (g, Rstar.mvar());
583  tmp.append (CFFactor (g, normFactors.getLast().exp()));
584  }
585  break;
586  }
587  }
588  }
589  }
590  LL= tmp;
591  (*Gen).next();
592  }
593  while (!LL.isEmpty());
594 
595  if (!isRat && getCharacteristic() == 0)
596  Off (SW_RATIONAL);
597 
598  delete Gen;
599 
600  return L;
601 }
602 
603 
604 /// map elements in @a AS into a PIE \f$ L \f$ and record where the variables
605 /// are mapped to in @a varsMapLevel, i.e @a varsMapLevel contains a list of
606 /// pairs of variables \f$ v_i \f$ and integers \f$ e_i \f$ such that
607 /// \f$ L=K(\sqrt[p^{e_1}]{v_1}, \ldots, \sqrt[p^{e_n}]{v_n}) \f$
608 CFList
609 mapIntoPIE (CFFList& varsMapLevel, CanonicalForm& lcmVars, const CFList & AS)
610 {
611  CanonicalForm varsG;
612  int j, exp= 0, tmpExp;
613  bool recurse= false;
614  CFList asnew, as= AS;
615  CFListIterator i= as, ii;
616  CFFList varsGMapLevel, tmp;
618  CFFList * varsGMap= new CFFList [as.length()];
619  for (j= 0; j < as.length(); j++)
620  varsGMap[j]= CFFList();
621  j= 0;
622  while (i.hasItem())
623  {
624  if (i.getItem().deriv() == 0)
625  {
626  deflateDegree (i.getItem(), exp, i.getItem().level());
627  i.getItem()= deflatePoly (i.getItem(), exp, i.getItem().level());
628 
629  varsG= getVars (i.getItem());
630  varsG /= i.getItem().mvar();
631 
632  lcmVars= lcm (varsG, lcmVars);
633 
634  while (!varsG.isOne())
635  {
636  if (i.getItem().deriv (varsG.level()).isZero())
637  {
638  deflateDegree (i.getItem(), tmpExp, varsG.level());
639  if (exp >= tmpExp)
640  {
641  if (exp == tmpExp)
642  i.getItem()= deflatePoly (i.getItem(), exp, varsG.level());
643  else
644  {
645  if (j != 0)
646  recurse= true;
647  i.getItem()= deflatePoly (i.getItem(), tmpExp, varsG.level());
648  }
649  varsGMapLevel.insert (CFFactor (varsG.mvar(), exp - tmpExp));
650  }
651  else
652  {
653  i.getItem()= deflatePoly (i.getItem(), exp, varsG.level());
654  varsGMapLevel.insert (CFFactor (varsG.mvar(), 0));
655  }
656  }
657  else
658  {
659  if (j != 0)
660  recurse= true;
661  varsGMapLevel.insert (CFFactor (varsG.mvar(),exp));
662  }
663  varsG /= varsG.mvar();
664  }
665 
666  if (recurse)
667  {
668  ii= as;
669  for (; ii.hasItem(); ii++)
670  {
671  if (ii.getItem() == i.getItem())
672  continue;
673  for (iter= varsGMapLevel; iter.hasItem(); iter++)
674  ii.getItem()= inflatePoly (ii.getItem(), iter.getItem().exp(),
675  iter.getItem().factor().level());
676  }
677  }
678  else
679  {
680  ii= i;
681  ii++;
682  for (; ii.hasItem(); ii++)
683  {
684  for (iter= varsGMapLevel; iter.hasItem(); iter++)
685  {
686  ii.getItem()= inflatePoly (ii.getItem(), iter.getItem().exp(),
687  iter.getItem().factor().level());
688  }
689  }
690  }
691  if (varsGMap[j].isEmpty())
692  varsGMap[j]= varsGMapLevel;
693  else
694  {
695  if (!varsGMapLevel.isEmpty())
696  {
697  tmp= varsGMap[j];
698  CFFListIterator iter2= varsGMapLevel;
699  ASSERT (tmp.length() == varsGMapLevel.length(),
700  "wrong length of lists");
701  for (iter=tmp; iter.hasItem(); iter++, iter2++)
702  iter.getItem()= CFFactor (iter.getItem().factor(),
703  iter.getItem().exp() + iter2.getItem().exp());
704  varsGMap[j]= tmp;
705  }
706  }
707  varsGMapLevel= CFFList();
708  }
709  asnew.append (i.getItem());
710  if (!recurse)
711  {
712  i++;
713  j++;
714  }
715  else
716  {
717  i= as;
718  j= 0;
719  recurse= false;
720  asnew= CFList();
721  }
722  }
723 
724  while (!lcmVars.isOne())
725  {
726  varsMapLevel.insert (CFFactor (lcmVars.mvar(), 0));
727  lcmVars /= lcmVars.mvar();
728  }
729 
730  for (j= 0; j < as.length(); j++)
731  {
732  if (varsGMap[j].isEmpty())
733  continue;
734 
735  for (CFFListIterator iter2= varsGMap[j]; iter2.hasItem(); iter2++)
736  {
737  for (iter= varsMapLevel; iter.hasItem(); iter++)
738  {
739  if (iter.getItem().factor() == iter2.getItem().factor())
740  {
741  iter.getItem()= CFFactor (iter.getItem().factor(),
742  iter.getItem().exp() + iter2.getItem().exp());
743  }
744  }
745  }
746  }
747 
748  delete [] varsGMap;
749 
750  return asnew;
751 }
752 
753 /// algorithm of A. Steel described in "Conquering Inseparability: Primary
754 /// decomposition and multivariate factorization over algebraic function fields
755 /// of positive characteristic" with the following modifications: we use
756 /// characteristic sets in IdealOverSubfield and Trager's primitive element
757 /// algorithm instead of FGLM
758 CFFList
759 SteelTrager (const CanonicalForm & f, const CFList & AS)
760 {
761  CanonicalForm F= f, lcmVars= 1;
762  CFList asnew, as= AS;
763  CFListIterator i, ii;
764 
765  bool derivZeroF= false;
766  int j, expF= 0, tmpExp;
767  CFFList varsMapLevel, tmp;
769 
770  // check if F is separable
771  if (F.deriv().isZero())
772  {
773  derivZeroF= true;
774  deflateDegree (F, expF, F.level());
775  }
776 
777  CanonicalForm varsF= getVars (F);
778  varsF /= F.mvar();
779 
780  lcmVars= lcm (varsF, lcmVars);
781 
782  if (derivZeroF)
783  as.append (F);
784 
785  asnew= mapIntoPIE (varsMapLevel, lcmVars, as);
786 
787  if (derivZeroF)
788  {
789  asnew.removeLast();
790  F= deflatePoly (F, expF, F.level());
791  }
792 
793  // map variables in F
794  for (iter= varsMapLevel; iter.hasItem(); iter++)
795  {
796  if (expF > 0)
797  tmpExp= iter.getItem().exp() - expF;
798  else
799  tmpExp= iter.getItem().exp();
800 
801  if (tmpExp > 0)
802  F= inflatePoly (F, tmpExp, iter.getItem().factor().level());
803  else if (tmpExp < 0)
804  F= deflatePoly (F, -tmpExp, iter.getItem().factor().level());
805  }
806 
807  // factor F with minimal polys given in asnew
808  asnew.append (F);
809  asnew= charSetViaModCharSet (asnew, false);
810 
811  F= asnew.getLast();
812  F /= content (F);
813 
814  asnew.removeLast();
815  for (i= asnew; i.hasItem(); i++)
816  i.getItem() /= content (i.getItem());
817 
818  tmp= facAlgFunc (F, asnew);
819 
820  // transform back
821  j= 0;
822  int p= getCharacteristic();
823  CFList transBack;
824  CFMap M;
826 
827  for (iter= varsMapLevel; iter.hasItem(); iter++)
828  {
829  if (iter.getItem().exp() > 0)
830  {
831  j++;
832  g= power (Variable (f.level() + j), ipower (p, iter.getItem().exp())) -
833  iter.getItem().factor().mvar();
834  transBack.append (g);
835  M.newpair (iter.getItem().factor().mvar(), Variable (f.level() + j));
836  }
837  }
838 
839  for (i= asnew; i.hasItem(); i++)
840  transBack.insert (M (i.getItem()));
841 
842  if (expF > 0)
843  tmpExp= ipower (p, expF);
844 
845  CFFList result;
846  CFList transform;
847 
848  bool found;
849  for (iter= tmp; iter.hasItem(); iter++)
850  {
851  found= false;
852  transform= transBack;
853  CanonicalForm factor= iter.getItem().factor();
854  factor= M (factor);
855  transform.append (factor);
856  transform= modCharSet (transform, false);
857 
858 retry:
859  if (transform.isEmpty())
860  {
861  transform= transBack;
862  transform.append (factor);
863  transform= charSetViaCharSetN (transform);
864  }
865  for (i= transform; i.hasItem(); i++)
866  {
867  if (degree (i.getItem(), f.mvar()) > 0)
868  {
869  if (i.getItem().level() > f.level())
870  break;
871  found= true;
872  factor= i.getItem();
873  break;
874  }
875  }
876 
877  if (!found)
878  {
879  found= false;
880  transform= CFList();
881  goto retry;
882  }
883 
884  factor /= content (factor);
885 
886  if (expF > 0)
887  {
888  int mult= tmpExp/(degree (factor)/degree (iter.getItem().factor()));
889  result.append (CFFactor (factor, iter.getItem().exp()*mult));
890  }
891  else
892  result.append (CFFactor (factor, iter.getItem().exp()));
893  }
894 
895  return result;
896 }
897 
898 /// factorize a polynomial that is irreducible over the ground field modulo an
899 /// extension given by an irreducible characteristic set
900 
901 // 1) prepares data
902 // 2) for char=p we distinguish 3 cases:
903 // no transcendentals, separable and inseparable extensions
904 CFFList
905 facAlgFunc2 (const CanonicalForm & f, const CFList & as)
906 {
907  bool isRat= isOn (SW_RATIONAL);
908  if (!isRat && getCharacteristic() == 0)
909  On (SW_RATIONAL);
910  Variable vf=f.mvar();
912  CFFListIterator jj;
913  CFList reduceresult;
914  CFFList result;
915 
916 // F1: [Test trivial cases]
917 // 1) first trivial cases:
918  if (vf.level() <= as.getLast().level())
919  {
920  if (!isRat && getCharacteristic() == 0)
921  Off (SW_RATIONAL);
922  return CFFList(CFFactor(f,1));
923  }
924 
925 // 2) Setup list of those polys in AS having degree > 1
926  CFList Astar;
927  Variable x;
928  CanonicalForm elem;
929  Varlist ord, uord;
930  for (int ii= 1; ii < level (vf); ii++)
931  uord.append (Variable (ii));
932 
933  for (i= as; i.hasItem(); i++)
934  {
935  elem= i.getItem();
936  x= elem.mvar();
937  if (degree (elem, x) > 1) // otherwise it's not an extension
938  {
939  Astar.append (elem);
940  ord.append (x);
941  }
942  }
943  uord= Difference (uord, ord);
944 
945 // 3) second trivial cases: we already proved irr. of f over no extensions
946  if (Astar.length() == 0)
947  {
948  if (!isRat && getCharacteristic() == 0)
949  Off (SW_RATIONAL);
950  return CFFList (CFFactor (f, 1));
951  }
952 
953 // 4) Look if elements in uord actually occur in any of the minimal
954 // polynomials. If no element of uord occures in any of the minimal
955 // polynomials the field is an alg. number field not an alg. function field
956  Varlist newuord= varsInAs (uord, Astar);
957 
958  CFFList Factorlist;
959  Varlist gcdord= Union (ord, newuord);
960  gcdord.append (f.mvar());
961  bool isFunctionField= (newuord.length() > 0);
962 
963  // TODO alg_sqrfree?
964  CanonicalForm Fgcd= 0;
965  if (isFunctionField)
966  Fgcd= alg_gcd (f, f.deriv(), Astar);
967 
968  bool derivZero= f.deriv().isZero();
969  if (isFunctionField && (degree (Fgcd, f.mvar()) > 0) && !derivZero)
970  {
971  CanonicalForm Ggcd= divide(f, Fgcd,Astar);
972  if (getCharacteristic() == 0)
973  {
974  CFFList result= facAlgFunc2 (Ggcd, as); //Ggcd is the squarefree part of f
975  multiplicity (result, f, Astar);
976  if (!isRat && getCharacteristic() == 0)
977  Off (SW_RATIONAL);
978  return result;
979  }
980 
981  Fgcd= pp (Fgcd);
982  Ggcd= pp (Ggcd);
983  if (!isRat && getCharacteristic() == 0)
984  Off (SW_RATIONAL);
985  return merge (facAlgFunc2 (Fgcd, as), facAlgFunc2 (Ggcd, as));
986  }
987 
988  if (getCharacteristic() > 0)
989  {
990  IntList degreelist;
991  Variable vminpoly;
992  for (i= Astar; i.hasItem(); i++)
993  degreelist.append (degree (i.getItem()));
994 
995  int extdeg= getDegOfExt (degreelist, degree (f));
996 
997  if (newuord.length() == 0) // no parameters
998  {
999  if (extdeg > 1)
1000  {
1001  CanonicalForm MIPO= generateMipo (extdeg);
1002  vminpoly= rootOf(MIPO);
1003  }
1004  Factorlist= Trager(f, Astar, vminpoly, as, isFunctionField);
1005  if (extdeg > 1)
1006  prune (vminpoly);
1007  return Factorlist;
1008  }
1009  else if (isInseparable(Astar) || derivZero) // inseparable case
1010  {
1011  Factorlist= SteelTrager (f, Astar);
1012  return Factorlist;
1013  }
1014  else // separable case
1015  {
1016  if (extdeg > 1)
1017  {
1018  CanonicalForm MIPO=generateMipo (extdeg);
1019  vminpoly= rootOf (MIPO);
1020  }
1021  Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
1022  if (extdeg > 1)
1023  prune (vminpoly);
1024  return Factorlist;
1025  }
1026  }
1027  else // char 0
1028  {
1029  Variable vminpoly;
1030  Factorlist= Trager (f, Astar, vminpoly, as, isFunctionField);
1031  if (!isRat && getCharacteristic() == 0)
1032  Off (SW_RATIONAL);
1033  return Factorlist;
1034  }
1035 
1036  return CFFList (CFFactor(f,1));
1037 }
1038 
1039 
1040 /// factorize a polynomial modulo an extension given by an irreducible
1041 /// characteristic set
1042 CFFList
1043 facAlgFunc (const CanonicalForm & f, const CFList & as)
1044 {
1045  bool isRat= isOn (SW_RATIONAL);
1046  if (!isRat && getCharacteristic() == 0)
1047  On (SW_RATIONAL);
1048  CFFList Output, output, Factors= factorize(f);
1049  if (Factors.getFirst().factor().inCoeffDomain())
1050  Factors.removeFirst();
1051 
1052  if (as.length() == 0)
1053  {
1054  if (!isRat && getCharacteristic() == 0)
1055  Off (SW_RATIONAL);
1056  return Factors;
1057  }
1058  if (f.level() <= as.getLast().level())
1059  {
1060  if (!isRat && getCharacteristic() == 0)
1061  Off (SW_RATIONAL);
1062  return Factors;
1063  }
1064 
1065  for (CFFListIterator i=Factors; i.hasItem(); i++)
1066  {
1067  if (i.getItem().factor().level() > as.getLast().level())
1068  {
1069  output= facAlgFunc2 (i.getItem().factor(), as);
1070  for (CFFListIterator j= output; j.hasItem(); j++)
1071  Output= append (Output, CFFactor (j.getItem().factor(),
1072  j.getItem().exp()*i.getItem().exp()));
1073  }
1074  }
1075 
1076  if (!isRat && getCharacteristic() == 0)
1077  Off (SW_RATIONAL);
1078  return Output;
1079 }
Rational abs(const Rational &a)
Definition: GMPrat.cc:436
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm mapinto(const CanonicalForm &f)
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:71
int getCharacteristic()
Definition: cf_char.cc:51
int degree(const CanonicalForm &f)
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:225
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:248
List< CFFactor > CFFList
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
Factor< CanonicalForm > CFFactor
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:175
int level(const CanonicalForm &f)
List< CanonicalForm > CFList
CanonicalForm LC(const CanonicalForm &f)
CanonicalForm replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition: cf_ops.cc:271
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
Definition: cfCharSets.cc:246
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents)
characteristic set via modified medial set
Definition: cfCharSets.cc:356
CFList modCharSet(const CFList &L, StoreFactors &StoredFactors, bool removeContents)
modified medial set
Definition: cfCharSets.cc:284
This file provides functions to compute characteristic sets.
int i
Definition: cfEzgcd.cc:125
Variable x
Definition: cfModGcd.cc:4023
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
Definition: cfModGcd.cc:1972
int p
Definition: cfModGcd.cc:4019
g
Definition: cfModGcd.cc:4031
CanonicalForm cd(bCommonDen(FF))
Definition: cfModGcd.cc:4030
CanonicalForm resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Z
modular resultant algorithm as described by G.
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
declarations of higher level algorithms.
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:757
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
assertions for Factory
#define ASSERT(expression, message)
Definition: cf_assert.h:99
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:29
generate integers, elements of finite fields
Iterators for CanonicalForm's.
map polynomials
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:26
FILE * f
Definition: checklibs.c:9
generate all elements in F_p(alpha) starting from 0
Definition: cf_generator.h:94
CFGenerator * clone() const
static CFGenerator * generate()
virtual class for generators
Definition: cf_generator.h:22
virtual CanonicalForm item() const
Definition: cf_generator.h:28
virtual void next()
Definition: cf_generator.h:29
virtual void reset()
Definition: cf_generator.h:27
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
class CFMap
Definition: cf_map.h:85
factory's main class
Definition: canonicalform.h:83
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
CanonicalForm genZero() const
genOne(), genZero()
CanonicalForm deriv() const
deriv() - return the formal derivation of CO.
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
generate all elements in F_p starting from 0
Definition: cf_generator.h:56
generate integers starting from 0
Definition: cf_generator.h:37
T & getItem() const
Definition: ftmpl_list.cc:431
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
int length() const
Definition: ftmpl_list.cc:273
void append(const T &)
Definition: ftmpl_list.cc:256
T getLast() const
Definition: ftmpl_list.cc:309
void insert(const T &)
Definition: ftmpl_list.cc:193
int isEmpty() const
Definition: ftmpl_list.cc:267
void removeLast()
Definition: ftmpl_list.cc:317
factory's class for variables
Definition: factory.h:118
int level() const
Definition: factory.h:134
functions to print debug output
CFFListIterator iter
Definition: facAbsBiFact.cc:54
Variable alpha
Definition: facAbsBiFact.cc:52
return result
Definition: facAbsBiFact.cc:76
const CanonicalForm int s
Definition: facAbsFact.cc:55
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
CanonicalForm res
Definition: facAbsFact.cc:64
CanonicalForm factor
Definition: facAbsFact.cc:101
Varlist varsInAs(const Varlist &uord, const CFList &Astar)
void deflateDegree(const CanonicalForm &F, int &pExp, int n)
CanonicalForm alg_LC(const CanonicalForm &f, int lev)
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
int hasVar(const CanonicalForm &f, const Variable &v)
CanonicalForm inflatePoly(const CanonicalForm &F, int exp)
int hasAlgVar(const CanonicalForm &f, const Variable &v)
int getDegOfExt(IntList &degreelist, int n)
bool isInseparable(const CFList &Astar)
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
CanonicalForm backSubst(const CanonicalForm &F, const CFList &a, const CFList &b)
CanonicalForm QuasiInverse(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
CanonicalForm generateMipo(int degOfExt)
CanonicalForm deflatePoly(const CanonicalForm &F, int exp)
Utility functions for factorization over algebraic function fields.
static CFFList sqrfNorm(const CanonicalForm &f, const CanonicalForm &PPalpha, const Variable &Extension, CanonicalForm &s, CanonicalForm &g, CanonicalForm &R)
see norm, R is guaranteed to be squarefree Based on Trager's sqrf_norm algorithm.
Definition: facAlgFunc.cc:287
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
Definition: facAlgFunc.cc:42
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
Definition: facAlgFunc.cc:61
CFFList SteelTrager(const CanonicalForm &f, const CFList &AS)
algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate...
Definition: facAlgFunc.cc:759
static CFFList norm(const CanonicalForm &f, const CanonicalForm &PPalpha, CFGenerator &myrandom, CanonicalForm &s, CanonicalForm &g, CanonicalForm &R, bool proof)
compute the norm R of f over PPalpha, g= f (x-s*alpha) if proof==true, R is squarefree and if in addi...
Definition: facAlgFunc.cc:206
static CFFList Trager(const CanonicalForm &F, const CFList &Astar, const Variable &vminpoly, const CFList &as, bool isFunctionField)
Trager's algorithm, i.e. convert to one field extension and factorize over this field extension.
Definition: facAlgFunc.cc:430
static CFList simpleExtension(CFList &backSubst, const CFList &Astar, const Variable &Extension, bool &isFunctionField, CanonicalForm &R)
Definition: facAlgFunc.cc:313
CFList mapIntoPIE(CFFList &varsMapLevel, CanonicalForm &lcmVars, const CFList &AS)
map elements in AS into a PIE and record where the variables are mapped to in varsMapLevel,...
Definition: facAlgFunc.cc:609
CFFList facAlgFunc(const CanonicalForm &f, const CFList &as)
factorize a polynomial modulo an extension given by an irreducible characteristic set
Definition: facAlgFunc.cc:1043
CFFList facAlgFunc2(const CanonicalForm &f, const CFList &as)
factorize a polynomial that is irreducible over the ground field modulo an extension given by an irre...
Definition: facAlgFunc.cc:905
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
Definition: cf_factor.cc:90
static CanonicalForm resultante(const CanonicalForm &f, const CanonicalForm &g, const Variable &v)
Definition: facAlgFunc.cc:179
Factorization over algebraic function fields.
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
bool found
Definition: facFactorize.cc:56
CFList tmp2
Definition: facFqBivar.cc:70
int j
Definition: facHensel.cc:105
Variable rootOf(const CanonicalForm &, char name='@')
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162
void prune(Variable &alpha)
Definition: variable.cc:261
some useful template functions.
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
STATIC_VAR int * multiplicity
STATIC_VAR Poly * h
Definition: janet.cc:971
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:647
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
int status int void size_t count
Definition: si_signals.h:59
#define R
Definition: sirandom.c:27
#define M
Definition: sirandom.c:25
int gcd(int a, int b)
Definition: walkSupport.cc:836