Loading...
Searching...
No Matches
cfCharSets.h File Reference

This file provides functions to compute characteristic sets. More...

`#include "cfCharSetsUtil.h"`

Go to the source code of this file.

## Functions

CFList | basicSet (const CFList &PS)
| basic set in the sense of Wang a.k.a. minimal ascending set in the sense of Greuel/Pfister
CFList | charSet (const CFList &PS)
| characteristic set
CFList | modCharSet (const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true)
| modified medial set
CFList | modCharSet (const CFList &PS, bool removeContents)
CFList | charSetViaCharSetN (const CFList &PS)
| compute a characteristic set via medial set
CFList | charSetN (const CFList &PS)
| medial set
CFList | charSetViaModCharSet (const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true)
| modified characteristic set, i.e. a characteristic set with certain factors removed
CFList | charSetViaModCharSet (const CFList &PS, bool removeContents=true)
| modified characteristic set, i.e. a characteristic set with certain factors removed
ListCFList | charSeries (const CFList &L)
| characteristic series
ListCFList FACTORY_PUBLIC | irrCharSeries (const CFList &PS)
| irreducible characteristic series
Varlist | neworder (const CFList &PolyList)
CFList | newordercf (const CFList &PolyList)
IntList FACTORY_PUBLIC | neworderint (const CFList &PolyList)
CFList | reorder (const Varlist &betterorder, const CFList &PS)
CFFList | reorder (const Varlist &betterorder, const CFFList &PS)
ListCFList | reorder (const Varlist &betterorder, const ListCFList &Q)

## Detailed Description

This file provides functions to compute characteristic sets.

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 Wang "On the Parallelization of characteristic-set based algorithms" or Greuel/Pfister "A Singular Introduction to Commutative Algebra".

Author
  Martin Lee

Definition in file cfCharSets.h.

## Function Documentation

## basicSet()

CFList basicSet | ( | const CFList & | PS | ) |

basic set in the sense of Wang a.k.a. minimal ascending set in the sense of Greuel/Pfister

Definition at line 150 of file cfCharSets.cc.

{
CFList QS= PS, BS, RS;
CanonicalForm b;
int cb, degb;
if (PS.length() < 2)
return PS;
CFListIterator i;
while (!QS.isEmpty())
{
b= lowestRank (QS);
cb= b.level();
BS= Union(CFList (b), BS);
if (cb <= 0)
return CFList();
else
{
degb= degree (b);
RS= CFList();
for (i= QS; i.hasItem(); i++)
{
if (degree (i.getItem(), cb) < degb)
RS= Union (CFList (i.getItem()), RS);
}
QS= RS;
}
}
return BS;
}
degree
int degree(const CanonicalForm &f)
Definition canonicalform.h:316
CFListIterator
ListIterator< CanonicalForm > CFListIterator
Definition canonicalform.h:396
CFList
List< CanonicalForm > CFList
Definition canonicalform.h:395
lowestRank
CanonicalForm lowestRank(const CFList &L)
Definition cfCharSetsUtil.cc:357
i
int i
Definition cfEzgcd.cc:132
b
CanonicalForm b
Definition cfModGcd.cc:4111
CanonicalForm
factory's main class
Definition canonicalform.h:86
List::length
int length() const
Definition ftmpl_list.cc:273
List::isEmpty
int isEmpty() const
Definition ftmpl_list.cc:267
Union
template List< Variable > Union(const List< Variable > &, const List< Variable > &)

## charSeries()

ListCFList charSeries | ( | const CFList & | L | ) |

characteristic series

Definition at line 411 of file cfCharSets.cc.

{
ListCFList tmp, result, tmp2, ppi1, ppi2, qqi, ppi, alreadyConsidered;
CFList l, charset, ini;
int count= 0;
int highestLevel= 1;
CFListIterator iter;
StoreFactors StoredFactors;
l= L;
for (iter= l; iter.hasItem(); iter++)
{
iter.getItem()= normalize (iter.getItem());
if (highestLevel < iter.getItem().level())
highestLevel= iter.getItem().level();
}
tmp= ListCFList (l);
while (!tmp.isEmpty())
{
sortListCFList (tmp);
l= tmp.getFirst();
tmp= Difference (tmp, l);
select (ppi, l.length(), ppi1, ppi2);
inplaceUnion (ppi2, qqi);
if (count > 0)
ppi= Union (ppi1, ListCFList (l));
else
ppi= ListCFList();
if (l.length() - 3 < highestLevel)
charset= charSetViaModCharSet (l, StoredFactors);
else
charset= charSetViaCharSetN (l);
if (charset.length() > 0 && charset.getFirst().level() > 0)
{
result= Union (ListCFList (charset), result);
ini= factorsOfInitials (charset);
ini= Union (ini, factorPSet (StoredFactors.FS1));
sortCFListByLevel (ini);
}
else
{
ini= factorPSet (StoredFactors.FS1);
sortCFListByLevel (ini);
}
tmp2= adjoin (ini, l, qqi);
tmp= Union (tmp2, tmp);
StoredFactors.FS1= CFList();
StoredFactors.FS2= CFList();
ppi1= ListCFList();
ppi2= ListCFList();
count++;
}
//TODO need to remove superflous components
return result;
}
ListCFList
List< CFList > ListCFList
Definition canonicalform.h:399
inplaceUnion
void inplaceUnion(const ListCFList &a, ListCFList &b)
Union of a and b stored in b.
Definition cfCharSetsUtil.cc:473
factorsOfInitials
CFList factorsOfInitials(const CFList &L)
Definition cfCharSetsUtil.cc:755
select
void select(const ListCFList &ppi, int length, ListCFList &ppi1, ListCFList &ppi2)
Definition cfCharSetsUtil.cc:570
sortListCFList
void sortListCFList(ListCFList &list)
sort in descending order of length of elements
Definition cfCharSetsUtil.cc:396
sortCFListByLevel
void sortCFListByLevel(CFList &list)
sort in descending order of level of elements
Definition cfCharSetsUtil.cc:428
factorPSet
CFList factorPSet(const CFList &PS)
Definition cfCharSetsUtil.cc:805
adjoin
ListCFList adjoin(const CFList &is, const CFList &qs, const ListCFList &qh)
Definition cfCharSetsUtil.cc:495
charSetViaCharSetN
CFList charSetViaCharSetN(const CFList &PS)
compute a characteristic set via medial set
Definition cfCharSets.cc:246
charSetViaModCharSet
CFList charSetViaModCharSet(const CFList &PS, StoreFactors &StoredFactors, bool removeContents)
characteristic set via modified medial set
Definition cfCharSets.cc:356
l
int l
Definition cfEzgcd.cc:100
CanonicalForm::level
int level() const
level() returns the level of CO.
Definition canonicalform.cc:576
List::getFirst
T getFirst() const
Definition ftmpl_list.cc:279
StoreFactors
class to store factors that get removed during char set computation
Definition cfCharSetsUtil.h:29
StoreFactors::FS2
CFList FS2
candidate factors that might get removed
Definition cfCharSetsUtil.h:32
StoreFactors::FS1
CFList FS1
factors that were removed
Definition cfCharSetsUtil.h:31
iter
CFFListIterator iter
Definition facAbsBiFact.cc:54
result
return result
Definition facAbsBiFact.cc:76
tmp2
CFList tmp2
Definition facFqBivar.cc:75
Difference
template List< Variable > Difference(const List< Variable > &, const List< Variable > &)
count
int status int void size_t count
Definition si_signals.h:69
normalize
static poly normalize(poly next_p, ideal add_generators, syStrategy syzstr, int *g_l, int *p_l, int crit_comp)
Definition syz3.cc:1027

## charSet()

CFList charSet | ( | const CFList & | PS | ) |

characteristic set

Definition at line 187 of file cfCharSets.cc.

{
CFList QS= PS, RS= PS, CSet, tmp;
CFListIterator i;
CanonicalForm r;
while (!RS.isEmpty())
{
CSet= basicSet (QS);
RS= CFList();
if (CSet.length() > 0 && CSet.getFirst().level() > 0)
{
tmp= Difference (QS, CSet);
for (i= tmp; i.hasItem(); i++)
{
r= Prem (i.getItem(), CSet);
if (r != 0)
RS= Union (RS, CFList (r));
}
QS= Union (QS, RS);
}
}
return CSet;
}
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
basicSet
CFList basicSet(const CFList &PS)
basic set in the sense of Wang a.k.a. minimal ascending set in the sense of Greuel/Pfister
Definition cfCharSets.cc:150

## charSetN()

CFList charSetN | ( | const CFList & | PS | ) |

medial set

Definition at line 216 of file cfCharSets.cc.

{
CFList QS= PS, RS= PS, CSet, tmp;
CFListIterator i;
CanonicalForm r;
while (!RS.isEmpty())
{
QS= uniGcd (QS);
CSet= basicSet (QS);
RS= CFList();
if (CSet.length() > 0 && CSet.getFirst().level() > 0)
{
tmp= Difference (QS, CSet);
for (i= tmp; i.hasItem(); i++)
{
r= Prem (i.getItem(), CSet);
if (!r.isZero())
RS= Union (RS, CFList (r));
}
QS= Union (CSet, RS);
}
}
return CSet;
}
uniGcd
CFList uniGcd(const CFList &L)
Definition cfCharSetsUtil.cc:721
CanonicalForm::isZero
CF_NO_INLINE bool isZero() const

## charSetViaCharSetN()

CFList charSetViaCharSetN | ( | const CFList & | PS | ) |

compute a characteristic set via medial set

Definition at line 246 of file cfCharSets.cc.

{
CFList L;
CFFList sqrfFactors;
CanonicalForm sqrf;
CFFListIterator iter2;
for (CFListIterator iter= PS; iter.hasItem(); iter++)
{
sqrf= 1;
sqrfFactors= sqrFree (iter.getItem());
for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
sqrf *= iter2.getItem().factor();
L= Union (L, CFList (normalize (sqrf)));
}
CFList result= charSetN (L);
if (result.isEmpty() || result.getFirst().inCoeffDomain())
return CFList(1);
CanonicalForm r;
CFList RS;
CFList tmp= Difference (L, result);
for (CFListIterator i= tmp; i.hasItem(); i++)
{
r= Premb (i.getItem(), result);
if (!r.isZero())
RS= Union (RS, CFList (r));
}
if (RS.isEmpty())
return result;
return charSetViaCharSetN (Union (L, Union (RS, result)));
}
CFFListIterator
ListIterator< CFFactor > CFFListIterator
Definition canonicalform.h:394
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
Premb
CanonicalForm Premb(const CanonicalForm &f, const CFList &L)
pseudo remainder of f by L with faster test for remainder being zero
Definition cfCharSetsUtil.cc:677
charSetN
CFList charSetN(const CFList &PS)
medial set
Definition cfCharSets.cc:216
sqrFree
CFFList FACTORY_PUBLIC sqrFree(const CanonicalForm &f, bool sort=false)
squarefree factorization
Definition cf_factor.cc:961
Factor::factor
T factor() const
Definition ftmpl_factor.h:30
ListIterator::hasItem
int hasItem()
Definition ftmpl_list.cc:439
ListIterator::getItem
T & getItem() const
Definition ftmpl_list.cc:431

## charSetViaModCharSet() [1/2]

CFList charSetViaModCharSet | ( | const CFList & | PS,
|  | bool | removeContents = true )

modified characteristic set, i.e. a characteristic set with certain factors removed

Definition at line 397 of file cfCharSets.cc.

{
StoreFactors tmp;
return charSetViaModCharSet (PS, tmp, removeContents);
}

## charSetViaModCharSet() [2/2]

CFList charSetViaModCharSet | ( | const CFList & | PS,
|  | StoreFactors & | StoredFactors,
|  | bool | removeContents )

modified characteristic set, i.e. a characteristic set with certain factors removed

modified characteristic set, i.e. a characteristic set with certain factors removed

Definition at line 356 of file cfCharSets.cc.

{
CFList L;
CFFList sqrfFactors;
CanonicalForm sqrf;
CFFListIterator iter2;
for (CFListIterator iter= PS; iter.hasItem(); iter++)
{
sqrf= 1;
sqrfFactors= sqrFree (iter.getItem());
for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
sqrf *= iter2.getItem().factor();
L= Union (L, CFList (normalize (sqrf)));
}
L= uniGcd (L);
CFList result= modCharSet (L, StoredFactors, removeContents);
if (result.isEmpty() || result.getFirst().inCoeffDomain())
return CFList(1);
CanonicalForm r;
CFList RS;
CFList tmp= Difference (L, result);
for (CFListIterator i= tmp; i.hasItem(); i++)
{
r= Premb (i.getItem(), result);
if (!r.isZero())
RS= Union (RS, CFList (r));
}
if (RS.isEmpty())
return result;
return charSetViaModCharSet (Union (L, Union (RS, result)), StoredFactors,
removeContents);
}
modCharSet
CFList modCharSet(const CFList &L, StoreFactors &StoredFactors, bool removeContents)
modified medial set
Definition cfCharSets.cc:284

## irrCharSeries()

ListCFList FACTORY_PUBLIC irrCharSeries | ( | const CFList & | PS | ) |

irreducible characteristic series

Definition at line 568 of file cfCharSets.cc.

{
CanonicalForm reducible, reducible2;
CFList qs, cs, factorset, is, ts, L;
CanonicalForm sqrf;
CFFList sqrfFactors;
CFFListIterator iter2;
for (CFListIterator iter= PS; iter.hasItem(); iter++)
{
sqrf= 1;
sqrfFactors= sqrFree (iter.getItem());
if (sqrfFactors.getFirst().factor().inCoeffDomain())
sqrfFactors.removeFirst();
for (iter2= sqrfFactors; iter2.hasItem(); iter2++)
sqrf *= iter2.getItem().factor();
sqrf= normalize (sqrf);
L= Union (CFList (sqrf), L);
}
ListCFList pi, ppi, qqi, qsi, iss, qhi= ListCFList(L);
int nr_of_iteration= 0, indexRed, highestlevel= 0;
for (CFListIterator iter= PS; iter.hasItem(); iter++)
{
if (level (iter.getItem()) > highestlevel)
highestlevel= level(iter.getItem());
}
while (!qhi.isEmpty())
{
sortListCFList (qhi);
qs= qhi.getFirst();
ListCFList ppi1,ppi2;
select (ppi, qs.length(), ppi1, ppi2);
inplaceUnion (ppi2, qqi);
if (nr_of_iteration == 0)
{
nr_of_iteration += 1;
ppi= ListCFList();
}
else
{
nr_of_iteration += 1;
ppi= Union (ppi1, ListCFList (qs));
}
StoreFactors StoredFactors;
if (qs.length() - 3 < highestlevel)
cs= modCharSet (qs, StoredFactors, false);
else
cs= charSetN (qs);
cs= removeContent (cs, StoredFactors);
factorset= StoredFactors.FS1;
if (!cs.isEmpty() && cs.getFirst().level() > 0)
{
ts= irredAS (cs, indexRed, reducible);
if (indexRed <= 0) // irreducible
{
if (!isSubset (cs,qs))
cs= charSetViaCharSetN (Union (qs,cs));
if (!find (pi, cs))
{
pi= Union (ListCFList (cs), pi);
if (cs.getFirst().level() > 0)
{
ts= irredAS (cs, indexRed, reducible);
if (indexRed <= 0) //irreducible
{
qsi= Union (ListCFList(cs), qsi);
if (cs.length() == highestlevel)
is= factorPSet (factorset);
else
is= Union (factorsOfInitials (cs), factorPSet (factorset));
iss= adjoin (is, qs, qqi);
}
}
else
iss= adjoin (factorPSet (factorset), qs, qqi);
}
else
iss= adjoin (factorPSet (factorset), qs, qqi);
}
if (indexRed > 0)
{
is= factorPSet (factorset);
if (indexRed > 1)
{
CFList cst;
for (CFListIterator i= cs ; i.hasItem(); i++)
{
if (i.getItem() == reducible)
break;
else
cst.append (i.getItem());
}
is= Union (factorsOfInitials (Union (cst, CFList (reducible))), is);
iss= Union (adjoinb (ts, qs, qqi, cst), adjoin (is, qs, qqi));
}
else
iss= adjoin (Union (is, ts), qs, qqi);
}
}
else
iss= adjoin (factorPSet (factorset), qs, qqi);
if (qhi.length() > 1)
{
qhi.removeFirst();
qhi= Union (iss, qhi);
}
else
qhi= iss;
}
if (!qsi.isEmpty())
return contract (qsi);
return ListCFList(CFList (1)) ;
}
level
int level(const CanonicalForm &f)
Definition canonicalform.h:331
removeContent
void removeContent(CanonicalForm &F, CanonicalForm &cF)
Definition cfCharSetsUtil.cc:776
isSubset
bool isSubset(const CFList &PS, const CFList &Cset)
is PS a subset of Cset ?
Definition cfCharSetsUtil.cc:461
adjoinb
ListCFList adjoinb(const CFList &is, const CFList &qs, const ListCFList &qh, const CFList &cs)
Definition cfCharSetsUtil.cc:533
contract
ListCFList contract(const ListCFList &cs)
Definition cfCharSetsUtil.cc:926
irredAS
static CFList irredAS(CFList &AS, int &indexRed, CanonicalForm &reducible)
Definition cfCharSets.cc:507
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
List::removeFirst
void removeFirst()
Definition ftmpl_list.cc:287
List::append
void append(const T &)
Definition ftmpl_list.cc:256
find
template bool find(const List< CanonicalForm > &, const CanonicalForm &)
pi
#define pi
Definition libparse.cc:1145

## modCharSet() [1/2]

CFList modCharSet | ( | const CFList & | PS,
|  | bool | removeContents )

Definition at line 404 of file cfCharSets.cc.

{
StoreFactors tmp;
return modCharSet (PS, tmp, removeContents);
}

## modCharSet() [2/2]

CFList modCharSet | ( | const CFList & | PS,
|  | StoreFactors & | StoredFactors,
|  | bool | removeContents = true )

modified medial set

Definition at line 284 of file cfCharSets.cc.

{
CFList QS, RS= L, CSet, tmp, contents, initial, removedFactors;
CFListIterator i;
CanonicalForm r, cF;
bool noRemainder= true;
StoreFactors StoredFactors2;
QS= uniGcd (L);
while (!RS.isEmpty())
{
noRemainder= true;
CSet= basicSet (QS);
initial= factorsOfInitials (CSet);
StoredFactors2.FS1= StoredFactors.FS1;
StoredFactors2.FS2= Union (StoredFactors2.FS2, initial);
RS= CFList();
if (CSet.length() > 0 && CSet.getFirst().level() > 0)
{
tmp= Difference (QS, CSet);
for (i= tmp; i.hasItem(); i++)
{
r= Prem (i.getItem(), CSet);
if (!r.isZero())
{
noRemainder= false;
if (removeContents)
{
removeContent (r, cF);
if (!cF.isZero())
contents= Union (contents, factorPSet (CFList(cF))); //factorPSet maybe too much it should suffice to do a squarefree factorization instead
}
removeFactors (r, StoredFactors2, removedFactors);
StoredFactors2.FS1= Union (StoredFactors2.FS1, removedFactors);
StoredFactors2.FS2= Difference (StoredFactors2.FS2, removedFactors);
removedFactors= CFList();
RS= Union (RS, CFList (r));
}
}
if (removeContents && !noRemainder)
{
StoredFactors.FS1= Union (StoredFactors2.FS1, contents);
StoredFactors.FS2= StoredFactors2.FS2;
}
else
StoredFactors= StoredFactors2;
QS= Union (CSet, RS);
contents= CFList();
removedFactors= CFList();
}
else
StoredFactors= StoredFactors2;
}
return CSet;
}
removeFactors
void removeFactors(CanonicalForm &r, StoreFactors &StoredFactors, CFList &removedFactors)
Definition cfCharSetsUtil.cc:823
initial
poly initial(const poly p, const ring r, const gfan::ZVector &w)
Returns the initial form of p with respect to w.
Definition initial.cc:30

## neworder()

Varlist neworder | ( | const CFList & | PolyList | ) |

## newordercf()

CFList newordercf | ( | const CFList & | PolyList | ) |

Definition at line 75 of file cfCharSets.cc.

{
Varlist reorder= neworder (PolyList);
CFList output;
for (VarlistIterator i=reorder; i.hasItem(); i++)
output.append (CanonicalForm (i.getItem()));
return output;
}
VarlistIterator
ListIterator< Variable > VarlistIterator
Definition canonicalform.h:404
Varlist
List< Variable > Varlist
Definition canonicalform.h:403
reorder
CFList reorder(const Varlist &betterorder, const CFList &PS)
Definition cfCharSets.cc:101
neworder
Varlist neworder(const CFList &PolyList)

## neworderint()

IntList FACTORY_PUBLIC neworderint | ( | const CFList & | PolyList | ) |

Definition at line 88 of file cfCharSets.cc.

{
Varlist reorder= neworder (PolyList);
IntList output;
for (VarlistIterator i= reorder; i.hasItem(); i++)
output.append (level (i.getItem()));
return output;
}
IntList
List< int > IntList
Definition canonicalform.h:401

## reorder() [1/3]

CFFList reorder | ( | const Varlist & | betterorder,
|  | const CFFList & | PS )

Definition at line 120 of file cfCharSets.cc.

{
int i= 1, n= betterorder.length();
Intarray v (1, n);
CFFList ps= PS;
//initalize:
for (VarlistIterator j= betterorder; j.hasItem(); j++)
{
v[i]= level (j.getItem());
i++;
}
// reorder:
for (i= 1; i <= n; i++)
ps= swapvar (ps, Variable (v[i]), Variable (n + i));
return ps;
}
Intarray
Array< int > Intarray
Definition canonicalform.h:405
swapvar
CanonicalForm FACTORY_PUBLIC swapvar(const CanonicalForm &, const Variable &, const Variable &)
swapvar() - swap variables x1 and x2 in f.
Definition cf_ops.cc:168
Variable
factory's class for variables
Definition factory.h:127
v
const Variable & v
< [in] a sqrfree bivariate poly
Definition facBivar.h:39
j
int j
Definition facHensel.cc:110

## reorder() [2/3]

CFList reorder | ( | const Varlist & | betterorder,
|  | const CFList & | PS )

Definition at line 101 of file cfCharSets.cc.

{
int i= 1, n= betterorder.length();
Intarray v (1, n);
CFList ps= PS;
//initalize:
for (VarlistIterator j= betterorder; j.hasItem(); j++)
{
v[i]= level (j.getItem());
i++;
}
// reorder:
for (i= 1; i <= n; i++)
ps= swapvar (ps, Variable (v[i]), Variable (n + i));
return ps;
}

## reorder() [3/3]

ListCFList reorder | ( | const Varlist & | betterorder,
|  | const ListCFList & | Q )

Definition at line 140 of file cfCharSets.cc.

{
ListCFList Q1;
for (ListCFListIterator i= Q; i.hasItem(); i++)
Q1.append (reorder (betterorder, i.getItem()));
return Q1;
}
ListCFListIterator
ListIterator< CFList > ListCFListIterator
Definition canonicalform.h:400
Q
#define Q
Definition sirandom.c:26