My Project
Loading...
Searching...
No Matches
Functions
facAlgFunc.cc File Reference

This file provides functions to factorize polynomials over alg. More...

#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}
Rational abs(const Rational &a)
Definition: GMPrat.cc:436
int i
Definition: cfEzgcd.cc:132
FILE * f
Definition: checklibs.c:9
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
factory's main class
Definition: canonicalform.h:86
return result
Definition: facAbsBiFact.cc:75
CanonicalForm alg_gcd(const CanonicalForm &fff, const CanonicalForm &ggg, const CFList &as)
Definition: facAlgFunc.cc:61

◆ 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}
int degree(const CanonicalForm &f)
CanonicalForm FACTORY_PUBLIC vcontent(const CanonicalForm &f, const Variable &x)
CanonicalForm vcontent ( const CanonicalForm & f, const Variable & x )
Definition: cf_gcd.cc:653
CanonicalForm Prem(const CanonicalForm &F, const CanonicalForm &G)
pseudo remainder of F by G with certain factors of LC (g) cancelled
Variable x
Definition: cfModGcd.cc:4082
g
Definition: cfModGcd.cc:4090
CF_NO_INLINE bool isZero() const
bool inCoeffDomain() const
int level() const
level() returns the level of CO.
T getLast() const
Definition: ftmpl_list.cc:309
factory's class for variables
Definition: variable.h:33
CanonicalForm res
Definition: facAbsFact.cc:60
CanonicalForm divide(const CanonicalForm &ff, const CanonicalForm &f, const CFList &as)
int hasVar(const CanonicalForm &f, const Variable &v)
int hasAlgVar(const CanonicalForm &f, const Variable &v)
CanonicalForm alg_content(const CanonicalForm &f, const CFList &as)
Definition: facAlgFunc.cc:42
const Variable & v
< [in] a sqrfree bivariate poly
Definition: facBivar.h:39
CFList tmp2
Definition: facFqBivar.cc:72
int j
Definition: facHensel.cc:110
bool delta(X x, Y y, D d)
Definition: TestSuite.h:160
int gcd(int a, int b)
Definition: walkSupport.cc:836

◆ 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}
bool isOn(int sw)
switches
void On(int sw)
switches
void Off(int sw)
switches
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
static const int SW_RATIONAL
set to 1 for computations over Q
Definition: cf_defs.h:31
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
int length() const
Definition: ftmpl_list.cc:273
CFFList append(const CFFList &Inputlist, const CFFactor &TheFactor)
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

◆ 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();
913 CFList reduceresult;
915
916// F1: [Test trivial cases]
917// 1) first trivial cases:
918 if (vf.level() <= as.getLast().level())
919 {
920 if (!isRat && getCharacteristic() == 0)
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)
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)
978 return result;
979 }
980
981 Fgcd= pp (Fgcd);
982 Ggcd= pp (Ggcd);
983 if (!isRat && getCharacteristic() == 0)
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}
CanonicalForm FACTORY_PUBLIC pp(const CanonicalForm &)
CanonicalForm pp ( const CanonicalForm & f )
Definition: cf_gcd.cc:676
List< CFFactor > CFFList
Factor< CanonicalForm > CFFactor
int level(const CanonicalForm &f)
int ** merge(int **points1, int sizePoints1, int **points2, int sizePoints2, int &sizeResult)
Variable mvar() const
mvar() returns the main variable of CO or Variable() if CO is in a base domain.
void append(const T &)
Definition: ftmpl_list.cc:256
int level() const
Definition: variable.h:49
Varlist varsInAs(const Varlist &uord, const CFList &Astar)
int getDegOfExt(IntList &degreelist, int n)
bool isInseparable(const CFList &Astar)
CanonicalForm generateMipo(int degOfExt)
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 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
template List< Variable > Union(const List< Variable > &, const List< Variable > &)
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
STATIC_VAR int * multiplicity
void prune(Variable &alpha)
Definition: variable.cc:261
Variable rootOf(const CanonicalForm &mipo, char name)
returns a symbolic root of polynomial with name name Use it to define algebraic variables
Definition: variable.cc:162

◆ 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}
CanonicalForm getVars(const CanonicalForm &f)
CanonicalForm getVars ( const CanonicalForm & f )
Definition: cf_ops.cc:350
List< CanonicalForm > CFList
#define ASSERT(expression, message)
Definition: cf_assert.h:99
CF_NO_INLINE bool isOne() const
T & getItem() const
Definition: ftmpl_list.cc:431
void insert(const T &)
Definition: ftmpl_list.cc:193
int isEmpty() const
Definition: ftmpl_list.cc:267
CFFListIterator iter
Definition: facAbsBiFact.cc:53
void deflateDegree(const CanonicalForm &F, int &pExp, int n)
CanonicalForm inflatePoly(const CanonicalForm &F, int exp)
CanonicalForm deflatePoly(const CanonicalForm &F, int exp)
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

◆ 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}
CanonicalForm FACTORY_PUBLIC content(const CanonicalForm &)
CanonicalForm content ( const CanonicalForm & f )
Definition: cf_gcd.cc:603
CanonicalForm mapinto(const CanonicalForm &f)
CanonicalForm bCommonDen(const CanonicalForm &f)
CanonicalForm bCommonDen ( const CanonicalForm & f )
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition: cf_factor.cc:957
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
CanonicalForm genZero() const
input/output
const CanonicalForm int s
Definition: facAbsFact.cc:51
const CanonicalForm int const CFList const Variable & y
Definition: facAbsFact.cc:53
static CanonicalForm resultante(const CanonicalForm &f, const CanonicalForm &g, const Variable &v)
Definition: facAlgFunc.cc:179
#define R
Definition: sirandom.c:27

◆ 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 99 of file cf_factor.cc.

100{
101 printf("%s",s1);
102 if (f.isZero()) printf("+0");
103 //else if (! f.inCoeffDomain() )
104 else if (! f.inBaseDomain() )
105 {
106 int l = f.level();
107 for ( CFIterator i = f; i.hasTerms(); i++ )
108 {
109 int e=i.exp();
110 if (i.coeff().isOne())
111 {
112 printf("+");
113 if (e==0) printf("1");
114 else
115 {
116 printf("%c",'a'+l-1);
117 if (e!=1) printf("^%d",e);
118 }
119 }
120 else
121 {
122 out_cf("+(",i.coeff(),")");
123 if (e!=0)
124 {
125 printf("*%c",'a'+l-1);
126 if (e!=1) printf("^%d",e);
127 }
128 }
129 }
130 }
131 else
132 {
133 if ( f.isImm() )
134 {
136 {
137 long a= imm2int (f.getval());
138 if ( a == gf_q )
139 printf ("+%ld", a);
140 else if ( a == 0L )
141 printf ("+1");
142 else if ( a == 1L )
143 printf ("+%c",gf_name);
144 else
145 {
146 printf ("+%c",gf_name);
147 printf ("^%ld",a);
148 }
149 }
150 else
151 {
152 long l=f.intval();
153 if (l<0) printf("%ld",l);
154 else printf("+%ld",l);
155 }
156 }
157 else
158 {
159 #ifdef NOSTREAMIO
160 if (f.inZ())
161 {
162 mpz_t m;
164 char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
165 str = mpz_get_str( str, 10, m );
166 puts(str);
167 delete[] str;
168 mpz_clear(m);
169 }
170 else if (f.inQ())
171 {
172 mpz_t m;
174 char * str = new char[mpz_sizeinbase( m, 10 ) + 2];
175 str = mpz_get_str( str, 10, m );
176 while(str[strlen(str)]<' ') { str[strlen(str)]='\0'; }
177 puts(str);putchar('/');
178 delete[] str;
179 mpz_clear(m);
181 str = new char[mpz_sizeinbase( m, 10 ) + 2];
182 str = mpz_get_str( str, 10, m );
183 while(str[strlen(str)]<' ') { str[strlen(str)]='\0'; }
184 puts(str);
185 delete[] str;
186 mpz_clear(m);
187 }
188 #else
189 std::cout << f;
190 #endif
191 }
192 //if (f.inZ()) printf("(Z)");
193 //else if (f.inQ()) printf("(Q)");
194 //else if (f.inFF()) printf("(FF)");
195 //else if (f.inPP()) printf("(PP)");
196 //else if (f.inGF()) printf("(PP)");
197 //else
198 if (f.inExtension()) printf("E(%d)",f.level());
199 }
200 printf("%s",s2);
201}
int l
Definition: cfEzgcd.cc:100
int m
Definition: cfEzgcd.cc:128
#define GaloisFieldDomain
Definition: cf_defs.h:18
void out_cf(const char *s1, const CanonicalForm &f, const char *s2)
cf_algorithm.cc - simple mathematical algorithms.
Definition: cf_factor.cc:99
static int gettype()
Definition: cf_factory.h:28
VAR int gf_q
Definition: gfops.cc:47
VAR char gf_name
Definition: gfops.cc:52
static long imm2int(const InternalCF *const imm)
Definition: imm.h:70
char * str(leftv arg)
Definition: shared.cc:704
void gmp_denominator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:40
void gmp_numerator(const CanonicalForm &f, mpz_ptr result)
Definition: singext.cc:20

◆ 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)
185 CanonicalForm fz = f * cd;
186 cd = bCommonDen( g );
187 CanonicalForm gz = g * cd;
188 if (!on_rational && getCharacteristic() == 0)
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}
CanonicalForm cd(bCommonDen(FF))
Definition: cfModGcd.cc:4089
CanonicalForm resultantZ(const CanonicalForm &A, const CanonicalForm &B, const Variable &x, bool prob)
modular resultant algorihtm over Z
CanonicalForm FACTORY_PUBLIC resultant(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
CanonicalForm resultant ( const CanonicalForm & f, const CanonicalForm & g, const Variable & x )

◆ 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;
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)
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)
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)
423
424 return Returnlist;
425}
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
CanonicalForm FACTORY_PUBLIC icontent(const CanonicalForm &f)
CanonicalForm icontent ( const CanonicalForm & f )
Definition: cf_gcd.cc:74
CanonicalForm FACTORY_PUBLIC replacevar(const CanonicalForm &, const Variable &, const Variable &)
CanonicalForm replacevar ( const CanonicalForm & f, const Variable & x1, const Variable & x2 )
Definition: cf_ops.cc:271
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition: cf_ops.cc:168
CanonicalForm Lc(const CanonicalForm &f)
CanonicalForm LC(const CanonicalForm &f)
CFArray evaluate(const CFArray &A, const CFList &evalPoints)
Definition: cfModGcd.cc:2031
Variable alpha
Definition: facAbsBiFact.cc:51
CanonicalForm backSubst(const CanonicalForm &F, const CFList &a, const CFList &b)
CanonicalForm QuasiInverse(const CanonicalForm &f, const CanonicalForm &g, const Variable &x)
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
template CanonicalForm tmax(const CanonicalForm &, const CanonicalForm &)
STATIC_VAR Poly * h
Definition: janet.cc:971

◆ 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{
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}
generate all elements in F_p(alpha) starting from 0
Definition: cf_generator.h:94
generate all elements in F_p starting from 0
Definition: cf_generator.h:56
generate integers starting from 0
Definition: cf_generator.h:37
mipo *CanonicalForm norm
Definition: facAlgExt.cc:61

◆ 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
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
858retry:
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}
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
int p
Definition: cfModGcd.cc:4078
int ipower(int b, int m)
int ipower ( int b, int m )
Definition: cf_util.cc:27
class CFMap
Definition: cf_map.h:85
CanonicalForm deriv() const
deriv() - return the formal derivation of CO.
void removeLast()
Definition: ftmpl_list.cc:317
CanonicalForm factor
Definition: facAbsFact.cc:97
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
bool found
Definition: facFactorize.cc:55
void mult(unsigned long *result, unsigned long *a, unsigned long *b, unsigned long p, int dega, int degb)
Definition: minpoly.cc:647
#define M
Definition: sirandom.c:25

◆ 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
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)
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)
499 else if (degree (vminpoly) > 0)
500 Gen= AlgExtGenerator (vminpoly).clone();
501 else
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)
597
598 delete Gen;
599
600 return L;
601}
bool hasFirstAlgVar(const CanonicalForm &f, Variable &a)
check if poly f contains an algebraic variable a
Definition: cf_ops.cc:679
CFGenerator * clone() const
static CFGenerator * generate()
virtual class for generators
Definition: cf_generator.h:22
CanonicalForm alg_LC(const CanonicalForm &f, int lev)
CanonicalForm subst(const CanonicalForm &f, const CFList &a, const CFList &b, const CanonicalForm &Rstar, bool isFunctionField)
static CFList simpleExtension(CFList &backSubst, const CFList &Astar, const Variable &Extension, bool &isFunctionField, CanonicalForm &R)
Definition: facAlgFunc.cc:313
int status int void size_t count
Definition: si_signals.h:59