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 More...
CFList	charSet (const CFList &PS)
	characteristic set More...
CFList	modCharSet (const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true)
	modified medial set More...
CFList	modCharSet (const CFList &PS, bool removeContents)
CFList	charSetViaCharSetN (const CFList &PS)
	compute a characteristic set via medial set More...
CFList	charSetN (const CFList &PS)
	medial set More...
CFList	charSetViaModCharSet (const CFList &PS, StoreFactors &StoredFactors, bool removeContents=true)
	modified characteristic set, i.e. a characteristic set with certain factors removed More...
CFList	charSetViaModCharSet (const CFList &PS, bool removeContents=true)
	modified characteristic set, i.e. a characteristic set with certain factors removed More...
ListCFList	charSeries (const CFList &L)
	characteristic series More...
ListCFList FACTORY_PUBLIC	irrCharSeries (const CFList &PS)
	irreducible characteristic series More...
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;
}

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;
}

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;
}

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;
}

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)));
}

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);
}

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)) ;
}

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;
}

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;
}

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;
}

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;
}

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;
}