My Project  debian-1:4.1.1-p2+ds-4
Functions
facAlgFunc.cc File Reference
#include "config.h"
#include "cf_assert.h"
#include "debug.h"
#include "cf_generator.h"
#include "cf_iter.h"
#include "cf_util.h"
#include "cf_algorithm.h"
#include "templates/ftmpl_functions.h"
#include "cf_map.h"
#include "cfModResultant.h"
#include "cfCharSets.h"
#include "facAlgFunc.h"
#include "facAlgFuncUtil.h"

Go to the source code of this file.

Functions

void out_cf (const char *s1, const CanonicalForm &f, const char *s2)
 cf_algorithm.cc - simple mathematical algorithms. More...
 
CanonicalForm alg_content (const CanonicalForm &f, const CFList &as)
 
CanonicalForm alg_gcd (const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
 
static CanonicalForm resultante (const CanonicalForm &f, const CanonicalForm &g, const Variable &v)
 
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 addition getCharacteristic() > 0 the squarefree factors of R are returned. Based on Trager's sqrf_norm algorithm. More...
 
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. More...
 
static CFList simpleExtension (CFList &backSubst, const CFList &Astar, const Variable &Extension, bool &isFunctionField, CanonicalForm &R)
 
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. More...
 
CFList mapIntoPIE (CFFList &varsMapLevel, CanonicalForm &lcmVars, const CFList &AS)
 map elements in AS into a PIE $ L $ and record where the variables are mapped to in varsMapLevel, i.e varsMapLevel contains a list of pairs of variables $ v_i $ and integers $ e_i $ such that $ L=K(\sqrt[p^{e_1}]{v_1}, \ldots, \sqrt[p^{e_n}]{v_n}) $ More...
 
CFFList SteelTrager (const CanonicalForm &f, const CFList &AS)
 algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic" with the following modifications: we use characteristic sets in IdealOverSubfield and Trager's primitive element algorithm instead of FGLM More...
 
CFFList facAlgFunc2 (const CanonicalForm &f, const CFList &as)
 factorize a polynomial that is irreducible over the ground field modulo an extension given by an irreducible characteristic set More...
 
CFFList facAlgFunc (const CanonicalForm &f, const CFList &as)
 factorize a polynomial modulo an extension given by an irreducible characteristic set More...
 

Detailed Description

This file provides 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.

ABSTRACT: Descriptions can be found in B. Trager "Algebraic Factoring and Rational Function Integration" and A. Steel "Conquering Inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic"

Author
Martin Lee

Definition in file facAlgFunc.cc.

Function Documentation

◆ alg_content()

CanonicalForm alg_content ( const CanonicalForm f,
const CFList as 
)

Definition at line 42 of file facAlgFunc.cc.

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 }

◆ alg_gcd()

CanonicalForm alg_gcd ( const CanonicalForm fff,
const CanonicalForm ggg,
const CFList as 
)

Definition at line 61 of file facAlgFunc.cc.

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 }

◆ facAlgFunc()

CFFList facAlgFunc ( const CanonicalForm f,
const CFList as 
)

factorize a polynomial modulo an extension given by an irreducible characteristic set

factorize a polynomial f modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $.

Parameters
[in]funivariate poly
[in]asirreducible characteristic set

Definition at line 1043 of file facAlgFunc.cc.

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 }

◆ facAlgFunc2()

CFFList facAlgFunc2 ( const CanonicalForm f,
const CFList as 
)

factorize a polynomial that is irreducible over the ground field modulo an extension given by an irreducible characteristic set

factorize a polynomial f that is irreducible over the ground field modulo an extension given by an irreducible characteristic set as, f is assumed to be integral, i.e. $ f\in K[x_1,\ldots,x_n]/(as) $, and each element of as is assumed to be integral as well. $ K $ must be either $ F_p $ or $ Q $.

Parameters
[in]funivariate poly
[in]asirreducible characteristic set

Definition at line 905 of file facAlgFunc.cc.

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 }

◆ mapIntoPIE()

CFList mapIntoPIE ( CFFList varsMapLevel,
CanonicalForm lcmVars,
const CFList AS 
)

map elements in AS into a PIE $ L $ and record where the variables are mapped to in varsMapLevel, i.e varsMapLevel contains a list of pairs of variables $ v_i $ and integers $ e_i $ such that $ L=K(\sqrt[p^{e_1}]{v_1}, \ldots, \sqrt[p^{e_n}]{v_n}) $

Definition at line 609 of file facAlgFunc.cc.

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 }

◆ norm()

static CFFList norm ( const CanonicalForm f,
const CanonicalForm PPalpha,
CFGenerator myrandom,
CanonicalForm s,
CanonicalForm g,
CanonicalForm R,
bool  proof 
)
static

compute the norm R of f over PPalpha, g= f (x-s*alpha) if proof==true, R is squarefree and if in addition getCharacteristic() > 0 the squarefree factors of R are returned. Based on Trager's sqrf_norm algorithm.

Definition at line 206 of file facAlgFunc.cc.

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 }

◆ out_cf()

void out_cf ( const char *  s1,
const CanonicalForm f,
const char *  s2 
)

cf_algorithm.cc - simple mathematical algorithms.

Hierarchy: mathematical algorithms on canonical forms

Developers note:

A "mathematical" algorithm is an algorithm which calculates some mathematical function in contrast to a "structural" algorithm which gives structural information on polynomials.

Compare these functions to the functions in ‘cf_ops.cc’, which are structural algorithms.

Definition at line 90 of file cf_factor.cc.

91 {
92  printf("%s",s1);
93  if (f.isZero()) printf("+0");
94  //else if (! f.inCoeffDomain() )
95  else if (! f.inBaseDomain() )
96  {
97  int l = f.level();
98  for ( CFIterator i = f; i.hasTerms(); i++ )
99  {
100  int e=i.exp();
101  if (i.coeff().isOne())
102  {
103  printf("+");
104  if (e==0) printf("1");
105  else
106  {
107  printf("v(%d)",l);
108  if (e!=1) printf("^%d",e);
109  }
110  }
111  else
112  {
113  out_cf("+(",i.coeff(),")");
114  if (e!=0)
115  {
116  printf("*v(%d)",l);
117  if (e!=1) printf("^%d",e);
118  }
119  }
120  }
121  }
122  else
123  {
124  if ( f.isImm() )
125  {
127  {
128  long a= imm2int (f.getval());
129  if ( a == gf_q )
130  printf ("+%ld", a);
131  else if ( a == 0L )
132  printf ("+1");
133  else if ( a == 1L )
134  printf ("+%c",gf_name);
135  else
136  {
137  printf ("+%c",gf_name);
138  printf ("^%ld",a);
139  }
140  }
141  else
142  printf("+%ld",f.intval());
143  }
144  else
145  {
146  #ifdef NOSTREAMIO
147  if (f.inZ())
148  {
149  mpz_t m;
150  gmp_numerator(f,m);
151  char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
152  str = mpz_get_str( str, 10, m );
153  puts(str);
154  delete[] str;
155  mpz_clear(m);
156  }
157  else if (f.inQ())
158  {
159  mpz_t m;
160  gmp_numerator(f,m);
161  char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
162  str = mpz_get_str( str, 10, m );
163  puts(str);putchar('/');
164  delete[] str;
165  mpz_clear(m);
167  str = new char[mpz_sizeinbase( m, 10 ) + 2];
168  str = mpz_get_str( str, 10, m );
169  puts(str);
170  delete[] str;
171  mpz_clear(m);
172  }
173  #else
174  std::cout << f;
175  #endif
176  }
177  //if (f.inZ()) printf("(Z)");
178  //else if (f.inQ()) printf("(Q)");
179  //else if (f.inFF()) printf("(FF)");
180  //else if (f.inPP()) printf("(PP)");
181  //else if (f.inGF()) printf("(PP)");
182  //else
183  if (f.inExtension()) printf("E(%d)",f.level());
184  }
185  printf("%s",s2);
186 }

◆ resultante()

static CanonicalForm resultante ( const CanonicalForm f,
const CanonicalForm g,
const Variable v 
)
static

Definition at line 179 of file facAlgFunc.cc.

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 }

◆ simpleExtension()

static CFList simpleExtension ( CFList backSubst,
const CFList Astar,
const Variable Extension,
bool &  isFunctionField,
CanonicalForm R 
)
static

Definition at line 313 of file facAlgFunc.cc.

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 }

◆ sqrfNorm()

static CFFList sqrfNorm ( const CanonicalForm f,
const CanonicalForm PPalpha,
const Variable Extension,
CanonicalForm s,
CanonicalForm g,
CanonicalForm R 
)
static

see norm, R is guaranteed to be squarefree Based on Trager's sqrf_norm algorithm.

Definition at line 287 of file facAlgFunc.cc.

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 }

◆ SteelTrager()

CFFList SteelTrager ( const CanonicalForm f,
const CFList AS 
)

algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate factorization over algebraic function fields of positive characteristic" with the following modifications: we use characteristic sets in IdealOverSubfield and Trager's primitive element algorithm instead of FGLM

Definition at line 759 of file facAlgFunc.cc.

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 }

◆ Trager()

static CFFList Trager ( const CanonicalForm F,
const CFList Astar,
const Variable vminpoly,
const CFList as,
bool  isFunctionField 
)
static

Trager's algorithm, i.e. convert to one field extension and factorize over this field extension.

Definition at line 430 of file facAlgFunc.cc.

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 }
evaluate
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
Definition: cfModGcd.cc:1972
SW_RATIONAL
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:28
isOn
bool isOn(int sw)
switches
Definition: canonicalform.cc:1912
isZero
bool isZero(const CFArray &A)
checks if entries of A are zero
Definition: facSparseHensel.h:468
j
int j
Definition: facHensel.cc:105
f
FILE * f
Definition: checklibs.c:9
IntGenerator
generate integers starting from 0
Definition: cf_generator.h:36
icontent
CanonicalForm icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:71
CFIterator
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
x
Variable x
Definition: cfModGcd.cc:4023
Prem
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
Definition: cfCharSetsUtil.cc:616
y
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:57
result
return result
Definition: facAbsBiFact.cc:76
isInseparable
bool isInseparable(const CFList &Astar)
Definition: facAlgFuncUtil.cc:522
resultantZ
CanonicalForm resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Z
Definition: cfModResultant.cc:560
CFFactory::gettype
static int gettype()
Definition: cf_factory.h:28
varsInAs
Varlist varsInAs(const Varlist &uord, const CFList &Astar)
Definition: facAlgFuncUtil.cc:66
CFMap
class CFMap
Definition: cf_map.h:84
CFFList
List< CFFactor > CFFList
Definition: canonicalform.h:386
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition: canonicalform.cc:1837
vcontent
CanonicalForm vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:230
modCharSet
CFList modCharSet(const CFList &L, StoreFactors &StoredFactors, bool removeContents)
modified medial set
Definition: cfCharSets.cc:284
g
g
Definition: cfModGcd.cc:4031
level
int level(const CanonicalForm &f)
Definition: canonicalform.h:324
rootOf
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
alg_gcd
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
Definition: facAlgFunc.cc:61
charSetViaCharSetN
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
Definition: cfCharSets.cc:246
iter
CFFListIterator iter
Definition: facAbsBiFact.cc:54
CFGenerator
virtual class for generators
Definition: cf_generator.h:21
gf_name
char gf_name
Definition: gfops.cc:52
getCharacteristic
int getCharacteristic()
Definition: cf_char.cc:51
CxxTest::delta
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
Trager
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
norm
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
CanonicalForm
factory's main class
Definition: canonicalform.h:77
found
bool found
Definition: facFactorize.cc:56
CanonicalForm::isOne
CF_NO_INLINE bool isOne() const
CF_INLINE bool CanonicalForm::isOne, isZero () const.
Definition: cf_inline.cc:354
GaloisFieldDomain
#define GaloisFieldDomain
Definition: cf_defs.h:22
i
int i
Definition: cfEzgcd.cc:125
Lc
CanonicalForm Lc(const CanonicalForm &f)
Definition: canonicalform.h:300
swapvar
CanonicalForm swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
out_cf
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
Definition: cf_factor.cc:90
res
CanonicalForm res
Definition: facAbsFact.cc:64
hasFirstAlgVar
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:665
ASSERT
#define ASSERT(expression, message)
Definition: cf_assert.h:99
Difference
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
abs
Rational abs(const Rational &a)
Definition: GMPrat.cc:439
M
#define M
Definition: sirandom.c:24
content
CanonicalForm content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:180
cd
CanonicalForm cd(bCommonDen(FF))
Definition: cfModGcd.cc:4030
getVars
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
alpha
Variable alpha
Definition: facAbsBiFact.cc:52
List::isEmpty
int isEmpty() const
Definition: ftmpl_list.cc:267
CanonicalForm::deriv
CanonicalForm deriv() const
deriv() - return the formal derivation of CO.
Definition: canonicalform.cc:1235
h
static Poly * h
Definition: janet.cc:972
FFGenerator
generate all elements in F_p starting from 0
Definition: cf_generator.h:55
prune
void prune(Variable &alpha)
Definition: variable.cc:261
QuasiInverse
CanonicalForm QuasiInverse(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
Definition: facAlgFuncUtil.cc:582
gf_q
int gf_q
Definition: gfops.cc:47
Variable::level
int level() const
Definition: factory.h:134
pp
CanonicalForm pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:253
append
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
Definition: facAlgFuncUtil.cc:32
factorize
CFFList factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:390
deflateDegree
void deflateDegree(const CanonicalForm &F, int &pExp, int n)
Definition: facAlgFuncUtil.cc:195
ipower
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:25
ListIterator::hasItem
int hasItem()
Definition: ftmpl_list.cc:439
Off
void Off(int sw)
switches
Definition: canonicalform.cc:1905
List::removeFirst
void removeFirst()
Definition: ftmpl_list.cc:287
List::getFirst
T getFirst() const
Definition: ftmpl_list.cc:279
exp
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357
Factor
Definition: ftmpl_factor.h:18
tmax
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
resultante
static CanonicalForm resultante(const CanonicalForm &f, const CanonicalForm &g, const Variable &v)
Definition: facAlgFunc.cc:179
SteelTrager
CFFList SteelTrager(const CanonicalForm &f, const CFList &AS)
algorithm of A. Steel described in "Conquering Inseparability: Primary decomposition and multivariate...
Definition: facAlgFunc.cc:759
bCommonDen
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
Definition: cf_algorithm.cc:293
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition: canonicalform.cc:119
inflatePoly
CanonicalForm inflatePoly(const CanonicalForm &F, int exp)
Definition: facAlgFuncUtil.cc:266
divide
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
Definition: facAlgFuncUtil.cc:500
List::length
int length() const
Definition: ftmpl_list.cc:273
factor
CanonicalForm factor
Definition: facAbsFact.cc:101
backSubst
CanonicalForm backSubst(const CanonicalForm &F, const CFList &a, const CFList &b)
Definition: facAlgFuncUtil.cc:178
List::removeLast
void removeLast()
Definition: ftmpl_list.cc:317
CanonicalForm::genZero
CanonicalForm genZero() const
genOne(), genZero()
Definition: canonicalform.cc:1808
imm2int
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
Variable
factory's class for variables
Definition: factory.h:117
ListIterator::getItem
T & getItem() const
Definition: ftmpl_list.cc:431
mult
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:647
CanonicalForm::mvar
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
Definition: canonicalform.cc:560
LC
CanonicalForm LC(const CanonicalForm &f)
Definition: canonicalform.h:303
mapinto
CanonicalForm mapinto(const CanonicalForm &f)
Definition: canonicalform.h:348
charSetViaModCharSet
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents)
characteristic set via modified medial set
Definition: cfCharSets.cc:356
getDegOfExt
int getDegOfExt(IntList &degreelist, int n)
Definition: facAlgFuncUtil.cc:543
facAlgFunc2
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
resultant
CanonicalForm resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )
Definition: cf_resultant.cc:173
m
int m
Definition: cfEzgcd.cc:121
sqrFree
CFFList sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:757
l
int l
Definition: cfEzgcd.cc:93
lcm
int lcm(unsigned long *l, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:709
deflatePoly
CanonicalForm deflatePoly(const CanonicalForm &F, int exp)
Definition: facAlgFuncUtil.cc:238
hasAlgVar
int hasAlgVar(const CanonicalForm &f, const Variable &v)
Definition: facAlgFuncUtil.cc:322
R
#define R
Definition: sirandom.c:26
gmp_denominator
void gmp_denominator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:40
CFGenerator::reset
virtual void reset()
Definition: cf_generator.h:27
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
gmp_numerator
void gmp_numerator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:20
gcd
int gcd(int a, int b)
Definition: walkSupport.cc:836
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:37
simpleExtension
static CFList simpleExtension(CFList &backSubst, const CFList &Astar, const Variable &Extension, bool &isFunctionField, CanonicalForm &R)
Definition: facAlgFunc.cc:313
CFGenerator::next
virtual void next()
Definition: cf_generator.h:29
p
int p
Definition: cfModGcd.cc:4019
List
Definition: ftmpl_list.h:20
s
const CanonicalForm int s
Definition: facAbsFact.cc:55
replacevar
CanonicalForm replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition: cf_ops.cc:271
CFList
List< CanonicalForm > CFList
Definition: canonicalform.h:388
count
int status int void size_t count
Definition: si_signals.h:58
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const
Definition: cf_inline.cc:372
multiplicity
static int * multiplicity
Definition: interpolation.cc:86
AlgExtGenerator::clone
CFGenerator * clone() const
Definition: cf_generator.cc:216
tmp2
CFList tmp2
Definition: facFqBivar.cc:70
hasVar
int hasVar(const CanonicalForm &f, const Variable &v)
Definition: facAlgFuncUtil.cc:345
CFGenerator::item
virtual CanonicalForm item() const
Definition: cf_generator.h:28
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition: canonicalform.cc:543
CFFactor
Factor< CanonicalForm > CFFactor
Definition: canonicalform.h:385
List::append
void append(const T &)
Definition: ftmpl_list.cc:256
CFGenFactory::generate
static CFGenerator * generate()
Definition: cf_generator.cc:221
subst
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
Definition: facAlgFuncUtil.cc:120
alg_content
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
Definition: facAlgFunc.cc:42
facAlgFunc
CFFList facAlgFunc(const CanonicalForm &f, const CFList &as)
factorize a polynomial modulo an extension given by an irreducible characteristic set
Definition: facAlgFunc.cc:1043
degree
int degree(const CanonicalForm &f)
Definition: canonicalform.h:309
alg_LC
CanonicalForm alg_LC(const CanonicalForm &f, int lev)
Definition: facAlgFuncUtil.cc:110
merge
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
Definition: cfNewtonPolygon.cc:230
List::insert
void insert(const T &)
Definition: ftmpl_list.cc:193
On
void On(int sw)
switches
Definition: canonicalform.cc:1898
List::getLast
T getLast() const
Definition: ftmpl_list.cc:309
sqrfNorm
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
generateMipo
CanonicalForm generateMipo(int degOfExt)
Definition: facAlgFuncUtil.cc:90
ListIterator
Definition: ftmpl_list.h:17
mapIntoPIE
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
AlgExtGenerator
generate all elements in F_p(alpha) starting from 0
Definition: cf_generator.h:93